Начинаясь в а поиск вглубину заканчивается бесконечным циклом между d и h a b d h d h d



Рисунок 11. 5.  Начинаясь в а, поиск вглубину заканчивается
бесконечным циклом между  d  и  h:   a, b, d, h, d, h, d ... .


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

        вглубину( Путь, Верш, Решение)

Как видно из Рисунок 11.6, Верш - это состояние, из которого необходимо найти путь до цели; Путь - путь (список вершин) между стартовой вершиной и Верш; Решение - Путь, продолженный до целевой вершины.



Содержание раздела