Функциональная схема программы
Рис. 1
Интерфейс пользователя
Открываем Visual Prolog в самой программе находим закладку “Open”, через неё раскрываем файл маршрут.pro После запуска маршрут.pro появится окно с вопросом: ‘Введите начальную станцию =a’ Указываете начальный пункт(например, «a»). Нажимаете «Enter» ‘ Введите конечную станцию = g’ Указываете конечный пункт назначения(«g»). Нажимаете «Enter» ‘Сколько вы хотите ввести количество промежуточных станций=2’ Указываете промежуточные станции с и j. Нажимаете «Enter»
После обработки входных данных появится ‘Путь: ["a","s","n","c","j","f","g"] Число остановок: 7 yes’ «Путь» показывает оптимальный маршрут с наименьшим количеством пересадок. Если на экране появится надпись «no», значит неправильно введено название станции или невозможно найти оптимальный маршрут, не проезжая через какую-либо станцию дважды.
Руководство программиста Логические модели. Блок-схемы алгоритмов Описание станций линий метро линия(линия_1,[a,s,d,f,g]). линия(линия_2,[l,k,d,j,h]). линия(линия_3,[z,x,d,c,v]). линия(линия_4,[b,n,d,m,q]). линия(линия_5,[c,j,f,m,x,k,s,n,c]).
Далее определяеться принадлежность станции к линии. Т.е. станция принадлежит списку (линии), если она являеться головой этого списка; станция принадлежит списку, если она находиться в хвосте. принадлежит(Станция,[Станция|_]). принадлежит(Станция,[_|Хвост]):- принадлежит(Станция,Хвост).
Аналогично производиться проверка двух станций на соседство в списке. соседние(Станция1,Станция2,[Станция1,Станция2|_]). соседние(Станция1,Станция2,[_|Хвост]):- соседние(Станция1,Станция2,Хвост).
Ненаправленность графа обеспечивается в поиске смежных станций, т.е. находим ветвь Станция1, Станция2 или Станция2, Станция1. смежные_станции(Станция1,Станция2,Линия):- линия(Линия,Список),принадлежит(Станция1,Список), принадлежит(Станция2,Список), соседние(Станция1,Станция2,Список); линия(Линия,Список), принадлежит(Станция1,Список), принадлежит(Станция2,Список), соседние(Станция2,Станция1,Список). Пересадка с линии1 на линию 2 возможна, когда станция принадлежит обеим линиям. пересадка(Станция,Линия1,Линия2):- линия(Линия1,Список1), линия (Линия2, Список2), принадлежит(Станция,Список1),принадлежит(Станция,Список2), Линия1<>Линия2.
Осуществляем поиск возможного пути от начальной станции к конечной. маршрут(Станция,Станция,[Станция],1,Линия,_):- линия(Линия,Список),принадлежит(Станция,Список). % путь с пересадкой маршрут(Начало,Конец,[Начало,Начало2|Хвост],Остановки1,Линия,История):- линия(Линия,Список),линия(Новая_Линия,Новый_Список), принадлежит(Начало,Список),принадлежит(Начало2,Новый_Список), пересадка(Начало,Линия,Новая_Линия),Линия<>Новая_Линия, смежные_станции(Начало,Начало2,_), not(принадлежит(Начало2,История)), маршрут(Начало2,Конец,[Начало2|Хвост],Остановки2,Новая_Линия, [Начало2|История]), Остановки1=Остановки2+1. % путь без пересадки маршрут(Начало,Конец,[Начало,Начало2|Хвост],Остановки1, Линия, История):- линия(Линия,Список),линия(Новая_Линия,Новый_Список), принадлежит(Начало,Список),принадлежит(Начало2,Новый_Список), Линия=Новая_Линия,смежные_станции(Начало,Начало2,_), not(принадлежит(Начало2,История)), маршрут(Начало2, Конец, [Начало2|Хвост], Остановки2, Линия, [Начало2|История]), Остановки1 = Остановки2 + 1. /* осуществляется поиск пути через заданную остановку*/ через_станцию(Начало,Конец,Пром,Ost,List):-маршрут(Начало,Конец,List,Ost,_,[Начало]),принадлежит(Пром,List).
Тестовый пример
Из схемы метро(см.приложение А) выбираем начальную и конечную станции, а так же вводим промежуточные через которые нам надо проехать.Запускаем программу. Вводим соответствующие названия станций Например: нач-a,кон-g, пром-с,j. После обработки данных программа выводит на экран маршрут проезда, в виде списка станций, через которые следует ехать, и количество остановок в пути.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|