Программа поиска
Рисунок 11. 11. Программа поиска в ширину более эффективная, чем
программа Рисунок 11.10. Усовершенствование основано на разностном
представлении списка путей-кандидатов.
(1) Начинаем с начального множества кандидатов:
[ [а] ]
(2) Порождаем продолжения пути [а]:
[ [b, а], [с, а] ]
(Обратите внимание, что пути записаны в обратном порядке.)
(3) Удаляем первый путь из множества кандидатов и порождаем его продолжения:
[ [d, b, a], [e, b, а] ]
Добавляем список продолжений в конец списка кандидатов:
[ [с, а], [d, b, a], [e, b, а] ]
(4) Удаляем [с, а], а затем добавляем все его продолжения в конец множества кандидатов. Получаем:
[ [d, b, a], [e, b, а], [f, c, a], [g, c, a] ]
Далее, после того, как пути [d, b, a] и [e, b, а] будут продолжены, измененный список кандидатов примет вид
[[f, c, a], [g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a]]
В этот момент обнаруживается путь [f, c, a], содержащий целевую вершину f. Этот путь выдается в качестве решения.
Программа, порождающая этот процесс, показана на Рисунок 11.10. В этой программе все продолжения пути на один шаг генерируются встроенной процедурой bagof. Кроме того, делается проверка, предотвращающая порождение циклических путей. Обратите внимание на то, что в случае, когда путь продолжить невозможно, и цель bagof терпит неудачу, обеспечивается альтернативный запуск процедуры вширину. Процедуры принадлежит и конк реализуют отношения принадлежности списку и конкатенации списков соответственно.
Недостатком этой программы является неэффективность операции конк. Положение можно исправить, применив разностное представление списков (см. гл. 8). Тогда множество путей-кандидатов будет представлено парой списков Пути и Z, записанной в виде
Пути-Z
При введении этого представления в программу Рисунок 11.10 ее можно постепенно преобразовать в программу, показанную на Рисунок 11.11. Оставим это преобразование читателю в качестве упражнения.
