Выбор алгоритма для поиска оптимального пути движения в метро

DOMAINS
 
список=symbol*
список_списков=список*
 
PREDICATES
 
nondeterm путь(symbol,symbol,список,список)
nondeterm путь1(symbol,список,список,список)  
nondeterm принадлежит(symbol,symbol,список) %проверка на принадлежность ребра линии
nondeterm смежные(symbol,symbol,список) %проверка смежности станций
 
    nondeterm путь(symbol,symbol) 
    nondeterm поиск_в_ширину(список_списков,symbol,список)  
    nondeterm обращ(список,список)
    nondeterm обращ(список,список,список)
    nondeterm конк(список_списков,список_списков,список_списков).
    nondeterm принадлежит(symbol,список)
    nondeterm новый_узел(symbol,список,список)
 
nondeterm граф(список)
nondeterm линия(список)  
nondeterm станция(symbol,symbol) %обозначение станции и ее название
nondeterm станция_где_есть_пересадка(symbol,symbol,symbol,symbol).
nondeterm время_перегона(symbol,symbol,integer)
nondeterm время_пересадки(symbol,symbol,integer)
 
nondeterm можно_пересесть(symbol,symbol,symbol)
nondeterm время_перехода(symbol,symbol,integer)
nondeterm смежная_пара(symbol,symbol,symbol,symbol) %проверка пересечения линий
 
nondeterm перегон(symbol,symbol,integer) %расстояние м/д А и В (направленные проезд)
nondeterm пересадка(symbol,symbol,symbol,symbol,integer,integer,список)
    
nondeterm время_пересадки_в_начале(список,integer,integer,symbol,symbol) 
nondeterm время_пересадок(список,integer,integer,integer,symbol)
nondeterm время_перегонов(список,integer,integer)
nondeterm время_пути(список,integer,integer,integer,integer,symbol,symbol)
 
%nondeterm сортировать(список_списков,список_списков,symbol,symbol)
%nondeterm swap(список_списков,список_списков,symbol,symbol)
    
nondeterm получить_путь(symbol,symbol,список,integer,integer,integer,symbol,symbol)
%nondeterm найти_оптим_путь(symbol,symbol,integer)
nondeterm оптимальный_путь(symbol,symbol)
%nondeterm вывод(список_списков,integer,integer,symbol,symbol)
nondeterm вывод(список_списков,integer,symbol,symbol)
%Предикаты для преобразования пути    
nondeterm удалить_пары_начало(список,список,symbol,symbol)
nondeterm удалить_пары_дальше(список,список_списков,integer,symbol)
 
nondeterm максимальное_количество_пересадок(integer)
nondeterm go
 
 
CLAUSES
%---------------------------------------------------------------------------------------------------
%Блок входных данных
%---------------------------------------------------------------------
%Система метро
%---------------------------------------------------------------------
%Граф
граф([а1,а2,а2,а3,а3,а4,а4,а5,а5,а6,а6,а7,а7,а8,а8,а9,а9,а10,а10,а11,а11,а12,а12,а13,а13,а14,а14,а15,а15,а16,а16,а17,а17,а18,а18,а19,
б1,б2,б2,б3,б3,б4,б4,б5,б5,б6,б6,б7,б7,б8,б8,б9,б9,б10,б10,а10,а10,б12,б12,б13,б13,б14,б14,б15,б15,б16,б16,б17,б17,б18,б18,б19,б19,б20,
в1,в2,в2,в3,в3,в4,в4,в5,в5,в6,в6,в7,в7,в8,в8,в9,в9,в10,в10,в11,в11,а9,а9,а10,а10,в14,в14,в15,в15,в16,в16,в17,в17,в18,в18,в19,в19,в20,в20,в21,
в7,г2,г2,г3,г3,г4,г4,г5,г5,г6,г6,г7,г7,в10,в10,г9,г9,г10,г10,а9,
д1,б9,б9,д3,д3,в14,в14,а14,а14,д6,д6,д7,д7,б14,б14,д9,д9,в10,в10,а7,а7,д12,д12,д1,
е1,е2,е2,е3,е3,е4,е4,е5,е5,е6,е6,е7,е7,е8,е8,е9,е9,е10,е10,е11,е11,д12,д12,б10,б10,е14,е14,а12,а12,е16,е16,д6,д6,е18,е18,е19,е19,е20,е20,е21,е21,е22,е22,е23,е23,е24,
ё1,ё2,ё2,ё3,ё3,ё4,ё4,ё5,ё5,ё6,ё6,д3,д3,е14,е14,а11,а11,б12,б12,д9,д9,ё12,ё12,ё13,ё13,ё14,ё14,ё15,ё15,ё16,ё16,ё17,ё17,ё18,ё18,ё19,
б10,д3,д3,ж3,ж3,ж4,ж4,ж5,ж5,ж6,ж6,ж7,
з1,з2,з2,з3,з3,з4,з4,з5,з5,з6,з6,з7,з7,з8,з8,з9,з9,з10,з10,з11,з11,д1,д1,з13,з13,а9,а9,б12,б12,з16,з16,д7,д7,з18,з18,з19,з19,з20,з20,з21,з21,з22,з22,з23,з23,з24,з24,з25,
и1,и2,и2,и3,и3,и4,и4,и5,и5,и6,и6,и7,и7,ё6,ё6,ж3,ж3,в14,в14,а12,а12,з16,з16,и13,и13,и14,
з7,й2,й2,б6,
к1,к2,к2,к3,к3,к4,к4,з1]).
 
%Линии--------------------------------------------------------------------------------------------
%Сокольническая
линия([а1,а2,а2,а3,а3,а4,а4,а5,а5,а6,а6,а7,а7,а8,а8,а9,а9,а10,а10,а11,а11,а12,а12,а13,а13,а14,а14,а15,а15,а16,а16,а17,а17,а18,а18,а19]).
%Замоскворецкая
линия([б1,б2,б2,б3,б3,б4,б4,б5,б5,б6,б6,б7,б7,б8,б8,б9,б9,б10,б10,а10,а10,б12,б12,б13,б13,б14,б14,б15,б15,б16,б16,б17,б17,б18,б18,б19,б19,б20]).
%Арбатско-Покровская
линия([в1,в2,в2,в3,в3,в4,в4,в5,в5,в6,в6,в7,в7,в8,в8,в9,в9,в10,в10,в11,в11,а9,а9,а10,а10,в14,в14,в15,в15,в16,в16,в17,в17,в18,в18,в19,в19,в20,в20,в21]).
%Филевская
линия([в7,г2,г2,г3,г3,г4,г4,г5,г5,г6,г6,г7,г7,в10,в10,г9,г9,г10,г10,а9]).
%Кольцевая
линия([д1,б9,б9,д3,д3,в14,в14,а14,а14,д6,д6,д7,д7,б14,б14,д9,д9,в10,в10,а7,а7,д12,д12,д1]).
%Калужско-Рижская
линия([е1,е2,е2,е3,е3,е4,е4,е5,е5,е6,е6,е7,е7,е8,е8,е9,е9,е10,е10,е11,е11,д12,д12,б10,б10,е14,е14,а12,а12,е16,е16,д6,д6,е18,е18,е19,е19,е20,е20,е21,е21,е22,е22,е23,е23,е24]).
%Таганско-Краснопресненская
линия([ё1,ё2,ё2,ё3,ё3,ё4,ё4,ё5,ё5,ё6,ё6,д3,д3,е14,е14,а11,а11,б12,б12,д9,д9,ё12,ё12,ё13,ё13,ё14,ё14,ё15,ё15,ё16,ё16,ё17,ё17,ё18,ё18,ё19]).
%Калининская
линия([б10,д3,д3,ж3,ж3,ж4,ж4,ж5,ж5,ж6,ж6,ж7]).
%Серпуховско-Тимирязевская
линия([з1,з2,з2,з3,з3,з4,з4,з5,з5,з6,з6,з7,з7,з8,з8,з9,з9,з10,з10,з11,з11,д1,д1,з13,з13,а9,а9,б12,б12,з16,з16,д7,д7,з18,з18,з19,з19,з20,з20,з21,з21,з22,з22,з23,з23,з24,з24,з25]).
%Люблинская
линия([и1,и2,и2,и3,и3,и4,и4,и5,и5,и6,и6,и7,и7,ё6,ё6,ж3,ж3,в14,в14,а12,а12,з16,з16,и13,и13,и14]).
%Каховская
линия([з7,й2,й2,б6]).
%Бутовсквя
линия([к1,к2,к2,к3,к3,к4,к4,з1]).
 
