Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地
Would you like to react to this message? Create an account in a few clicks or log in to continue.
Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地

一个供Prolog爱好者学习与交流的地方


您没有登录。 请登录注册

[问题求解]火车站问题

2 posters

向下  留言 [第1页/共1页]

1[问题求解]火车站问题 Empty [问题求解]火车站问题 周六 三月 31, 2012 3:23 am

wdx04



比利时是一个铁道上的国家。1835年5月5日,欧洲大陆开行的第一列火车把首都布鲁塞尔和省会城市梅赫伦连接在了一起。紧接着比利时又修建了大量的铁路,形成了一个密集的铁路网。火车经常晚点,但这并不妨碍人们居住在这个国家的任何一个城市,却在另一个城市工作。因为乘火车去工作,并不比坐公交车从长岛去曼哈顿,或者从墨尔本郊外到墨尔本大学更费时。既然交通的便利性不是问题,因此人们愿意居住在哪个地方是由其它因素决定的。请编写谓词station/1,这个谓词只成功一次,使它的参数合一为最好的一个火车站(也就是最好的城市,因为每座城市只有一个火车站),如果不存在这样一个火车站,谓词失败。
这里:
“小城市”指最多只与两座城市有铁路直连的城市,相应的,大城市与多于两个相邻的城市有铁路直连。
“好城市”总是一个“小城市”,并且它到最近的两个大城市的距离相等(这是为了购物方便)。
“最好的城市”是所有的“好城市”中,与最近的两个大城市距离最短的一个(因为人们不愿意为购物而跑过远的路程)。
两座城市之间的铁路连接由事实rail/2给出,所有铁路都是双向的,而且长度相等。两个城市的距离就是它们之间最短的铁路线长度。
例1:
rail(brussel,mechelen).
rail(brussel,antwerpen).
rail(brussel,gent).
rail(antwerpen,mechelen).
rail(antwerpen,gent).
rail(gent,brugge).
?- station(X).
X = mechelen

例2:
rail(brussel,charleroi).
rail(brussel,haacht).
rail(haacht,mechelen).
rail(mechelen,berchem).
rail(berchem,antwerpen).
rail(brussel,boom).
rail(boom,antwerpen).
rail(antwerpen,turnhout).
?- station(X).
X = boom

