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

       

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



9. 5. 2.    Поиск пути в графе

Пусть 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 имеют следующий смысл:

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



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