在
莫贝特的blog看到一个过桥问题：
四个女人过桥，夜间有一火把，每次最多过两个，必需带火把，过桥速度不一样
no.1 1min
no.2 2min
no3 5min
no.4 10min
两个人过用最慢一个的速度，火把不能扔，如何在17min内四个女人都过桥？
我一开始想穷举法，但无法建立规则和程序的对应。后来看了两个例子：
把火把优化掉，变成一次过去两个人，回来一个人。
河对岸没人，则把未过河的人按照过河时间升序排列，然后取两人过河；
河对岸有人，则把未过河的人按照过河时间降序排列，然后取两人过河。
未全过河时，每次总是取过河用时最小的人返回。
河对岸没人，取过河用时最小的两个人过河。
河对岸有人，如果左岸过桥时间最短的比右岸过桥时间最短的还短,则派两个时间最长的妇女过岸。（这个策略在现在的情况下，和上一个策略相同，但是定的比较牵强）
判断是否都已过河，没有则总是取过河用时最小的人返回。
对于更复杂的情况，策略可以指定的大致如下：
大的和小的在一起优先过小的（因为只有小的过去了回来的时候才能选小的）；
在对面有小的情况下优先过大的（桥对面没小的优先选择小的先过去）；
过桥的时候永远选择和自己最大最接近的那个因为那样最省时间（5和10在一起过节省5分钟）；
回来的时候永远选最小的。
听人说对于过桥问题可以制定策略后，用广度优先搜索做，还在努力中……
阅读(980) | 评论(0) | 转发(0) |
