LINUX.ORG.RU

Вопрос по дискретной математике - найти все возможные варианты связывания элементов таблицы

 , , , ,


0

1

Здравствуйте.
Ищу метод решения проблемы поиска слов в таблице (на манер сканвордов).
В данный момент уже запрограммированы все структуры данных, осталось только написать метод самого решения.

Алгоритм, каким я его вижу:
У нас есть квадратная матрица с кодами букв, каждая клетка матрицы соответственно имеет свою координату.
1) Сгенерировать список возможных «в принципе» слов, по координатам (буквы рядом - значит их можно связать).
По сути, задача по построению всевозможных графов на этой таблице.
И я абсолютно не понимаю как найти все возможные перестановки.
Условия:

  • Графов в таблице должно быть больше одного.
  • Каждый граф должен иметь больше 2х листьев
  • Графы односвязные, ориентированные. Обратное направление - новый случай.

2) Используя сгенерированый список, проверить каждый вариант расположения букв на соответствие словарю.

Прошу натолкнуть на алгоритм действия, или показать на примере готового решения \ общей задачи.
Код не покажу, тк задача сугубо теоретическая, пока что.

UPD: Таки скорее по дискретной математике вопрос, просто у нас это в курсе вероятностей шло х)

Как-то рекурсивно, наверное, поле обходить надо с буфером в размер максимальной длины слова. Это если слова могут в любом направлении вилять. А если только вертикально и горизонтально, то можно и циклом обойтись, мне кажется.

Начните с простого — с одной строки и найдите там все возможные слова.

anonymous ()
Ответ на: комментарий от anonymous

Хотелось бы сначала на бумаге решить.
Я догадываюсь как решить и в принципе, могу, но:
1) Скорее всего это решение будет неоптимально 2) Нет 100% уверенности что я найду все возможные комбинации

mersinvald ★★★★★ ()
Ответ на: комментарий от anonymous

Собственно, в 1м пункте нам не важно что там буквы, задача именно на нахождения возможностей связать (простите) связуемые элементы в N-е число графов N-го размера, так чтобы получить максимальную выборку таковых графов.

mersinvald ★★★★★ ()

Слова могут располагаться не по линии, а змейкой? Самое быстрое, мне кажется, взять список всех слов и пробовать подставлять. Предварительно можно составить всевозможные N-граммы небольшой длины и отфильтровать часть слов и позиций.

Bell ()
Ответ на: комментарий от Bell

Ну таки да, я и говорю: надо предварительно составить список всех возможных n-грамм, которые можно разместить в таблице.
Слова могут быть как вертикальными, так горизонтальными и змейкой.
Диагоналей нет, слава Одину.

Можно и прогнать сразу словами, но не факт что я получу избыточную выборку решений - а какие-то могут и не подойти.

mersinvald ★★★★★ ()
Ответ на: комментарий от Bell

А, да, забыл сказать: сравнение со сканвордами не совсем корректно.
У меня нет изначально списка слов, только словарь Ожегова распарсеный, а решение подойдет только конкретное.

mersinvald ★★★★★ ()
Ответ на: комментарий от mersinvald

Тогда вроде просто. Берешь слово, берешь из него N-грамму пореже и пытаешься подставлять в таблицу по месту таких же N-грамм. Я бы так сделал.

Bell ()
Ответ на: комментарий от Bell

Я думал об этом, но скорость работы подобного решения оставляет желать лучшего.
Я везде ужался в O(n), хотелось бы что-то хотя бы близкое к этому найти)
Все таки я бы предпочел остаться при моем плане решения и найти полную выборку перестановок.
Надеюсь, кто-нибудь что-то подскажет по этому поводу.

mersinvald ★★★★★ ()
Ответ на: комментарий от mersinvald

Линейной скорости тут никак не получится. По моим подсчётам, на поле 10х10 с максимальной длиной слова в 10 букв будет порядка 7 млн вариантов «слов».

anonymous ()

n*n графов у тебя уже есть. загоняй по ним поиск в глубину пока остаются слова-кандидаты. для поиска по всему словарю сразу см ахо-корасика.

anonymous ()

Конечно, такой алгоритм тоже годится, однако его можно существенно ускорить: есть такие последовательности букв, что не найдется ни одного слова, начинающегося с данной последовательности. Соответственно, очень много «возможных слов» можно даже не строить, не хранить и не проверять в конце.

И я абсолютно не понимаю как найти все возможные перестановки.

Рекурсивно. Представь, что уже построена часть слова из N букв, занимающая ячейки (x0;y0); (x1;y1).... (xN; yN). Какие слова можно построить на ее основе? Очевидно, такие, у которых N+1-я буква находится рядом с (xN; yN), не выходит за рамки таблицы и не пересекается с буквами (x0; y0)... (xN-1; yN-1). Далее остается перебрать слова, начинающиеся из каждой клетки таблицы.

amomymous ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.