%Станции----------------------------------------------------------------------------------------------
%Линия метро Сокольническая
станция(а1,юго_западная).
станция(а2,проспект_вернадского).
станция(а3,университет).
станция(а4,воробьевы_горы).
станция(а5,спортивная).
станция(а6,фрунзенская).
станция(а7,парк_культуры_сокольнической_линии).
станция(а8,кропоткинская).
станция(а9,библиотека_имени_ленина).
станция(а10,охотный_ряд).
станция(а11,лубянка).
станция(а12,чистые_пруды).
станция(а13,красные_ворота).
станция(а14,комсомольская_сокольнической_линии).
станция(а15,красносельская).
станция(а16,сокольники).
станция(а17,преображенская_площадь).
станция(а18,черкизовская).
станция(а19,улица_подбельского).
 
%Линия метро Замоскворецкая
станция(б1,красногвардейская).
станция(б2,домодедовская).
станция(б3,орехово).
станция(б4,царицыно).
станция(б5,кантемировская).
станция(б6,каширская_замоскворецкой_линии).
станция(б7,коломенская).
станция(б8,автозаводская).
станция(б9,павелецкая_замоскворецкой_линии).
станция(б10,новокузнецкая).
станция(а10,театральная).
станция(б12,тверская).
станция(б13,маяковская).
станция(б14,белорусская_замоскворецкой_линии).
станция(б15,динамо).
станция(б16,аэропорт).
станция(б17,сокол).
станция(б18,войковская).
станция(б19,водный_стадион).
станция(б20,речной_вокзал).
 
%Линия метро Арбатско-Покровская
станция(в1,митино).
станция(в2,волоколамская).
станция(в3,мякинино).
станция(в4,строгино).
станция(в5,крылатское).
станция(в6,молодежная).
станция(в7,кунцевская_арбатско_покровской_линии).
станция(в8,славянский_бульвар).
станция(в9,парк_победы).
станция(в10,киевская_арбатско_покровской_линии).
станция(в11,смоленская).
станция(а9,арбатская_арбатско_покровской_линии).
станция(а10,площадь_революции).
станция(в14,курская_арбатско_покровской_линии).
станция(в15,бауманская).
станция(в16,электрозаводская).
станция(в17,семеновская).
станция(в18,партизанская).
станция(в19,измайловская).
станция(в20,первомайская).
станция(в21,щелковская).
 
%Линия метро Филевская
станция(в7,кунцевская_филевской_линии).
станция(г2,пионерская).
станция(г3,филёвский_парк).
станция(г4,багратионовская).
станция(г5,фили).
станция(г6,кутузовская).
станция(г7,студенческая).
станция(в10,киевская_филевской_линии).
станция(г9,смоленская).
станция(г10,арбатская_филевской_линии).
станция(а9,александровский_сад).
 
%Линия метро Кольцевая
станция(д1,добрынинская_кольцевой_линии).
станция(б9,павелецкая_кольцевой_линии).
станция(д3,таганская_кольцевой_линии).
станция(в14,курская_кольцевой_линии).
станция(а14,комсомольская_кольцевой_линии).
станция(д6,проспект_мира_кольцевой_линии).
станция(д7,новослободская_кольцевой_линии).
станция(б14,белорусская_кольцевой_линии).
станция(д9,краснопресненская).
станция(в10,киевская_кольцевой_линии).
станция(а7,парк_культуры_кольцевой_линии).
станция(д12,октябрьская_кольцевой_линии).
 
%Линия метро Калужско-Рижская
станция(е1,битцевский_парк).
станция(е2,ясенево).
станция(е3,теплый_стан).
станция(е4,коньково).
станция(е5,беляево).
станция(е6,калужская).
станция(е7,новые_черемушки).
станция(е8,профсоюзная).
станция(е9,академическая).
станция(е10,ленинский_проспект).
станция(е11,шаболовская).
станция(д12,октябрьская_калужско_рижской_линии).
станция(б10,третьяковская_калужско_рижской_линии).
станция(е14,китай_город_калужско_рижской_линии).
станция(а12,тургеневская).
станция(е16,сухаревская).
станция(д6,проспект_мира_калужско_рижской_линии).
станция(е18,рижская).
станция(е19,алексеевская).
станция(е20,вднх).
станция(е21,ботанический_сад).
станция(е22,свиблово).
станция(е23,бабушкинская).
станция(е24,медведково).
 
%Линия метро Таганско-Краснопресненская
станция(ё1,выхино).
станция(ё2,рязанский_проспект).
станция(ё3,кузьминки).
станция(ё4,текстильщики).
станция(ё5,волгоградский_проспект).
станция(ё6,пролетарская).
станция(д3,таганская_таганско_краснопресненской_линии).
станция(е14,китай_город_таганско_краснопресненской_линии).
станция(а11,кузнецкий_мост).
станция(б12,пушкинская).
станция(д9,баррикадная).
станция(ё12,улица_1905_года).
станция(ё13,беговая).
станция(ё14,полежаевская).
станция(ё15,октябрьское_поле).
станция(ё16,щукинская).
станция(ё17,тушинская).
станция(ё18,сходненская).
станция(ё19,планетарная).
 
%Линия метро Калининская
станция(б10,третьяковская_калининской_линии).
станция(д3,марксистская).
станция(ж3,площадь_ильича).
станция(ж4,авиамоторная).
станция(ж5,шоссе_энтузиастов).
станция(ж6,перово).
станция(ж7,новогиреево).
 
%Линия метро Серпуховско-Тимирязевская
станция(з1,бульвар_дмитрия_донского).
станция(з2,аннино).
станция(з3,улица_академика_янгеля).
станция(з4,пражское).
станция(з5,южная).
станция(з6,чертановская).
станция(з7,севастопольская).
станция(з8,нахимовский_проспект).
станция(з9,нагорная).
станция(з10,нагатинская).
станция(з11,тульская).
станция(д1,серпуховская).
станция(з13,полянка).
станция(а9,боровицкая).
станция(б12,чеховская).
станция(з16,цветной_бульвар).
станция(д7,менделеевская).
станция(з18,савеловская).
станция(з19,дмитровская).
станция(з20,тимирязевская).
станция(з21,петровско_разумовская).
станция(з22,владыкино).
станция(з23,отрадное).
станция(з24,бибирево).
станция(з25,алтуфьево).
 
%Линия метро Люблинская
станция(и1,марьино).
станция(и2,братиславская).
станция(и3,люблино).
станция(и4,волжская).
станция(и5,печатники).
станция(и6,кожуховская).
станция(и7,дубровка).
станция(ё6,крестьянская_застава).
станция(ж3,римская).
станция(в14,чкаловская).
станция(а12,сретенский_бульвар).
станция(з16,трубная).
станция(и13,достоевская).
станция(и14,марьина_роща).
 
%Линия метро Каховская
станция(з7,каховская).
станция(й2,варшавская).
станция(б6,каширская_каховской_линии).
 
%Линия метро Бутовская
станция(к1,бунинская_аллея).
станция(к2,улица_горчакова).
станция(к3,бульвар_адмирала_ушакова).
станция(к4,улица_скобелевская).
станция(з1,бульвар_дмитрия_донского).
 
