3. Типы поиска, использующего дерево решений

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

3.1. Поиск по глубине

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

Рис. П.4а. Дерево поиска по глубине.

Рис. П.4б. Дерево поиска по ширине, Задача решена.

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

3.2. Поиск по ширине

При поиске по ширине ветвление происходит от уровня к уровню, так что если на уровне 1 начальная задача разбивается на подзадачи то каждая из этих подзадач исследуется раньше, чем задачи уровня 2. Задачи уровня 1, которые не могут быть разрешены, разбиваются на подзадачи уровня 2, и опять все они исследуются до исследования какой-либо подзадачи, могущей возникнуть на уровне 3, и т. д. Вид дерева решений при этом типе поиска показан на рис.