Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地

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


您没有登录。 请登录注册

多人持火炬过桥问题

浏览上一个主题 浏览下一个主题 向下  留言 [第1页/共1页]

1 多人持火炬过桥问题 于 周六 十月 27, 2012 4:54 pm

发一则问题:如下列网页中所述,
http://hi.baidu.com/hlhykcvhkxbafmq/item/60e58bd01cf46dffcb0c3975
一般来说问题形式就是有几个人要过桥,每个人过桥行走的时间有差别。桥的承载力只够同时有二人在上头走,并且因环境是黑夜,众人只有一根火炬可用,所以凡二人过桥,须有一人把火炬带回出发处。问题要求全员过桥花费的最短时间。

这问题我曾经写在我的博客 (不晓得墙内是否能见到) ,但不久就被一位年轻人破解,因我用的是启发规则方法解题。稍微想了,解决办法应该用动态规划。在prolog解题大概是写成如下查询,然後找最小的Result。
代码:

?- member(A,List), member(B,List), A \= B, max(A,B,M), min(A,B,C,N),
  diff_set(List,[C],List1),
  member(D,List1), member(E,List1), D \= E, max(D,E,M1), min(D,E,F,N1),
  diff_set(List1,[F],List2),
  ...,
  Result is M+N+M1+N1+...

查阅用户资料 http://yauhsien.wordpress.com

2 回复: 多人持火炬过桥问题 于 周日 十月 28, 2012 4:57 am

学习。这之前还没看过动态规划的例子呢

查阅用户资料

3 回复: 多人持火炬过桥问题 于 周二 十月 30, 2012 12:06 pm

参数说明:

MF(Monkey From)是移动前猴子的位置,[0,0,0,0]表示猴子还没开跑,[1,1,1,1]表示猴子都过去了。
FF(Fire From)是移动前火把的位置。R是准备记录移动路径的,方便成功时我们可以印出过程。
T0是移动前的时刻。

MT(Monkey To)是移动后猴子的位置,FT(Fire To)是移动后火把的位置,
RR是移动后的新移动过程记录。T1是移动后的时刻。


代码:
continue_pass(MF, FF, R, T0) :- pass(MF, FF, T1, MT, FT, RR, R, T0),
                          T1 =< 21, ( nth1(X, MT, 0) -> continue_pass(MT, FT, RR, T1); print_solution(RR)).

pass(MF, FF, T1, MTT, FT, RR, R, T0) :- nth1(A, MF, FF), nth1(B, MF, FF),
        move(MT, MF, A), (A \= B -> move(MTT, MT, B), A < B, append(R, [A-B], RR); MTT = MT, append(R, [A], RR)),
        fire_move(FT, FF), nth1(A, [3,2,7,10], TA), nth1(B, [3,2,7,10], TB), T1 is T0 + max(TA, TB).

move(MT, MF, N) :- nth1(N, MF, X), X1 is 1 - X, replace(MF, N, X1, MT).

fire_move(FT, FF) :- FT is 1 - FF.

print_solution(R) :- forall(member(A, R), (write(A), write(','))).

replace(List, Index, With, ListOut) :-
  Idx is Index - 1, length(Before,Idx),
  append(Before, [_Discard|Rest], List),
  append(Before, [With|Rest], ListOut).


执行结果:

4 ?- continue_pass([0,0,0,0], 0, [], 0).
1-2,1,3-4,2,1-2,
true ;
;
1-2,2,3-4,1,1-2,
true ;
;
false.

表示有两种走法:

第一种:1和2一起过,时间过去3分钟;
1跑回来,时间过去6分钟;
3和4一起过去,16分钟过去;
2跑回来,18分钟过去;
1和2一起过去,刚好21分钟。

第二种:与第1种方法其实一样,差别在2先跑回来,再换1跑回来。

查阅用户资料 http://prolog.longluntan.net

浏览上一个主题 浏览下一个主题 返回页首  留言 [第1页/共1页]

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