发一则问题:如下列网页中所述,
http://hi.baidu.com/hlhykcvhkxbafmq/item/60e58bd01cf46dffcb0c3975
一般来说问题形式就是有几个人要过桥,每个人过桥行走的时间有差别。桥的承载力只够同时有二人在上头走,并且因环境是黑夜,众人只有一根火炬可用,所以凡二人过桥,须有一人把火炬带回出发处。问题要求全员过桥花费的最短时间。
这问题我曾经写在我的博客 (不晓得墙内是否能见到) ,但不久就被一位年轻人破解,因我用的是启发规则方法解题。稍微想了,解决办法应该用动态规划。在prolog解题大概是写成如下查询,然後找最小的Result。
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+...