%Станции,где есть пересадка------------------------------------------------------------------
станция_где_есть_пересадка(а9,библиотека_имени_ленина,а8,а10).
станция_где_есть_пересадка(а9,арбатская_арбатско_покровской_линии,в11,а10).%заком
станция_где_есть_пересадка(а9,александровский_сад,г10,нет).
станция_где_есть_пересадка(а9,боровицкая,к13,б12).
станция_где_есть_пересадка(в10,киевская_арбатско_покровской_линии,в9,в11). %заком
станция_где_есть_пересадка(в10,киевская_филевской_линии,г7,г9).
станция_где_есть_пересадка(в10,киевская_кольцевой_линии,д9,а7).
станция_где_есть_пересадка(б12,тверская,а10,б13).
станция_где_есть_пересадка(б12,пушкинская,а11,д9).
станция_где_есть_пересадка(б12,чеховская,а9,з16).
станция_где_есть_пересадка(а10,охотный_ряд,а9,а11).
станция_где_есть_пересадка(а10,театральная,б10,б12).
станция_где_есть_пересадка(а10,площадь_революции,а9,б14).%заком
станция_где_есть_пересадка(б10,новокузнецкая,б9,а10).
станция_где_есть_пересадка(б10,третьяковская_калужско_рижской_линии,д12,е14).
станция_где_есть_пересадка(б10,третьяковская_калининской_линии,нет,д3).
станция_где_есть_пересадка(а12,чистые_пруды,а11,а13).
станция_где_есть_пересадка(а12,тургеневская,е14,е16).
станция_где_есть_пересадка(а12,сретенский_бульвар,в14,з16).
станция_где_есть_пересадка(д3,таганская_кольцевой_линии,б9,в14).
станция_где_есть_пересадка(д3,таганская_таганско_краснопресненской_линии,ё6,е14).
станция_где_есть_пересадка(д3,марксистская,б10,ж3).
станция_где_есть_пересадка(в14,курская_арбатско_покровской_линии,а10,в15).%заком
станция_где_есть_пересадка(в14,курская_кольцевой_линии,д3,а14).
станция_где_есть_пересадка(в14,чкаловская,ж3,а12).
станция_где_есть_пересадка(в7,кунцевская_арбатско_покровской_линии,в6,в8).%заком
станция_где_есть_пересадка(в7,кунцевская_филевской_линии,нет,г2).%заком
станция_где_есть_пересадка(д9,краснопресненская,б14,в10).
станция_где_есть_пересадка(д9,баррикадная,б12,ё12).
станция_где_есть_пересадка(б14,белорусская_замоскворецкой_линии,б13,б15).
станция_где_есть_пересадка(б14,белорусская_кольцевой_линии,д7,д9).
станция_где_есть_пересадка(а7,парк_культуры_сокольнической_линии,а6,а8).
станция_где_есть_пересадка(а7,парк_культуры_кольцевой_линии,в10,д12).
станция_где_есть_пересадка(д7,новослободская,д6,б14).
станция_где_есть_пересадка(д7,менделеевская,з16,з18).
станция_где_есть_пересадка(д12,октябрьская_калужско_рижской_линии,е11,б10).
станция_где_есть_пересадка(д12,октябрьская_кольцевой_линии,а7,д1).
станция_где_есть_пересадка(з16,цветной_бульвар,б12,д7).
станция_где_есть_пересадка(з16,трубная,а12,и13).
станция_где_есть_пересадка(а11,лубянка,а10,а12).
станция_где_есть_пересадка(а11,кузнецкий_мост,е14,б12).
станция_где_есть_пересадка(д1,добрынинская,д12,б9).
станция_где_есть_пересадка(д1,серпуховская,з11,з13).
станция_где_есть_пересадка(з7,каховская,нет,й2).               
станция_где_есть_пересадка(з7,севастопольская,з6,з8).
станция_где_есть_пересадка(з1,бульвар_дмитрия_донского,нет,з2).
станция_где_есть_пересадка(з1,улица_старокачаловская,к4,нет).
станция_где_есть_пересадка(д6,проспект_мира_кольцевой_линии,а14,д7).
станция_где_есть_пересадка(д6,проспект_мира_калужско_рижской_линии,е16,е18).
станция_где_есть_пересадка(е14,китай_город_калужско_рижской_линии,б10,а12).
станция_где_есть_пересадка(е14,китай_город_таганско_краснопресненской_линии,д2,а11).
станция_где_есть_пересадка(б9,павелецкая_замоскворецкой_линии,б8,б10).
станция_где_есть_пересадка(б9,павелецкая_кольцевой_линии,д1,д3).
станция_где_есть_пересадка(а14,комсомольская_сокольнической_линии,а13,а15).
станция_где_есть_пересадка(а14,комсомольская_кольцевой_линии,в14,д6).
станция_где_есть_пересадка(б6,каширская_замоскворецкой_линии,б5,б7).
станция_где_есть_пересадка(б6,каширская_каховской_линии,й2,нет).
станция_где_есть_пересадка(ж3,площадь_ильича,д3,ж4).
станция_где_есть_пересадка(ж3,римская,ё6,в14).
станция_где_есть_пересадка(ё6,пролетарская,ё5,д3).
станция_где_есть_пересадка(ё6,крестьянская_застава,и7,ж3).
 
%Время пересадок-------------------------------------------------------------------------------   
время_пересадки(александровский_сад,библиотека_имени_ленина,2).
время_пересадки(библиотека_имени_ленина,боровицкая,4).
время_пересадки(боровицкая,арбатская_арбатско_покровской_линии,3).%заком
время_пересадки(арбатская_арбатско_покровской_линии,александровский_сад,1).%заком
время_пересадки(александровский_сад,боровицкая,1).
время_пересадки(арбатская_арбатско_покровской_линии,библиотека_имени_ленина,5).%заком
время_пересадки(киевская_арбатско_покровской_линии,киевская_филевской_линии,3).%заком
время_пересадки(киевская_филевской_линии,киевская_кольцевой_линии,2).
время_пересадки(киевская_кольцевой_линии,киевская_арбатско_покровской_линии,3).%заком
время_пересадки(тверская,пушкинская,4).
время_пересадки(пушкинская,чеховская,2).
время_пересадки(чеховская,тверская,4).
время_пересадки(охотный_ряд,театральная,2).
время_пересадки(театральная,площадь_революции,1).%заком
время_пересадки(площадь_революции,охотный_ряд,3).%заком
время_пересадки(новокузнецкая,третьяковская_калужско_рижской_линии,4).
время_пересадки(третьяковская_калужско_рижской_линии,третьяковская_калининской_линии,3).
время_пересадки(третьяковская_калининской_линии,новокузнецкая,2).
время_пересадки(чистые_пруды,тургеневская,3).
время_пересадки(тургеневская,сретенский_бульвар,1).
время_пересадки(сретенский_бульвар,чистые_пруды,3).
время_пересадки(таганская_кольцевой_линии,таганская_таганско_краснопресненской_линии,3).
время_пересадки(таганская_таганско_краснопресненской_линии,марксистская,2).
время_пересадки(марксистская,таганская_кольцевой_линии,1).
время_пересадки(курская_арбатско_покровской_линии,курская_кольцевой_линии,4).%заком
время_пересадки(курская_кольцевой_линии,чкаловская,4).
время_пересадки(чкаловская,курская_арбатско_покровской_линии,1).%заком
время_пересадки(кунцевская_арбатско_покровской_линии,кунцевская_филевской_линии,1).%заком
время_пересадки(краснопресненская,баррикадная,1).
время_пересадки(белорусская_замоскворецкой_линии,белорусская_кольцевой_линии,3).
время_пересадки(парк_культуры_сокольнической_линии,парк_культуры_кольцевой_линии,5).
время_пересадки(новослободская,менделеевская,2).
время_пересадки(октябрьская_калужско_рижской_линии,октябрьская_кольцевой_линии,3).
время_пересадки(цветной_бульвар,трубная,4).
время_пересадки(лубянка,кузнецкий_мост,2).
время_пересадки(добрынинская,серпуховская,3).
время_пересадки(каховская,севастопольская,2).
время_пересадки(бульвар_дмитрия_донского,улица_старокачаловская,1).
время_пересадки(проспект_мира_кольцевой_линии,проспект_мира_калужско_рижской_линии,4).
время_пересадки(китай_город_калужско_рижской_линии,китай_город_таганско_краснопресненской_линии,4).
время_пересадки(павелецкая_замоскворецкой_линии,павелецкая_кольцевой_линии,5).
время_пересадки(комсомольская_сокольнической_линии,комсомольская_кольцевой_линии,1).
время_пересадки(каширская_замоскворецкой_линии,каширская_каховской_линии,2).
время_пересадки(площадь_ильича,римская,4).
время_пересадки(пролетарская,крестьянская_застава,4).
 
