Я делаю Tetris интересным проектом (а не домашним заданием) и хотел бы реализовать AI, чтобы компьютер мог играть сам. То, как я слышал, это использовать BFS для поиска в доступных местах, а затем создать совокупный балл самого разумного места падения...
Но мне сложно понять алгоритмы BFS и DFS. То, как я узнаю лучше всего, это вычеркнуть... правильно ли мои рисунки?
Спасибо!
Конечный результат ваших обходов верен, вы довольно близки. Тем не менее, вы немного в деталях.
В первом поиске глубины вы попадёте в node, пометьте его как посетив и уложите в него своих невидимых детей. В этой последовательности. Порядок может показаться неуместным для дерева, но если у вас есть график с циклами, вы можете упасть в бесконечный цикл, но это еще одно обсуждение.
Учитывая базовый алгоритм, после того, как вы введете корень node в стек, вы начнете свою первую итерацию, сразу же попадёв A. Он не останется в стеке до конца алгоритма. Вы сразу же поместите A, стек D, C и B (или B, C и D, вы можете сделать это слева направо или налево, это ваш выбор) и пометить A как посещенный. Прямо сейчас, ваш стек имеет D внизу, C посередине и B сверху.
Следующий node выскочил B. Вы нажмете F и E в стек (я сохраню порядок такой же, как ваш), помечая B как посещенный. Стек имеет сверху вниз E F C D. Затем появляется E, новые узлы не добавляются, а E отмечен как посещенный. Цикл будет продолжаться, делая то же самое с F, C и D. Окончательный порядок - A B E F C D.
Я попытаюсь переписать алгоритм так же, как ваш:
Push root into stack
Loop until stack is empty
Pop node N on top of stack
Mark N as visited
For each children M of N
If M has not been visited (M.visited() == false)
Push M on top of stack
Я не буду вдаваться в подробности первого поиска ширины, алгоритм точно такой же. Разница заключается в структуре данных и том, как она ведет себя. Очередь - это FIFO (First In First Out), и из-за этого вы будете посещать все узлы того же уровня, прежде чем вы начнете посещать узлы на нижних уровнях.
Прежде всего, я считаю, что ваши обходы выглядят хорошо (из краткого обзора). Я дам вам несколько полезных ссылок ниже.
Я нашел несколько достойных видео на YouTube по этому поводу, но вот один (не лучший, что я видел), который покрывает его http://www.youtube.com/watch?v=eXaaYoTKBlE. Если вы делаете это ради забавы, создайте две версии: одну с DFS и одну с BFS, и сравните их, чтобы заметить разницу. Также скачайте поисковик графика и любые другие инструменты, которые вы найдете полезными из http://www.aispace.org/downloads.shtml, если хотите отследить их для лучшего понимания. И последнее, но не менее важное: вопрос о stackoverflow для DFS и BFS http://www.stackoverflow.com/info/687731/