Почему DFS работает при попытке найти все допустимые слова на доске Boggle

Я программно решал игру Boggle и заметил, что поиск в глубину можно использовать для поиска всех допустимых комбинаций букв на доске. Доска Boggle описана здесь.

Скажем, у нас есть доска 4x4. Для каждого персонажа на доске используйте DFS, чтобы найти все пути на доске (единственное правило — вы не можете использовать один символ более одного раза). Почему для этого работает DFS, если доска Boggle на самом деле не является графиком? Кроме того, к каким другим типам задач можно применить DFS, которые аналогичны этому использованию?


graph algorithm boggle
person jcm    schedule 18.12.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Это потому, что это (или может быть) представлено графом. Боггл-слова состоят из соседних букв, расположенных горизонтально, вертикально или по диагонали. Таким образом, вы можете построить график связей между буквами, следуя этому правилу. Кроме того, DFS не посещает узел дважды, поскольку хранит список уже посещенных узлов. Таким образом, выполняется другое правило, согласно которому букву можно использовать только один раз.

DFS (и BFS тоже) в конечном итоге обнаружит каждый путь в графе, поэтому вы можете сравнить сгенерированный таким образом список путей со словарем допустимых слов, чтобы определить общее количество допустимых слов из одной доски Boggle.

Самое известное использование DFS, конечно, для поиска пути — почти любое пространство может быть отображено в графе, а затем найден кратчайший или самый длинный путь. DFS может быть полезен для нахождения радиуса графа и, следовательно, самого центрального узла. Это может быть полезно для таких вещей, как алгоритмы заливки, когда вы хотите быстро заполнить внутреннюю часть неправильной формы, так как расширение края произойдет быстрее всего, если начать с центра графа.

person Aaron D    schedule 18.12.2015

arrow_upward
0
arrow_downward

Вы можете применять DFS или другие алгоритмы графа, потому что вы в основном играете на сетчатом графе с диагоналями. .

введите здесь описание изображения

Поместите свои буквы вместо точек, и у вас есть график. Теперь, почему DFS будет работать здесь?

Когда вы создаете слово в этой игре — вы соединяете соседние вершины и тем самым создаете путь на графе. Итак, вот подход, с которого вы можете начать (и улучшить).

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

Вы можете видеть, что в моей части графика вы можете легко найти слово TORUS.

Почему имеет смысл использовать DFS, а не BFS? Вот несколько причин:

  • легче реализовать
  • намного меньшая космическая сложность

Какова сложность моего алгоритма Предположим, что у вас есть сетка n * m и самое длинное слово имеет длину d. Потому что в моем алгоритме вы реализуете поиск в глубину из всех вершин, а сложность поиска в глубину составляет O(b^d), где средняя ветвь немного меньше 8 (может быть даже меньше 7, потому что здесь не может быть циклов). Поиск в наборе id O(1). Итак, сложность m * n * 8^d.

Как его улучшить? Нет смысла искать слово TLRSOU, потому что в английском алфавите нет слов, начинающихся с TLR. Поэтому лучше хранить слова в trie и быстро завершать ветки, которые не делают смысл.

person Salvador Dali    schedule 18.12.2015