%Время перегонов-------------------------------------------------------------------------------
%Линия метро Сокольническая
время_перегона(а1,а2,4).
время_перегона(а2,а3,4).
время_перегона(а3,а4,3).
время_перегона(а4,а5,4).
время_перегона(а5,а6,3).
время_перегона(а6,а7,4).
время_перегона(а7,а8,3).
время_перегона(а8,а9,3).
время_перегона(а9,а10,3).
время_перегона(а10,а11,3).
время_перегона(а11,а12,3).
время_перегона(а12,а13,3).
время_перегона(а13,а14,3).
время_перегона(а14,а15,3).
время_перегона(а15,а16,3).
время_перегона(а16,а17,4).
время_перегона(а17,а18,5).
время_перегона(а18,а19,4).
 
%Линия метро Замоскворецкая
время_перегона(б1,б2,4).
время_перегона(б2,б3,4).
время_перегона(б3,б4,6).
время_перегона(б4,б5,5).
время_перегона(б5,б6,5).
время_перегона(б6,б7,6).
время_перегона(б7,б8,6).
время_перегона(б8,б9,6).
время_перегона(б9,б10,3).
время_перегона(б10,а10,5).
время_перегона(а10,б12,3).
время_перегона(б12,б13,3).
время_перегона(б13,б14,2).
время_перегона(б14,б15,4).
время_перегона(б15,б16,4).
время_перегона(б16,б17,3).
время_перегона(б17,б18,4).
время_перегона(б18,б19,4).
время_перегона(б19,б20,4).
 
%Линия метро Арбатско-Покровская
время_перегона(в1,в2,3).
время_перегона(в2,в3,3).
время_перегона(в3,в4,4).
время_перегона(в4,в5,4).
время_перегона(в5,в6,4).
время_перегона(в6,в7,4).
время_перегона(в7,в8,4).
время_перегона(в8,в9,4).
время_перегона(в9,в10,4).
время_перегона(в10,в11,4).
время_перегона(в11,а9,4).
время_перегона(а9,а10,3).
время_перегона(а10,в14,5).
время_перегона(в14,в15,3).
время_перегона(в15,в16,4).
время_перегона(в16,в17,4).
время_перегона(в17,в18,4).
время_перегона(в18,в19,4).
время_перегона(в19,в20,3).
время_перегона(в20,в21,3).
 
%Линия метро Филевская
время_перегона(в7,г2,5).
время_перегона(г2,г3,5).
время_перегона(г3,г4,3).
время_перегона(г4,г5,3).
время_перегона(г5,г6,3).
время_перегона(г6,г7,3).
время_перегона(г7,в10,4).
время_перегона(в10,г9,4).
время_перегона(г9,г10,4).
время_перегона(г10,а9,4).
 
%Линия метро Кольцевая
время_перегона(д1,б9,3).
время_перегона(б9,д3,4).
время_перегона(д3,в14,4).
время_перегона(в14,а14,4).
время_перегона(а14,д6,4).
время_перегона(д6,д7,4).
время_перегона(д7,б14,4).
время_перегона(б14,д9,4).
время_перегона(д9,в10,4).
время_перегона(в10,а7,4).
время_перегона(а7,д12,3).
время_перегона(д12,д1,3).
 
%Линия метро Калужско-Рижская
время_перегона(е1,е2,4).
время_перегона(е2,е3,4).
время_перегона(е3,е4,5).
время_перегона(е4,е5,3).
время_перегона(е5,е6,4).
время_перегона(е6,е7,4).
время_перегона(е7,е8,3).
время_перегона(е8,е9,3).
время_перегона(е9,е10,4).
время_перегона(е10,е11,4).
время_перегона(е11,д12,3).
время_перегона(д12,б10,4).
время_перегона(б10,е14,4).
время_перегона(е14,а12,3).
время_перегона(а12,е16,3).
время_перегона(е16,д6,3).
время_перегона(д6,е18,4).
время_перегона(е18,е19,4).
время_перегона(е19,е20,4).
время_перегона(е20,е21,5).
время_перегона(е21,е22,4).
время_перегона(е22,е23,4).
время_перегона(е23,е24,5).
 
%Линия метро Таганско-Краснопресненская
время_перегона(ё1,ё2,4).
время_перегона(ё2,ё3,4).
время_перегона(ё3,ё4,4).
время_перегона(ё4,ё5,5).
время_перегона(ё5,ё6,4).
время_перегона(ё6,д3,4).
время_перегона(д3,е14,4).
время_перегона(е14,а11,3).
время_перегона(а11,б12,3).
время_перегона(б12,д9,4).
время_перегона(д9,ё12,3).
время_перегона(ё12,ё13,3).
время_перегона(ё13,ё14,4).
время_перегона(ё14,ё15,4).
время_перегона(ё15,ё16,4).
время_перегона(ё16,ё17,5).
время_перегона(ё17,ё18,4).
время_перегона(ё18,ё19,3).
 
%Линия метро Калининская
время_перегона(б10,д3,4).
время_перегона(д3,ж3,5).
время_перегона(ж3,ж4,4).
время_перегона(ж4,ж5,4).
время_перегона(ж5,ж6,4).
время_перегона(ж6,ж7,4).
 
%Линия метро Серпуховско-Тимирязевская
время_перегона(з1,з2,6).
время_перегона(з2,з3,5).
время_перегона(з3,з4,4).
время_перегона(з4,з5,3).
время_перегона(з5,з6,4).
время_перегона(з6,з7,4).
время_перегона(з7,з8,3).
время_перегона(з8,з9,3).
время_перегона(з9,з10,4).
время_перегона(з10,з11,5).
время_перегона(з11,д1,6).
время_перегона(д1,з13,5).
время_перегона(з13,а9,4).
время_перегона(а9,б12,4).
время_перегона(б12,з16,3).
время_перегона(з16,д7,4).
время_перегона(д7,з18,4).
время_перегона(з18,з19,4).
время_перегона(з19,з20,3).
время_перегона(з20,з21,4).
время_перегона(з21,з22,4).
время_перегона(з22,з23,4).
время_перегона(з23,з24,4).
время_перегона(з24,з25,5).
 
%Линия метро Люблинская
время_перегона(и1,и2,6).
время_перегона(и2,и3,5).
время_перегона(и3,и4,4).
время_перегона(и4,и5,4).
время_перегона(и5,и6,5).
время_перегона(и6,и7,4).
время_перегона(и7,ё6,3).
время_перегона(ё6,ж3,4).
время_перегона(ж3,в14,4).
время_перегона(в14,а12,6).
время_перегона(а12,з16,4).
время_перегона(з16,и13,4).
время_перегона(и13,и14,3).
 
%Линия метро Каховская
время_перегона(з7,й2,6).
время_перегона(й2,б6,7).
 
%Линия метро Бутовская
время_перегона(к1,к2,3).
время_перегона(к2,к3,3).
время_перегона(к3,к4,2).
время_перегона(к4,з1,4).
 
%Ограничение на максимальное количество пересадок
максимальное_количество_пересадок(3).
 
%---------------------------------------------------------------------------------------
%Определение времени пути
%---------------------------------------------------------------------------------------
пересадка(A,B,B,C,0,0,[Name]):-
        можно_пересесть(B,Name,A),not(смежная_пара(A,B,B,C)),!; %пересадки нет и проезжаем через одну из станций_где_есть_пересадка
        not(смежная_пара(A,B,B,C)),станция(B,Name).  %пересадки нет и проезжаем через обычную станцию
пересадка(A,B,B,C,Время,1,Name):-
        смежная_пара(A,B,B,C),           %есть пересадка
        можно_пересесть(B,Name1,A),       %откуда
        можно_пересесть(B,Name2,C),       %куда
        время_перехода(Name1,Name2,Время),    %время пересадки
        Name=[Name1,"пересадка -->",Name2].
перегон(A,B,Время):-                %время перегона между станциями
        время_перегона(A,B,Время);
        время_перегона(B,A,Время).
 
можно_пересесть(B,Name,X):-
        станция_где_есть_пересадка(B,Name,_,X);
        станция_где_есть_пересадка(B,Name,X,_).
 
время_перехода(Name1,Name2,Время):-
        время_пересадки(Name1,Name2,Время);
        время_пересадки(Name2,Name1,Время).
 
