recursion - 如何在 PROLOG 中找到两个站点之间的路线
问题描述
抱歉,我知道这个问题出现了很多,但我做了很多研究,我就是不知道如何解决这个问题。我在 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).
但它只会对任何输入返回 false。如果有人可以提供帮助,那就太好了。
解决方案
这很困惑。
在
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]
吗?
在第二种情况下,你从From
到To
by waystation Inbetween
,这也不等于To
,并且还没有被访问过。好的。但是你需要Route
在递归调用之后完成。
尝试在format("Current route from ~w to ~w: ~w\n", [From, To, Route])
前面添加一个adjacent/2
,看看会发生什么。
推荐阅读
- javascript - 如何转发 ref 函数声明而不是箭头函数?
- amazon-web-services - Route53 和 ElasticBeanstalk,如何使 DNS 记录对应用程序更新具有持久性?
- c - lang-c 使用嵌套的for循环和函数打印两个中间有空格的金字塔?
- python - Python 在 C++ 中崛起 ** 运算符
- java - 为什么我的android应用程序循环时不会增加时间?
- c++ - 令人沮丧的数学问题,结果不如预期(EDQ)
- tomcat - 使用 Pentaho 用户控制台 9.0 生成 PDF 报告
- python - 使用上下文管理器重构 if-else 块 python?
- python - seaborn点图可视化
- python - 如何运行模型而无需再次运行训练数据