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




Поиск пути в графе - часть 4


                Ст2 is Ст1 + СтXY,
                путь1( А, [ X, Y | Путь1], Ст2, Граф, Путь, Ст).

line();

Рис. 9. 21.  Поиск пути в графе: Путь - путь между А и Z в графе Граф стоимостью Ст.

Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами Верш1, Верш2 графа Граф, задав цели

        путь( Bepш1, Верш2, Граф, МинПуть, МинСт),
        not ( путь( Верш1, Верш2, Граф, _, Ст), Ст<МинСт )

Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели

        путь( _, _, Граф, МаксПуть, МаксСт),
        not ( путь( _, _, Граф, _, Ст), Ст > МаксСт)

Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.




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