%Определяется время пересадки до посадки в поезд
время_пересадки_в_начале([],0,0,_,_).
время_пересадки_в_начале([_],Время,1,Stan1,Stan2):-
        время_перехода(Stan1,Stan2,Время).
время_пересадки_в_начале([A,B|_],Время,Count,Stan1,_):-
        можно_пересесть(A,Stan1,Z),
            пересадка(Z,A,A,B,Время,Count,_),!;
            Время=1,Count=0.
 
время_пересадок([],_,0,0,_).
время_пересадок([_],_,0,0,_).
время_пересадок([A,B],_,Time,0,Stan2):-
        можно_пересесть(B,Stan2,Z),
            пересадка(A,B,B,Z,Time,_,_),!;
            Time=0.
время_пересадок([A,B,B,C|Хвост],MaxCount,Время,Количество,Stan2):-
        время_пересадок([B,C|Хвост],MaxCount,Время1,Количество1,Stan2),
        пересадка(A,B,B,C,Time,Count,_),
        Количество=Количество1+Count,
        Количество<=MaxCount,
        Время=Время1+Time.
 
время_перегонов([],0,0).
время_перегонов([_],0,0).
время_перегонов([A,B|Хвост],Время,Количество):-
        время_перегонов(Хвост,Время1,Количество1),
        перегон(A,B,Time),
        Количество=Количество1+1,
        Время=Время1+Time.
 
время_пути(Путь,MaxCount,Время,Количество,Количество2,Stan1,Stan2):-
        время_пересадки_в_начале(Путь,Time,Count,Stan1,Stan2),
        время_пересадок(Путь,MaxCount,Время1,Количество1,Stan2),
        время_перегонов(Путь,Время2,Количество2),
        Время=Время1+Время2+Time,
        Количество=Количество1+Count.
        
смежная_пара(A,B,B,C):-
        линия(Линия),
        смежные(A,B,Линия),
        not(смежные(B,C,Линия)).
 
 
 
%---------------------------------------------------------------------------
%Поиск путей в графе
%-------------------------------------------------------------------------  
путь(A,Z,Граф,Путь):-               %правило1
        путь1(A,[Z],Граф,Путь),
        not(принадлежит(Z,_,Путь)).
 
путь1(A,[A],_,[A]):-!.              %факт1
        
путь1(A,[A|Путь1],_,Путь1).         %факт2              
 
путь1(A,[Z|Путь1],Граф,Путь):-          %правило 2
        смежные(Y,Z,Граф),
        not(принадлежит(Y,_,Путь1)),
        путь1(A,[Y,Y,Z|Путь1],Граф,Путь).               
    
смежные(Y,Z,Граф):-              %правило 3   
        принадлежит(Y,Z,Граф);
        принадлежит(Z,Y,Граф).
 
принадлежит(Y,Z,[Y,Z|_]).            %факт3
    
принадлежит(Y,Z,[_,_|Хвост]):-принадлежит(Y,Z,Хвост).%правило 4
 
%---------------------------------------------------------------------------    
%Сортировка списка путей
%---------------------------------------------------------------------------
%Применяется пузырьковая сортировка
/*сортировать(L,S,Stan1,Stan2):-swap(L,M,Stan1,Stan2),!,сортировать(M,S,Stan1,Stan2).
сортировать(L,L,_,_):-!.
swap([X,Y|R],[Y,X|R],Stan1,Stan2):-
        время_пути(Y,100,ВремяПути1,_,_,Stan1,Stan2),
        время_пути(X,100,ВремяПути2,_,_,Stan1,Stan2),
        ВремяПути1<ВремяПути2.
swap([X|R],[X|R1],Stan1,Stan2):-swap(R, R1,Stan1,Stan2).
*/
%---------------------------------------------------------------------------------
%Получение и вывод результатов
%---------------------------------------------------------------------------------
 
получить_путь(X,Y,Путь,Время_пути,Количество_пересадок,Количество_перегонов,Stan1,Stan2):-
        граф(Граф),
        путь(X,Y,Граф,Путь),
        максимальное_количество_пересадок(N),
    время_пути(Путь,N,Время_пути,Количество_пересадок,Количество_перегонов,Stan1,Stan2).
 
оптимальный_путь(Stan1,Stan2):-
        Stan1<>Stan2,станция(X,Stan1),станция(Y,Stan2),
        путь(X,Y),
        %findall(Путь,получить_путь(X,Y,Путь,_,_,_,Stan1,Stan2),Список_путей),
        %сортировать(Список_путей,Отсорт_Список_путей,Stan1,Stan2),
        %вывод(Отсорт_Список_путей,1,Stan1,Stan2),
        %вывод(Путь,1,Stan1,Stan2),
        go.
        
оптимальный_путь(Stan1,Stan2):- %Если введена одна и таже станция.
        Stan1=Stan2,
        write("Конечный пункт следования совпадает с начальным, поэтому поиск прекращен"),nl,nl,
        go.
        
        
        принадлежит(X,[X|_]).
        принадлежит(X,[_|Хвост]):- 
                принадлежит(X,Хвост).     
     
        обращ(X,Y):- 
                        обращ([],X,Y).  
        обращ(Y,[],Y).  
        обращ(X1,[Z|X2],Y):- 
                        обращ([Z|X1],X2,Y).
      
        конк([],L,L).
        конк([X|L1],L2,[X|L3]) :- 
                        конк(L1,L2,L3).
 
        путь(Старт,Z) :- 
                поиск_в_ширину([[Старт]],Z,Решение),
                обращ(Решение,X),
                %вывод([X],1,Старт,Z).
                write("Поиск в ширину : ",X,"\n").%,fail.
        путь(_,_).
 
        поиск_в_ширину([[Узел|Путь]|_],Узел,[Узел|Путь]).
        поиск_в_ширину([[B|Путь]|Paths],Z,Решение) :- 
                findall(S,новый_узел(B,S,Путь),NewPaths),
                конк(Paths,NewPaths,Paths1),!, 
                поиск_в_ширину(Paths1,Z,Решение);
                поиск_в_ширину(Paths,Z,Решение).  
 
        новый_узел(B,S,Путь) :-
            граф(Граф),
                смежные(B,B1,Граф), 
                not(принадлежит(B1,[B|Путь])), 
                S=[B1,B|Путь].
                
           
           
                    
 
вывод([],_,_,_).
вывод([X|_],_,Stan1,Stan2):-
        время_пути(X,100,Время_пути,Количество_пересадок,Количество_перегонов,Stan1,Stan2),
        удалить_пары_начало(X,Start,Stan1,Stan2),
        удалить_пары_дальше(X,P,Count,Stan2),
        Количество_пересадок1=Количество_пересадок+Count,
        P1=[Start|P],       
    write("Путь =",P1,"\n  Время пути: ",Время_пути," минут","\n  Пересадок: ",Количество_пересадок1,"\n  Перегонов: ",Количество_перегонов,"\n\n").
 
удалить_пары_начало([],[],_,_).
удалить_пары_начало([_],Start,Stan1,Stan2):-
            Start=[Stan1,"пересадка -->",Stan2].
удалить_пары_начало([X,Y|_],Start,Stan1,_):-
            можно_пересесть(X,Stan1,Z),
            пересадка(Z,X,X,Y,_,_,Start),!;
            станция(X,Start1),Start=[Start1].
 
удалить_пары_дальше([],[],0,_).
удалить_пары_дальше([_],[],0,_).
удалить_пары_дальше([X,Y],[Название],Count,Stan2):-
            можно_пересесть(Y,Stan2,Z),
            пересадка(X,Y,Y,Z,_,Count,Название),!;
            станция(Y,Название1),Название=[Название1],Count=0.
удалить_пары_дальше([X,Y,Y,Z|Хвост],[Название|Хвост1],Count,Stan2):-
        пересадка(X,Y,Y,Z,_,_,Название),
        удалить_пары_дальше([Y,Z|Хвост],Хвост1,Count,Stan2).
 
go:-
        write("Программа определения оптимального маршрута движения в метро"),nl,
        write("Для выхода нажмите Esc"),nl,
        write("Начальная станция: "),readln(Stan1),
        write("Конечная станция: "),readln(Stan2),
        write("---------------------------------------------------------------------- "),nl,
        write("Идет поиск оптимального маршрута движения... "),nl,
        оптимальный_путь(Stan1,Stan2).
 
