上周朋友提到一个智力题:
有4个人在晚上通过一座摇摇欲坠的小桥，并且每次只能让2个人过去。过桥的人必须要用到手电筒，不然会出事故，只有一个手电筒，4个人的行走速度不同。亚当用1分钟就可以走完，拉里用2分钟。埃奇用5分钟，最慢的汤姆用10分钟。两人同行时, 过桥速度取决于速度较慢者。请问用什么方法才能最快过桥，用时多少。
人肉一番：如果已经有人过桥，那么回送手电的必须是已经过桥的人中速度最快的那一个，而要想桥对面有过桥快的人，必须有过桥快的人过去。人就4个,比较好设计,答案可在1分钟内思考得到：
- 亚当和拉里先过，用时2分钟，然后亚当拿着手电筒再回来，用时3分钟。
- 汤姆和埃奇过用时10分钟，然后拉里拿着手电筒再回来，用时12分钟。
- 最后是亚当和拉里再回来，用时2分钟，总用时是17分钟。
后来提到如果人多了，问题规模变大了，怎么办呢？想必大家都知道，那就是交给机器去解决.
召唤AI
人工智能领域对于此类问题是有匹配的解决方案的,即A*算法.
它是一种在有多个节点的图中寻找达到目标节点最低成本的算法. 该算法综合了BFS和Dijkstra最短路径算法的优点, 主要是通过启发式搜索提高算法效率. 如果以g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么 A*算法的估算函数为：
- 如果g(n)为0，即只计算任意顶点n到目标的评估函数h(n)，而不计算起点到顶点n的距离，则算法转化为BFS(Best First Search),此时使用的是贪心策略，速度最快，但可能得不出最优解；
- 如果h(n)不为0，则一定可以求出最优解，而且h(n)越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
- 如果h(n)为0，即只需求出起点到任意顶点n的最短路径g(n)，而不计算任何评估函数h(n)，则转化为单源最短路径问题，即Dijkstra算法，此时需要计算最多的定点；
关于A*算法的更多性质和证明可参考wiki(比如一个有效评估f(n)必须要小于实际距离算法才有效的证明).本文就不再详细介绍.我们主要看一下当前这个问题,如何使用A-Star算法解决.
评估函数
虽然理论有了, 但具体问题还要具体分析. 正如前文所述,不同的问题有不同的评估函数,在建立评估函数前,需要对这个问题进行建模.
问题建模
状态
每当有人过桥,相对于初始的场景,都会生成一个新的场景. 对应桥的两端,可以使用tuple来表示. (1,2,5,10)<->() 就对应最开始的状态(假设左侧是未过桥,右侧tuple是已经过桥的). 比如汤姆(5)和埃奇(10)过桥,那么状态变为(1,2)<->(5,10).
状态迁移
还有一个问题,就是当前的状态下一步到底是有人从左到右还是从右到左呢. 这时,我们需要把手电筒加入到状态中:(1,2)<->(5,10), 'r', 如果最后一个标志位是r,那么下一步的操作就是亚当(1)和拉里(2)过桥. 可以使用python的namedtuple来表示如下:
Status = namedtuple('Status', ['left','right','torch'])
评估函数设计
有了这个模型, 问题变得比较清晰. 对于g(n)很简单,就是已经耗时多少, 那么h(n)就是从任一状态到()<->(1,2,5,10)的耗时函数了.设计h(n)最关键的地方在于,一定不要overestimate即可.
- 假设下一步是过河,且还有3人以上未过河, h(n)取左侧最大耗时加最小耗时
- 假设下一步是过河,还有2人或少于未过河, h(n)取左侧最大耗时
- 假设下一步是回送手电, 则h(n) 为 右侧最小耗时加左侧的h(n)
公式如下:
有了h(n)的公式,那么只需要把BFS算法加上priority-queue, 就可得到最终的A-Star算法了.
代码实现
代码如下:
from itertools import combinations
import heapq as hq
def tuple_eq(self, other):
if len(self) != len(other):
return False
for e in self:
if e not in other:
return False
return True
class Status(object):
def __init__(self, left, right, torch, prev = None):
self.left = left
self.right = right
self.torch = torch
self.prev = prev
def __eq__(self, other):
return self.torch == other.torch and tuple_eq(self.left, other.left) and tuple_eq(self.right, other.right)
def estimate(self):
def estimate_left():
return max(self.left) if len(self.left) <= 2 else max(self.left) + min(self.left)
if self.torch == 'l':
return estimate_left()
elif self.left:
return min(self.right) + estimate_left()
return 0
def yield_next(self):
def tuple_sub(minuend, subtrahend):
return tuple(set(minuend) - set(subtrahend))
def tuple_add(t1, t2):
return tuple(set(t1).union(set(t2)))
if self.torch == 'l':
for e in combinations(self.left, 2):
yield max(e), Status(tuple_sub(self.left, e),tuple_add(self.right, e), 'r')
if self.torch == 'r':
yield min(self.right), Status(tuple_add(self.left, (min(self.right),)),
tuple_sub(self.right, (min(self.right),)), 'l')
def __str__(self):
return '[' + str(self.left) + '--' + str(self.right) + ']'
def reverse_path(self):
if not self.prev:
return str(self)
return self.prev.reverse_path() + '->' + str(self)
start = Status((1,2,5,10), (),'l')
goal = Status((), (1,2,5,10),'r')
BIG_NUM = 1000
def A_Star(start, goal):
nexts = [(BIG_NUM,0,start)]
closed_set = set()
while nexts:
f_score, already_cost, current_status = hq.heappop(nexts)
if current_status == goal:
return already_cost, current_status.reverse_path()
closed_set.add(current_status)
for cost, next_status in current_status.yield_next():
if next_status not in closed_set:
next_status.prev = current_status
closed_set.add(next_status)
hq.heappush(nexts, (already_cost + cost + next_status.estimate(), already_cost + cost, next_status))
return 'fail'
print A_Star(start,goal)
实现策略方面:
- 放弃使用namedtuple自动生成类的原因是还需要添加其他函数, 每次都
Status.estimate = estimate的方式很不美观. - 为了简化代码,认为所有同学的过桥速度均不相等(这样可以使用内置的set表示).
代码运行结果:
(17, '[(1, 2, 5, 10)--()]->[(10, 5)--(1, 2)]->[(1, 10, 5)--(2,)]->[(1,)--(2, 10, 5)]->[(1, 2)--(10, 5)]->[()--(1, 10, 2, 5)]')
