Программирование на языке ПРОЛОГ для искуственного интеллекта




Поиск пути в графе


Пусть G - граф, а А и Z - две его вершины. Определим отношение

        путь( А, Z, G, Р)

где Р - ациклический путь между А и Z в графе G. Если G - граф, показанный в левой части рис. 9.18, то верно:

        путь( a, d, G, [a, b, d] )
        путь( а, d, G, [a, b, c, d] )

Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:

line();

Для того, чтобы найти ациклический путь Р между А и Z в графе G, необходимо:

Если А = Z , то положить Р = [А], иначе найти ациклический путь Р1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из Р1.

line();

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

        путь1( А, Р1, G, Р)

Аргументы в соответствии с рис. 9.19 имеют следующий смысл:

  • А - некоторая вершина,

fig9_19.gif (1262 bytes)

Pис. 9. 19.  Отношение путь1:   Путь - это путь между А и Z, в своей
заключительной части он перекрывается с Путь1.

  • G - граф,
  • P1 - путь в G,
  • Р - ациклический путь в G, идущий из А в начальную вершину пути Р1, а затем - вдоль пути Р1 вплоть до его конца.

Между путь и путь1 имеется следующее соотношение:

        путь( А, Z, G, Р) :- путь1( А, [Z], G, Р).

На рис. 9.19 показана идея рекурсивного определения отношения путь1. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути Р. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что

(1)        Y - вершина, смежная с X,



Содержание  Назад  Вперед