GOAL
go.

путь(Старт,Z) :- 
                поиск_в_ширину([[Старт]],Z,Решение),
                обращ(Решение,X),
                %вывод([X],1,Старт,Z).
                write("Поиск в ширину : ",X,"\n").%,fail.

смежные(А,Б,Время):-время_перегона(А,Б,Время).
смежные(А,Б,Время):-станция(А,СтанцияА),станция(Б,СтанцияБ),время_пересадки(СтанцияА,СтанцияБ,Время).

время_пересадки1(А,Б,Время):-время_пересадки(А,Б,Время);время_пересадки(Б,А,Время).

смежные(А,Б,Время):-станция(А,СтанцияА),станция(Б,СтанцияБ),
    время_пересадки(СтанцияА,СтанцияБ,ВремяПересадки),
    время_ожидания(Б,ВремяОжидания),Время=ВремяПересадки+ВремяОжидания.

predicates
way(integer,список)
prolong(список,список)
place(список,список,список)
placeone(список,список,список)
search_bst(symbol,symbol,список)
bst(список,symbol,список)
 
clauses     
prolong(way(C,[X|T]),way(C1,[Y,X|T])):- 
        перегон(X,Y,A),not(принадлежит(Y,[X|T])),
        C1 = C+A.
 
place([],L,L).
place([X|T],L,R):-
        placeone(X,L,L1),place(T,L1,R).
 
placeone(way(C,P),[way(C1,P1)|R],[way(C,P),way(C1,P1)|R]):-
        C<C1,!.
placeone(way(C,P),[X|T],[X|R]):-
        placeone(way(C,P),T,R).
placeone(way(C,P),[],[way(C,P)]).
 
search_bst(Start,Finish,Res):-
        bst([way(0,[Start])],Finish,way(_,Res)).
bst([way(C,[Finish|T])|_],Finish,way(C,[Finish|T])).
bst([Path|Rest],Finish,R):-
        findall(Z,prolong(Path,Z),NewPathes),
        place(NewPathes,Rest,NewQueue),!,
        bst(NewQueue,Finish,R).
bst([P|T],F,R):-
        bst(T,F,R).

станция(а1,юго_западная).
станция(а2,проспект_вернадского).
станция(а3,университет).
станция(а4,воробьевы_горы).
станция(а5,спортивная).
станция(а6,фрунзенская).
станция(а7,парк_культуры_сокольнической_линии).
станция(а8,кропоткинская).
станция(а9,библиотека_имени_ленина).
станция(а10,охотный_ряд).
станция(а11,лубянка).
станция(а12,чистые_пруды).
станция(а13,красные_ворота).
станция(а14,комсомольская_сокольнической_линии).
станция(а15,красносельская).
станция(а16,сокольники).
станция(а17,преображенская_площадь).
станция(а18,черкизовская).
станция(а19,улица_подбельского).
 
%Линия метро Замоскворецкая
станция(б1,красногвардейская).
станция(б2,домодедовская).
станция(б3,орехово).
станция(б4,царицыно).
станция(б5,кантемировская).
станция(б6,каширская_замоскворецкой_линии).
станция(б7,коломенская).
станция(б8,автозаводская).
станция(б9,павелецкая_замоскворецкой_линии).
станция(б10,новокузнецкая).
станция(а10,театральная).
станция(б12,тверская).
станция(б13,маяковская).
станция(б14,белорусская_замоскворецкой_линии).
станция(б15,динамо).
станция(б16,аэропорт).
станция(б17,сокол).
станция(б18,войковская).
станция(б19,водный_стадион).
станция(б20,речной_вокзал).
 
%Линия метро Арбатско-Покровская
станция(в1,митино).
станция(в2,волоколамская).
станция(в3,мякинино).
станция(в4,строгино).
станция(в5,крылатское).
станция(в6,молодежная).
станция(в7,кунцевская_арбатско_покровской_линии).
станция(в8,славянский_бульвар).
станция(в9,парк_победы).
станция(в10,киевская_арбатско_покровской_линии).
станция(в11,смоленская).
станция(а9,арбатская_арбатско_покровской_линии).
станция(а10,площадь_революции).
станция(в14,курская_арбатско_покровской_линии).
станция(в15,бауманская).
станция(в16,электрозаводская).
станция(в17,семеновская).
станция(в18,партизанская).
станция(в19,измайловская).
станция(в20,первомайская).
станция(в21,щелковская).
 
%Линия метро Филевская
станция(г1,кунцевская_филевской_линии).
станция(г2,пионерская).
станция(г3,филёвский_парк).
станция(г4,багратионовская).
станция(г5,фили).
станция(г6,кутузовская).
станция(г7,студенческая).
станция(г8,киевская_филевской_линии).
станция(г9,смоленская).
станция(г10,арбатская_филевской_линии).
станция(г11,александровский_сад).
 
%Линия метро Кольцевая
станция(д1,добрынинская_кольцевой_линии).
станция(д2,павелецкая_кольцевой_линии).
станция(д3,таганская_кольцевой_линии).
станция(д4,курская_кольцевой_линии).
станция(д5,комсомольская_кольцевой_линии).
станция(д6,проспект_мира_кольцевой_линии).
станция(д7,новослободская_кольцевой_линии).
станция(д8,белорусская_кольцевой_линии).
станция(д9,краснопресненская).
станция(д10,киевская_кольцевой_линии).
станция(д11,парк_культуры_кольцевой_линии).
станция(д12,октябрьская_кольцевой_линии).
 
%Линия метро Калужско-Рижская
станция(е1,битцевский_парк).
станция(е2,ясенево).
станция(е3,теплый_стан).
станция(е4,коньково).
станция(е5,беляево).
станция(е6,калужская).
станция(е7,новые_черемушки).
станция(е8,профсоюзная).
станция(е9,академическая).
станция(е10,ленинский_проспект).
станция(е11,шаболовская).
станция(е12,октябрьская_калужско_рижской_линии).
станция(е13,третьяковская_калужско_рижской_линии).
станция(е14,китай_город_калужско_рижской_линии).
станция(е15,тургеневская).
станция(е16,сухаревская).
станция(е17,проспект_мира_калужско_рижской_линии).
станция(е18,рижская).
станция(е19,алексеевская).
станция(е20,вднх).
станция(е21,ботанический_сад).
станция(е22,свиблово).
станция(е23,бабушкинская).
станция(е24,медведково).
 
%Линия метро Таганско-Краснопресненская
станция(ё1,выхино).
станция(ё2,рязанский_проспект).
станция(ё3,кузьминки).
станция(ё4,текстильщики).
станция(ё5,волгоградский_проспект).
станция(ё6,пролетарская).
станция(ё7,таганская_таганско_краснопресненской_линии).
станция(ё8,китай_город_таганско_краснопресненской_линии).
станция(ё9,кузнецкий_мост).
станция(ё20,пушкинская).
станция(ё11,баррикадная).
станция(ё12,улица_1905_года).
станция(ё13,беговая).
станция(ё14,полежаевская).
станция(ё15,октябрьское_поле).
станция(ё16,щукинская).
станция(ё17,тушинская).
станция(ё18,сходненская).
станция(ё19,планетарная).
 
%Линия метро Калининская
станция(ж1,третьяковская_калининской_линии).
станция(ж2,марксистская).
станция(ж3,площадь_ильича).
станция(ж4,авиамоторная).
станция(ж5,шоссе_энтузиастов).
станция(ж6,перово).
станция(ж7,новогиреево).
 
%Линия метро Серпуховско-Тимирязевская
станция(з1,бульвар_дмитрия_донского).
станция(з2,аннино).
станция(з3,улица_академика_янгеля).
станция(з4,пражское).
станция(з5,южная).
станция(з6,чертановская).
станция(з7,севастопольская).
станция(з8,нахимовский_проспект).
станция(з9,нагорная).
станция(з10,нагатинская).
станция(з11,тульская).
станция(з12,серпуховская).
станция(з13,полянка).
станция(з14,боровицкая).
станция(з15,чеховская).
станция(з16,цветной_бульвар).
станция(з17,менделеевская).
станция(з18,савеловская).
станция(з19,дмитровская).
станция(з20,тимирязевская).
станция(з21,петровско_разумовская).
станция(з22,владыкино).
станция(з23,отрадное).
станция(з24,бибирево).
станция(з25,алтуфьево).
 
