Должен ли DFS проверять детей на предмет состояния цели?

Question

Должен ли DFS (поиск в глубину) проверять все дочерние элементы данного узла на предмет состояния цели перед переходом к следующему узлу?

Answer 1

Да (кроме случаев, когда DFS останавливается на дочернем узле, конечно).Демоверсии:

• http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations.html
• http://www.cs.sunysb.edu/~skiena/combinatorica/animations/search.html
• http://www.cs.duke.edu/csed/jawaa2/examples/DFS.html

Answer 2

Поиск в глубину в первую очередь означает именно то, что: запустите самые левые дочерние узлы first . Только когда у узла нет дочерних элементов, вы отменяете свои вызовы и пробуете другого дочернего элемента на более высоком уровне. Вы можете видеть, что это анимация, левый узел корня не сначала проверяет все дочерние элементы.

Сначала вы можете проверить всех детей: это называется ширина первый поиск. В случае анимации, предоставленной Франком, это приведет к тому, что оба дочерних элемента корня будут проверены, а затем опустятся вниз по левому крайнему дочернему элементу и проверит оба этих узла и т. Д.

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

Обратите внимание: если вы ищете самый дешевый (минимальная глубина) целевой путь (при условии, что доступно несколько таких путей), то широта - это, вероятно, то, что вы ищете.

Answer 3

Я тоже не уверен, что понимаю ваш вопрос, но:

В DFS, когда вы находитесь на узле, вы делаете целевой тест. Если вы не достигли цели, вы переходите к крайнему левому дочернему элементу, проверяете его и т. Д. Предположим, что крайний левый дочерний элемент не является целью и является листом. Затем вы возвращаетесь к его родителю и переходите ко второму левому узлу, проверяете его и т. Д. Затем третий левый дочерний узел и т. Д.

Вы не делаете что-то вроде «отметьте всех детей, , затем переходите к крайнему левому ребенку», если вы об этом спрашиваете.

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