Как найти маршрут между двумя станциями в PROLOG - PullRequest
Новая
       26

Как найти маршрут между двумя станциями в PROLOG

0 голосов
/ 16 марта 2020

Извините, я знаю, что этот вопрос часто поднимается, но я провел много исследований и просто не могу понять, как решить эту проблему. Я представил карту труб в PROLOG и мне нужно написать предикат, который возвращает все маршруты между двумя станциями. Я знаю, что мне нужно использовать рекурсию, и я пробовал кучу разных решений, но ни одно из них не работает. Вот факты, которые у меня есть: 

station('AL',[metropolitan]).%Aldgate on the Metropolitan Line
station('BG',[central]).%Bethnal Green on the Central Line
station('BR',[victoria]).%Brixton on the Victoria Line
station('BS',[metropolitan]).%Baker Street on the Metropolitan Line
station('CL',[central]).%Chancery Lane on the Central Line
station('EC',[bakerloo]).%Elephant & Castle on the Bakerloo Line
station('EM',[bakerloo,northern]).%Embankment on the Bakerloo and Northern Lines
station('EU',[northern]).%Euston on the Northern Line
station('FP',[victoria]).%Finsbury Park on the Victoria Line
station('FR',[metropolitan]).%Finchley Road on the Metropolitan Line
station('KE',[northern]).%Kennington on the Northern Line
station('KX',[metropolitan,victoria]).%Kings Cross on the Metropolitan and Victoria Lines
station('LG',[central]).%Lancaster Gate on the Central Line
station('LS',[central,metropolitan]).%Liverpool Street on the Central and Metropolitan Lines
station('NH',[central]).%Notting Hill Gate on the Central Line
station('OC',[bakerloo,central,victoria]).%Oxford Circus on the Bakerloo, Central and Victoria Lines
station('PA',[bakerloo]).%Paddington on the Bakerloo Line
station('TC',[central,northern]).%Tottenham Court Road on the Central and Northern Lines
station('VI',[victoria]).%Victoria on the Victoria Line
station('WA',[bakerloo]).%Warwick Avenue on the Bakerloo Line
station('WS',[northern,victoria]).%Warren Street on the Northern and Victoria Lines
adjacent('WA','PA').%Warwick Avenue is adjacent to Paddington
adjacent('PA','OC').%Paddington is adjacent to Oxford Circus
adjacent('OC','EM').%Oxford Circus is adjacent to Embankment
adjacent('EM','EC').%Embankment is adjacent to Elephant & Castle
adjacent('NH','LG').%Notting Hill Gate is adjacent to Lancaster Gate
adjacent('LG','OC').%Lancaster Gate is adjacent to Oxford Circus
adjacent('OC','TC').%Oxford Circus is adjacent to Tottenham Court Road
adjacent('TC','CL').%Tottenham Court Road is adjacent to Chancery Lane
adjacent('CL','LS').%Chancery Lane is adjacent to Lviverpool Street
adjacent('LS','BG').%Liverpool Street is adjacent to Bethnal Green
adjacent('FR','BS').%Finchley Road is adjacent to Baker Street
adjacent('BS','KX').%Baker Street is adjacent to Kings Cross
adjacent('KX','LS').%Kings Cross is adjacent to Liverpool Street
adjacent('LS','AL').%Liverpool Street is adjacent to Algate
adjacent('EU','WS').%Euston is adjacent Warren Street
adjacent('WS','TC').%Warren Street is adjacent to Tottenham Court Road
adjacent('TC','EM').%Tottenham Court Road is adjacent to Embankment
adjacent('EM','KE').%Embankment is adjacent to Kennington
adjacent('BR','VI').%Brixton is adjacent to Victoria
adjacent('VI','OC').%Victoria is adjacent to Oxford Circus
adjacent('OC','WS').%Oxford Circus is adjacent to Warren Street
adjacent('WS','KX').%Warrent Street is adjacent to Kings Cross
adjacent('KX','FP').%Kings Cross is adjacent to Finsbury Park

И решение, которое я попробовал, это: 

route(From,To,Route) :-
   routeattempt(From,To,[From],Route),
   reverse(Route,route).

routeattempt(From,To,Inbetween,Route) :-
   adjacent(From,To),
   \+member(From,Inbetween),
   Route = [From|Inbetween].
routeattempt(From,To,Visited,Route) :-
   adjacent(From,Inbetween),
   Inbetween \== To,
   \+member(Inbetween,Visited),
   routeattempt(Inbetween,To,Inbetween|Visited],Route).

Но оно просто возвращает ложь на любой вход. Если бы кто-то мог помочь, это было бы здорово.

1 Ответ

0 голосов
/ 16 марта 2020

Это сбивает с толку.

В 

route(From,To,Route) :-
   routeattempt(From,To,[From],Route),
   reverse(Route,route).

очевидно, что routeattempt/4 предлагает "найти маршрут от From до To для сохранения в виде списка станций в Route. Но что конкретно делает аргумент 3, здесь [From]? Это список посещенных станций, но действительно ли он вам нужен? У вас уже есть Route.

Теперь у вас есть подсистемы: From или To смежны: 

routeattempt(From,To,Inbetween,Route) :-
   adjacent(From,To),
   \+member(From,Inbetween),
   Route = [From|Inbetween].

или не являются: 

routeattempt(From,To,Visited,Route) :-
   adjacent(From,Inbetween),
   Inbetween \== To,
   \+member(Inbetween,Visited),
   routeattempt(Inbetween,To,Inbetween|Visited],Route).

В первом случае (базовый случай) , неясно, зачем проверять, является ли From членом Inbetween. Действительно, это исключит поиск любого маршрута между двумя соседними станциями, потому что route/3 уже внесет From в список Inbetween И не должен ли маршрут между двумя соседними станциями быть не просто [From,To] вместо [From|Inbetween]?

Во втором случае вам нужно go от From до To с помощью waytation Inbetween, который также не равен To, и еще не посещен. Хорошо. Но вам нужно заполнить Route после r рекурсивный вызов.

Попробуйте добавить format("Current route from ~w to ~w: ~w\n", [From, To, Route]) до adjacent/2 и посмотрите, что произойдет.

...