%Линия метро Люблинская
станция(и1,марьино).
станция(и2,братиславская).
станция(и3,люблино).
станция(и4,волжская).
станция(и5,печатники).
станция(и6,кожуховская).
станция(и7,дубровка).
станция(и8,крестьянская_застава).
станция(и9,римская).
станция(и10,чкаловская).
станция(и11,сретенский_бульвар).
станция(и12,трубная).
станция(и13,достоевская).
станция(и14,марьина_роща).
 
%Линия метро Каховская
станция(й1,каховская).
станция(й2,варшавская).
станция(й3,каширская_каховской_линии).
 
%Линия метро Бутовская
станция(к1,бунинская_аллея).
станция(к2,улица_горчакова).
станция(к3,бульвар_адмирала_ушакова).
станция(к4,улица_скобелевская).
станция(к5,бульвар_дмитрия_донского).
 
%Время пересадок-------------------------------------------------------------------------------
время_пересадки_(александровский_сад,библиотека_имени_ленина,2).
время_пересадки_(библиотека_имени_ленина,боровицкая,4).
время_пересадки_(боровицкая,арбатская_арбатско_покровской_линии,3).%заком
время_пересадки_(арбатская_арбатско_покровской_линии,александровский_сад,1).%заком
время_пересадки_(александровский_сад,боровицкая,1).
время_пересадки_(арбатская_арбатско_покровской_линии,библиотека_имени_ленина,5).%заком
время_пересадки_(киевская_арбатско_покровской_линии,киевская_филевской_линии,3).%заком
время_пересадки_(киевская_филевской_линии,киевская_кольцевой_линии,2).
время_пересадки_(киевская_кольцевой_линии,киевская_арбатско_покровской_линии,3).%заком
время_пересадки_(тверская,пушкинская,4).
время_пересадки_(пушкинская,чеховская,2).
время_пересадки_(чеховская,тверская,4).
время_пересадки_(охотный_ряд,театральная,2).
время_пересадки_(театральная,площадь_революции,1).%заком
время_пересадки_(площадь_революции,охотный_ряд,3).%заком
время_пересадки_(новокузнецкая,третьяковская_калужско_рижской_линии,4).
время_пересадки_(третьяковская_калужско_рижской_линии,третьяковская_калининской_линии,3).
время_пересадки_(третьяковская_калининской_линии,новокузнецкая,2).
время_пересадки_(чистые_пруды,тургеневская,3).
время_пересадки_(тургеневская,сретенский_бульвар,1).
время_пересадки_(сретенский_бульвар,чистые_пруды,3).
время_пересадки_(таганская_кольцевой_линии,таганская_таганско_краснопресненской_линии,3).
время_пересадки_(таганская_таганско_краснопресненской_линии,марксистская,2).
время_пересадки_(марксистская,таганская_кольцевой_линии,1).
время_пересадки_(курская_арбатско_покровской_линии,курская_кольцевой_линии,4).%заком
время_пересадки_(курская_кольцевой_линии,чкаловская,4).
время_пересадки_(чкаловская,курская_арбатско_покровской_линии,1).%заком
время_пересадки_(кунцевская_арбатско_покровской_линии,кунцевская_филевской_линии,1).%заком
время_пересадки_(краснопресненская,баррикадная,1).
время_пересадки_(белорусская_замоскворецкой_линии,белорусская_кольцевой_линии,3).
время_пересадки_(парк_культуры_сокольнической_линии,парк_культуры_кольцевой_линии,5).
время_пересадки_(новослободская,менделеевская,2).
время_пересадки_(октябрьская_калужско_рижской_линии,октябрьская_кольцевой_линии,3).
время_пересадки_(цветной_бульвар,трубная,4).
время_пересадки_(лубянка,кузнецкий_мост,2).
время_пересадки_(добрынинская,серпуховская,3).
время_пересадки_(каховская,севастопольская,2).
время_пересадки_(бульвар_дмитрия_донского,улица_старокачаловская,1).
время_пересадки_(проспект_мира_кольцевой_линии,проспект_мира_калужско_рижской_линии,4).
время_пересадки_(китай_город_калужско_рижской_линии,китай_город_таганско_краснопресненской_линии,4).
время_пересадки_(павелецкая_замоскворецкой_линии,павелецкая_кольцевой_линии,5).
время_пересадки_(комсомольская_сокольнической_линии,комсомольская_кольцевой_линии,1).
время_пересадки_(каширская_замоскворецкой_линии,каширская_каховской_линии,2).
время_пересадки_(площадь_ильича,римская,4).
время_пересадки_(пролетарская,крестьянская_застава,4).
 
время_пересадки(А,Б,Время):-станция(А,СтанцияА),станция(Б,СтанцияБ),
    время_пересадки_(СтанцияА,СтанцияБ,Время).
время_пересадки(А,Б,Время):-станция(А,СтанцияА),станция(Б,СтанцияБ),
    время_пересадки_(СтанцияБ,СтанцияА,Время).
 
 
%Время перегонов-------------------------------------------------------------------------------
%Линия метро Сокольническая
время_перегона_(а1,а2,4).
время_перегона_(а2,а3,4).
время_перегона_(а3,а4,3).
время_перегона_(а4,а5,4).
время_перегона_(а5,а6,3).
время_перегона_(а6,а7,4).
время_перегона_(а7,а8,3).
время_перегона_(а8,а9,3).
время_перегона_(а9,а10,3).
время_перегона_(а10,а11,3).
время_перегона_(а11,а12,3).
время_перегона_(а12,а13,3).
время_перегона_(а13,а14,3).
время_перегона_(а14,а15,3).
время_перегона_(а15,а16,3).
время_перегона_(а16,а17,4).
время_перегона_(а17,а18,5).
время_перегона_(а18,а19,4).
 
%Линия метро Замоскворецкая
время_перегона_(б1,б2,4).
время_перегона_(б2,б3,4).
время_перегона_(б3,б4,6).
время_перегона_(б4,б5,5).
время_перегона_(б5,б6,5).
время_перегона_(б6,б7,6).
время_перегона_(б7,б8,6).
время_перегона_(б8,б9,6).
время_перегона_(б9,б10,3).
время_перегона_(б10,а10,5).
время_перегона_(а10,б12,3).
время_перегона_(б12,б13,3).
время_перегона_(б13,б14,2).
время_перегона_(б14,б15,4).
время_перегона_(б15,б16,4).
время_перегона_(б16,б17,3).
время_перегона_(б17,б18,4).
время_перегона_(б18,б19,4).
время_перегона_(б19,б20,4).
 
%Линия метро Арбатско-Покровская
время_перегона_(в1,в2,3).
время_перегона_(в2,в3,3).
время_перегона_(в3,в4,4).
время_перегона_(в4,в5,4).
время_перегона_(в5,в6,4).
время_перегона_(в6,в7,4).
время_перегона_(в7,в8,4).
время_перегона_(в8,в9,4).
время_перегона_(в9,в10,4).
время_перегона_(в10,в11,4).
время_перегона_(в11,в12,4).
время_перегона_(в12,в13,3).
время_перегона_(в13,в14,5).
время_перегона_(в14,в15,3).
время_перегона_(в15,в16,4).
время_перегона_(в16,в17,4).
время_перегона_(в17,в18,4).
время_перегона_(в18,в19,4).
время_перегона_(в19,в20,3).
время_перегона_(в20,в21,3).
 
%Линия метро Филевская
время_перегона_(г1,г2,5).
время_перегона_(г2,г3,5).
время_перегона_(г3,г4,3).
время_перегона_(г4,г5,3).
время_перегона_(г5,г6,3).
время_перегона_(г6,г7,3).
время_перегона_(г7,г8,4).
время_перегона_(г8,г9,4).
время_перегона_(г9,г10,4).
время_перегона_(г10,г11,4).
 
