Курсовая работа: Поиск оптимального пути в графе
Путь: ["остановка1","мi","остановкаQ",...,"мj"," остановка 2"]
Сумма_времени=Kyes
Так же результата решения может и не быть: “no", если нет таких пути, остановок, введённых в запрос пользователем. Поэтому требование к входным данным такое: остановки, введённые в запрос должны быть базе фактов.
Если пользователь захотел добавить ветвь, то ему необходимо добавить в базу фактов ещё один или два, один из которых обеспечивает не направленность ветки в формате:
участок (остановка1, х1, у1, остановка2, х2, у2, номер_маршрутки, время).
(участок (остановка2, х2, у2, остановка1, х1, у1, номер_маршрутки, время)) Для закрытии какой-нибудь линии необходимо сделать обратное -.
Для добавления новой остановки между двумя соединенными остановками надо отредактировать один факта и добавить новый и плюс два факта, описывающие обратные участки для всё той же не направленности веток и графа в целом:
участок (остановка1, х1, у1, остановкаNew, хN, уN, номер_маршрутки, время1).
NEW-участок (остановкаNew, хN, уN, остановка2, х2, у2, номер_маршрутки, время2).
(участок (остановкаNew, хN, уN, остановка1ew, х1, у1, номер_маршрутки, время1).
NEW-участок (остановка2, х2, у2, остановкаNew, хN, уN, номер_маршрутки, время2))
Для добавления новой остановки, не врезающейся в ветвь надо добавить факты, описывающие соединения этой остановки с другими.
3. Руководство программиста
 |
3.1 Функциональная схема
Логические модели. Блок-схемы алгоритма.
а) принадлежит (Х, [Х|_]).
принадлежит (Х, [_|Хвост]): - принадлежит (Х, Хвост).
см. Братко И. Программирование на языке Пролог для искусственного интеллекта.
б) max (X,Y,X): - X>Y.
max (X,Y,Y): - X<=Y.
min (X,Y,X): - X<Y.
min (X,Y,Y): - X>=Y.
см. Братко И. Программирование на языке Пролог для искусственного интеллекта.
в) мин_сумма1 (_, []).
мин_сумма1 (М, [Х|Список]): - М<=Х, мин_сумма1 (М, Список).
мин_сумма2 (М, [Х|Список]): - мин_сумма1 (М, Список),!;
мин_сумма2 (М, Список).
В данном случае конкретизирован Cписок, необходимо найти М. Присваиваем М значение первого элемента и сравниваем с остольными элементами списка. Если М является минимумом, то искомое значение найдено, отсечение не позволяет перейти ко второму условию этого правила. Иначе сравниваем с значения второго элемента списка с оставшимися. Цикл прекращается, если очередное значение М является минимальным.
г) коридор (Нач, Кон, СписокХ, СписокУ): -
участок (Нач, Х1, У1,_,_,_,_,_),!,
участок (_,_,_, Кон, Х2, У2,_,_),!,