2[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周六 三月 31, 2012 2:21 pm

Mercury Liao


Admin

wdx04 写道:比利时是一个铁道上的国家。1835年5月5日,欧洲大陆开行的第一列火车把首都布鲁塞尔和省会城市梅赫伦连接在了一起。紧接着比利时又修建了大量的铁路,形成了一个密集的铁路网。火车经常晚点,但这并不妨碍人们居住在这个国家的任何一个城市,却在另一个城市工作。因为乘火车去工作,并不比坐公交车从长岛去曼哈顿,或者从墨尔本郊外到墨尔本大学更费时。既然交通的便利性不是问题,因此人们愿意居住在哪个地方是由其它因素决定的。请编写谓词station/1,这个谓词只成功一次,使它的参数合一为最好的一个火车站(也就是最好的城市,因为每座城市只有一个火车站),如果不存在这样一个火车站,谓词失败。
这里:
“小城市”指最多只与两座城市有铁路直连的城市,相应的,大城市与多于两个相邻的城市有铁路直连。
“好城市”总是一个“小城市”,并且它到最近的两个大城市的距离相等(这是为了购物方便)。
“最好的城市”是所有的“好城市”中,与最近的两个大城市距离最短的一个(因为人们不愿意为购物而跑过远的路程)。
两座城市之间的铁路连接由事实rail/2给出,所有铁路都是双向的,而且长度相等。两个城市的距离就是它们之间最短的铁路线长度。
例1:
rail(brussel,mechelen).
rail(brussel,antwerpen).
rail(brussel,gent).
rail(antwerpen,mechelen).
rail(antwerpen,gent).
rail(gent,brugge).
?- station(X).
X = mechelen

例2:
rail(brussel,charleroi).
rail(brussel,haacht).
rail(haacht,mechelen).
rail(mechelen,berchem).
rail(berchem,antwerpen).
rail(brussel,boom).
rail(boom,antwerpen).
rail(antwerpen,turnhout).
?- station(X).
X = boom

这题看起来简单写起来不容易啊…
很好奇W大都是从哪找到这些题目的?
这些题目是专门针对prolog出的吗?

下面是我写的,试了一下至少和题目提供的例子跑出来是一样的结果:

代码:
direct_linked(X,Y) :- rail(X,Y); rail(Y,X).

distance(X, Y, D, Path) :-
  direct_linked(X,Y) -> D = 1 ;
  direct_linked(X, W), not(member(W,Path)), append(Path, [W], New_Path),
  min_distance(W, Y, D1, New_Path), D is D1 + 1.

min_distance(X, Y, Min_Distance, Path) :- setof(D ,distance(X, Y, D, Path), D_list), min_list(D_list, Min_Distance).

small_city(C) :- setof(City, direct_linked(C,City), Set), length(Set,Len), Len =< 2.

big_city(C) :- direct_linked(C, _), not(small_city(C)).

good_city(C, Min_Distance) :-
  small_city(C), big_city(A), big_city(B), A \= B,
  min_distance(C,A,Min_Distance, [C]), min_distance(C,B,Db,[C]), Min_Distance = Db.

best_city(C) :- setof(Candidate-D, good_city(Candidate, D), D_list), return_min_num(D_list, Num), member(C-Num, D_list).

return_min_num(List, Num) :- findall(N, member(C-N, List), Num_list), min_list(Num_list, Num).

station(S) :- setof(C, best_city(C), S).

http://prolog.longluntan.net

3[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 5:47 am

wdx04



这都是“国际Prolog编程竞赛”的题目,网上有答案,可惜没有测试数据。
这是我的版本,比较重视性能
代码:

:- ensure_loaded([library(lists),library(ordsets)]).
:- dynamic city_cnt/2,city/2.

% 把城市分类按大小分类
% call: classification_cities
classification_cities :-
rail(X, Y),
inc_city(X),
inc_city(Y),
fail.

classification_cities :-
city_cnt(X, N),
(
N > 2 ->
assert(city(big, X))
;
assert(city(small, X))
),
retract(city_cnt(X,N)),
fail.

classification_cities.

inc_city(X) :-
(
city_cnt(X,N) ->
N1 is N + 1,
retract(city_cnt(X,N)),
assert(city_cnt(X,N1))
;
assert(city_cnt(X,1))
).

% 两个城市是否直连
% call: conncected(?City1, ?City2)
connected(X, Y) :- rail(X, Y).
connected(X, Y) :- rail(Y, X).

% 扩展开放列表
% call: expand_nodes(+Sources, [], -Targets)
expand_nodes([OneNode|RestNodes], CurrExpandedNodes, ExpandedNodes) :-
setof(OtherNode, connected(OneNode, OtherNode), OtherNodes),
ord_union(CurrExpandedNodes, OtherNodes, NewExpandedNodes),
expand_nodes(RestNodes, NewExpandedNodes, ExpandedNodes).
expand_nodes([], ExpandedNodes, ExpandedNodes).

% 判断列表中有哪些大城市
% call: get_big_cities(+Cities, -BigCities)
get_big_cities([OneNode|RestNodes], [OneNode|RestBigCities]) :-
city(big, OneNode), !, get_big_cities(RestNodes, RestBigCities).
get_big_cities([_|RestNodes], RestBigCities) :-
get_big_cities(RestNodes, RestBigCities).
get_big_cities([], []).

% 查找最近的大城市
nearest_big_cities(OpenNodes, ClosedNodes, CurrentDistance, BigCities, Distance) :-
expand_nodes(OpenNodes, [], TempNewNodes1),
ord_subtract(TempNewNodes1, OpenNodes, TempNewNodes2),
ord_subtract(TempNewNodes2, ClosedNodes, NewNodes),
NewNodes \= [],
get_big_cities(NewNodes, TempBigCities),
(TempBigCities == [] ->
NewDistance is CurrentDistance + 1,
ord_union(OpenNodes, ClosedNodes, NewClosedNodes),
!, nearest_big_cities(NewNodes, NewClosedNodes, NewDistance, BigCities, Distance)
;
Distance = CurrentDistance,
BigCities = TempBigCities
).

nearest_big_cities(SmallCity, BigCities, Distance) :-
nearest_big_cities([SmallCity], [], 1, BigCities, Distance).

good_city(SmallCity, Distance) :-
city(small, SmallCity),
nearest_big_cities(SmallCity, BigCities, Distance),
length(BigCities, 2).

station(BestCity) :-
retractall(city(_,_)),
classification_cities,
setof((Distance,GoodCity), good_city(GoodCity,Distance), [(_,BestCity)|_]),
!.

这是参考答案:
代码:

:- use_module(library(lists), [member/2]).

station(Station) :-
setof(Distance-City,good_city(City,Distance),[_-Station|_]).

good_city(City,Distance) :-
small_city(City),
setof(big_city(Distance,BigCity,OutRail),
reachable_big_city(City,BigCity,Distance,OutRail),BigCities),
BigCities = [big_city(Distance,City1,OutRail1)|Rest],
Rest = [big_city(Distance,City2,OutRail2)|_],
City1 \== City2,
OutRail1 \== OutRail2.

reachable_big_city(City,BigCity,Distance,OutRail) :-
rail_c(City,OutRail),
Visited = [City],
reachable(OutRail,BigCity,Visited,Distance),
big_city(BigCity).

reachable(City,City,Visited,Distance) :- length(Visited,Distance).

reachable(City,TargetCity,Visited,Distance) :-
rail_c(City,City1),
\+ member(City1,Visited),
reachable(City1,TargetCity,[City|Visited],Distance).

big_city(City) :-
rail_c(City,CityA),
rail_c(City,CityB),
rail_c(City,CityC),
CityA \== CityB,
CityA \== CityC,
CityB \== CityC.

small_city(City) :-
rail_c(City,_),
\+ big_city(City).

rail_c(From,To) :- rail(From,To).
rail_c(From,To) :- rail(To,From).

4[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 5:53 am

wdx04



附4个自制的参考数据(没有使用真实的城市名称):

代码:

rail(city2,city29).
rail(city18,city15).
rail(city27,city12).
rail(city27,city11).
rail(city5,city30).
rail(city6,city7).
rail(city1,city25).
rail(city12,city13).
rail(city18,city9).
rail(city14,city4).
rail(city26,city7).
rail(city17,city14).
rail(city7,city23).
rail(city22,city21).
rail(city21,city19).
rail(city20,city13).
rail(city3,city2).
rail(city22,city24).
rail(city17,city10).
rail(city10,city19).
rail(city16,city23).
rail(city25,city7).
rail(city14,city15).
rail(city14,city20).
rail(city28,city7).
rail(city11,city7).
rail(city24,city29).
rail(city14,city7).
rail(city6,city16).
rail(city7,city30).
rail(city1,city7).
rail(city9,city5).
rail(city14,city8).

代码:

rail(city7,city21).
rail(city18,city15).
rail(city24,city26).
rail(city29,city23).
rail(city6,city24).
rail(city20,city8).
rail(city30,city4).
rail(city19,city25).
rail(city4,city19).
rail(city9,city21).
rail(city30,city9).
rail(city8,city10).
rail(city17,city2).
rail(city26,city23).
rail(city23,city21).
rail(city17,city23).
rail(city18,city20).
rail(city21,city19).
rail(city23,city16).
rail(city14,city19).
rail(city8,city21).
rail(city28,city3).
rail(city25,city7).
rail(city13,city28).
rail(city23,city1).
rail(city22,city11).
rail(city23,city5).
rail(city3,city22).
rail(city11,city8).
rail(city15,city21).
rail(city27,city12).
rail(city13,city5).
rail(city19,city23).
rail(city8,city27).
rail(city6,city16).
rail(city2,city12).

代码:

rail(city11,city16).
rail(city3,city15).
rail(city24,city8).
rail(city29,city20).
rail(city1,city26).
rail(city15,city32).
rail(city14,city13).
rail(city3,city25).
rail(city9,city28).
rail(city3,city30).
rail(city27,city2).
rail(city19,city33).
rail(city19,city18).
rail(city15,city23).
rail(city34,city8).
rail(city28,city4).
rail(city32,city7).
rail(city31,city12).
rail(city24,city23).
rail(city22,city28).
rail(city35,city17).
rail(city13,city11).
rail(city33,city35).
rail(city31,city4).
rail(city15,city10).
rail(city33,city5).
rail(city18,city28).
rail(city7,city22).
rail(city20,city2).
rail(city6,city1).
rail(city26,city34).
rail(city28,city21).
rail(city25,city27).
rail(city12,city30).
rail(city3,city29).
rail(city17,city3).
rail(city15,city30).
rail(city30,city16).
rail(city28,city14).

代码:

rail(city25,city16).
rail(city20,city25).
rail(city23,city31).
rail(city15,city20).
rail(city4,city18).
rail(city13,city4).
rail(city22,city37).
rail(city7,city25).
rail(city32,city6).
rail(city20,city7).
rail(city25,city27).
rail(city7,city16).
rail(city4,city22).
rail(city18,city8).
rail(city30,city4).
rail(city18,city30).
rail(city10,city34).
rail(city12,city37).
rail(city20,city12).
rail(city27,city20).
rail(city13,city24).
rail(city36,city8).
rail(city29,city31).
rail(city39,city36).
rail(city18,city38).
rail(city30,city5).
rail(city30,city20).
rail(city3,city16).
rail(city6,city15).
rail(city11,city2).
rail(city35,city18).
rail(city7,city18).
rail(city28,city5).
rail(city7,city32).
rail(city14,city21).
rail(city16,city4).
rail(city16,city30).
rail(city16,city23).
rail(city29,city11).
rail(city1,city40).
rail(city3,city19).
rail(city1,city39).
rail(city30,city25).
rail(city27,city9).
rail(city25,city28).
rail(city17,city18).
rail(city4,city20).
rail(city21,city7).
rail(city18,city25).
rail(city24,city7).
rail(city20,city2).
rail(city27,city18).
rail(city18,city34).
rail(city14,city7).
rail(city19,city27).
rail(city16,city18).
rail(city7,city4).
rail(city27,city7).
rail(city16,city27).
rail(city27,city30).
rail(city26,city10).
rail(city25,city40).
rail(city26,city38).
rail(city30,city7).
rail(city18,city33).

5[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 6:28 am

Mercury Liao


Admin

当最好的城市不只一个的时候,
你的程序是怎么选择最终结果的?

因为我用我自己写的程序来跑,
我的程序是会将所有满足最好城市的车站列出来的,
按你提供的试测数据的话,
有好几测试数据跑出来会有超过一个解。

http://prolog.longluntan.net

6[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 6:37 am

Mercury Liao


Admin

顺带一问,有人知道

17 ?- time(station(X)).
% 117,768,176 inferences, 37.125 CPU in 37.140 seconds (100% CPU, 3172207 Lips)

里面,各个数字实际代表什么意思吗?

按字面翻译来看,inferences是指推理,
但我不晓得这边prolog是把什么认定为推理,
这个数字是越大代表你的程序效率高还是越小代表效率高?

37.140应该是你花了多久时间跑这个程序,37.125又是什么?
100% CPU是指什么? 3172207Lips跟你的程序效率有什么关系?

http://prolog.longluntan.net

7[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 6:37 am

wdx04



Mercury Liao 写道:当最好的城市不只一个的时候,
你的程序是怎么选择最终结果的?

因为我用我自己写的程序来跑,
我的程序是会将所有满足最好城市的车站列出来的,
按你提供的试测数据的话,
有好几测试数据跑出来会有超过一个解。
有多个最好城市的时候,只要输出其中之一就可以了,这个可以人工验证。

8[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 6:51 am

wdx04



Mercury Liao 写道:顺带一问,有人知道

17 ?- time(station(X)).
% 117,768,176 inferences, 37.125 CPU in 37.140 seconds (100% CPU, 3172207 Lips)

里面,各个数字实际代表什么意思吗?

按字面翻译来看,inferences是指推理,
但我不晓得这边prolog是把什么认定为推理,
这个数字是越大代表你的程序效率高还是越小代表效率高?

37.140应该是你花了多久时间跑这个程序,37.125又是什么?
100% CPU是指什么? 3172207Lips跟你的程序效率有什么关系?
37.125是CPU计算时间,也就是实际时间(37.140)减去磁盘读写、屏幕显示等其它操作占用的时间

Lips是Logical Inferences Per Second,每秒钟执行的逻辑推理数,常用于衡量Prolog虚拟机自身的性能,例如SICStus Prolog官网说它在i7上的性能在61MLips以上,而你这里只有3.17MLips。
http://www.sics.se/isl/sicstuswww/site/performance.html

100%表示程序运行时占用了100%的CPU计算资源。

9[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 7:07 am

Mercury Liao


Admin

wdx04 写道:
Mercury Liao 写道:顺带一问,有人知道

17 ?- time(station(X)).
% 117,768,176 inferences, 37.125 CPU in 37.140 seconds (100% CPU, 3172207 Lips)

里面,各个数字实际代表什么意思吗?

按字面翻译来看,inferences是指推理,
但我不晓得这边prolog是把什么认定为推理,
这个数字是越大代表你的程序效率高还是越小代表效率高?

37.140应该是你花了多久时间跑这个程序,37.125又是什么?
100% CPU是指什么? 3172207Lips跟你的程序效率有什么关系?
37.125是CPU计算时间,也就是实际时间(37.140)减去磁盘读写、屏幕显示等其它操作占用的时间

Lips是Logical Inferences Per Second,每秒钟执行的逻辑推理数,常用于衡量Prolog虚拟机自身的性能,例如SICStus Prolog官网说它在i7上的性能在61MLips以上,而你这里只有3.17MLips。
http://www.sics.se/isl/sicstuswww/site/performance.html

100%表示程序运行时占用了100%的CPU计算资源。

喔,感谢回答。

那同样都用SWI-Prolog的情况下,
程序能做到的功能也相同的情况下,
是inferences越大的越好,还是越小的越好?

或者是说,time谓词主要能给我们用来判断的信息其实就只有花了几秒的时间,
时间越少就是越好?

http://prolog.longluntan.net

10[问题求解]火车站问题 Empty 回复: [问题求解]火车站问题 周日 四月 01, 2012 7:13 am

wdx04



inferences越小越好。
就像我们研究排序算法的时候,认为平均比较次数越少越好一样

你的代码移植到支持tabling的Prolog环境下可以加快很多,比如说Yap-tabling和B-Prolog。
移植到Yap的tabling只要在最前面加三行代码:
代码:

:- ensure_loaded([library(lists)]).
:- table(small_city/1).
:- table(big_city/1).

返回页首  留言 [第1页/共1页]

您在这个论坛的权限:
不能在这个论坛回复主题