%Линия метро Кольцевая
время_перегона_(д1,д2,3).
время_перегона_(д2,д3,4).
время_перегона_(д3,д4,4).
время_перегона_(д4,д5,4).
время_перегона_(д5,д6,4).
время_перегона_(д6,д7,4).
время_перегона_(д7,д8,4).
время_перегона_(д8,д9,4).
время_перегона_(д9,д10,4).
время_перегона_(д10,д11,4).
время_перегона_(д11,д12,3).
время_перегона_(д12,д1,3).
 
%Линия метро Калужско-Рижская
время_перегона_(е1,е2,4).
время_перегона_(е2,е3,4).
время_перегона_(е3,е4,5).
время_перегона_(е4,е5,3).
время_перегона_(е5,е6,4).
время_перегона_(е6,е7,4).
время_перегона_(е7,е8,3).
время_перегона_(е8,е9,3).
время_перегона_(е9,е10,4).
время_перегона_(е10,е11,4).
время_перегона_(е11,е12,3).
время_перегона_(е12,е13,4).
время_перегона_(е13,е14,4).
время_перегона_(е14,е15,3).
время_перегона_(е15,е16,3).
время_перегона_(е16,е17,3).
время_перегона_(е17,е18,4).
время_перегона_(е18,е19,4).
время_перегона_(е19,е20,4).
время_перегона_(е20,е21,5).
время_перегона_(е21,е22,4).
время_перегона_(е22,е23,4).
время_перегона_(е23,е24,5).
 
%Линия метро Таганско-Краснопресненская
время_перегона_(ё1,ё2,4).
время_перегона_(ё2,ё3,4).
время_перегона_(ё3,ё4,4).
время_перегона_(ё4,ё5,5).
время_перегона_(ё5,ё6,4).
время_перегона_(ё6,ё7,4).
время_перегона_(ё7,ё8,4).
время_перегона_(ё8,ё9,3).
время_перегона_(ё9,ё10,3).
время_перегона_(ё10,ё11,4).
время_перегона_(ё11,ё12,3).
время_перегона_(ё12,ё13,3).
время_перегона_(ё13,ё14,4).
время_перегона_(ё14,ё15,4).
время_перегона_(ё15,ё16,4).
время_перегона_(ё16,ё17,5).
время_перегона_(ё17,ё18,4).
время_перегона_(ё18,ё19,3).
 
%Линия метро Калининская
время_перегона_(ж1,ж2,4).
время_перегона_(ж2,ж3,5).
время_перегона_(ж3,ж4,4).
время_перегона_(ж4,ж5,4).
время_перегона_(ж5,ж6,4).
время_перегона_(ж6,ж7,4).
 
%Линия метро Серпуховско-Тимирязевская
время_перегона_(з1,з2,6).
время_перегона_(з2,з3,5).
время_перегона_(з3,з4,4).
время_перегона_(з4,з5,3).
время_перегона_(з5,з6,4).
время_перегона_(з6,з7,4).
время_перегона_(з7,з8,3).
время_перегона_(з8,з9,3).
время_перегона_(з9,з10,4).
время_перегона_(з10,з11,5).
время_перегона_(з11,з12,6).
время_перегона_(з13,з13,5).
время_перегона_(з13,з14,4).
время_перегона_(з14,б12,4).
время_перегона_(з15,з16,3).
время_перегона_(з16,з17,4).
время_перегона_(з17,з18,4).
время_перегона_(з18,з19,4).
время_перегона_(з19,з20,3).
время_перегона_(з20,з21,4).
время_перегона_(з21,з22,4).
время_перегона_(з22,з23,4).
время_перегона_(з23,з24,4).
время_перегона_(з24,з25,5).
 
%Линия метро Люблинская
время_перегона_(и1,и2,6).
время_перегона_(и2,и3,5).
время_перегона_(и3,и4,4).
время_перегона_(и4,и5,4).
время_перегона_(и5,и6,5).
время_перегона_(и6,и7,4).
время_перегона_(и7,и8,3).
время_перегона_(и8,и9,4).
время_перегона_(и9,и10,4).
время_перегона_(и10,и11,6).
время_перегона_(и11,и12,4).
время_перегона_(и12,и13,4).
время_перегона_(и13,и14,3).
 
%Линия метро Каховская
время_перегона_(и1,й2,6).
время_перегона_(й2,и3,7).
 
%Линия метро Бутовская
время_перегона_(к1,к2,3).
время_перегона_(к2,к3,3).
время_перегона_(к3,к4,2).
время_перегона_(к4,к5,4).
 
время_перегона(А,Б,Время):-время_перегона_(А,Б,Время);время_перегона_(Б,А,Время).
 
%Ограничение на максимальное количество пересадок
%максимальное_количество_пересадок(3).
 
 
%---------------------------------------------------------------------------------
%Получение и вывод результатов
%---------------------------------------------------------------------------------
 
оптимальный_путь(Stan1,Stan1):- %Если введена одна и таже станция.
                !,write("Конечный пункт следования совпадает с начальным, поэтому поиск прекращен"),
        nl,nl.%,go.
 
оптимальный_путь(Stan1,Stan2):- станция(X,Stan1),станция(Y,Stan2),путь(X,Y),go.
 
 
принадлежит(X,[X|_]).
принадлежит(X,[_|Хвост]):-принадлежит(X,Хвост).
 
обращ(X,Y):- обращ([],X,Y).
 
обращ(Y,[],Y).
обращ(X1,[Z|X2],Y):- обращ([Z|X1],X2,Y).
 
 
путь(Старт,Z):- bst([way(0,[Старт])],Z,way(Время_пути,Решение)),
    обращ(Решение,Еинешер),write("Путь:\n"),вывод(Еинешер,Время_пути,0,0).
 
 
вывод([_],Время_пути,Количество_пересадок,Количество_перегонов):-write("Время пути: "),write(Время_пути),
    write(" минут,\nПересадок: "),write(Количество_пересадок),
    write("\nПерегонов: "),write(Количество_перегонов),nl,nl,nl.
вывод([А,Б|Хвост],Время_пути,Пересадки,Перегоны):-
    время_пересадки(А,Б,_),!,Пересадки1 = Пересадки+1,
    станция(А,СтанцияА),станция(Б,СтанцияБ),
    write(СтанцияА),write("   пересадка -->   "),write(СтанцияБ),nl,
    вывод([Б|Хвост],Время_пути,Пересадки1,Перегоны).
вывод([А,Б|Хвост],Время_пути,Пересадки,Перегоны):-Перегоны1 = Перегоны+1,
    станция(А,СтанцияА),станция(Б,СтанцияБ),
    write(СтанцияА),write("   переезд -->   "),write(СтанцияБ),nl,
    вывод([Б|Хвост],Время_пути,Пересадки,Перегоны1).
 
go:-
                write("Программа определения оптимального маршрута движения в метро"),nl,
                write("Для выхода нажмите Esc"),nl,
                write("Начальная станция: "),readln(Stan1),
                write("Конечная станция: "),readln(Stan2),
                write("---------------------------------------------------------------------- "),nl,
                write("Идет поиск оптимального маршрута движения... "),nl,
                оптимальный_путь(Stan1,Stan2).
 
prolong(way(C,[X|T]),way(C1,[Y,X|T])):-
                время_перегона(X,Y,A),not(принадлежит(Y,[X|T])),
                C1 = C+A.
prolong(way(C,[X|T]),way(C1,[Y,X|T])):-
                время_пересадки(X,Y,A),not(принадлежит(Y,[X|T])),
                C1 = C+A.
 
 
place([],L,L).
place([X|T],L,R):-
                placeone(X,L,L1),place(T,L1,R).
 
placeone(way(C,P),[way(C1,P1)|R],[way(C,P),way(C1,P1)|R]):-
                C<C1,!.
placeone(way(C,P),[X|T],[X|R]):-
                placeone(way(C,P),T,R).
placeone(way(C,P),[],[way(C,P)]).
 
bst([way(C,[Fin=h|T])|_],Fin=h,way(C,[Fin=h|T])):-!.
bst([Path|Rest],Fin=h,R):-
                findall(Z,prolong(Path,Z),NewPathes),
                place(NewPathes,Rest,NewQueue),!,
                bst(NewQueue,Fin=h,R).
bst([_|T],F,R):-
                bst(T,F,R).