algorithm - 统一成本搜索项目 euler #81

Question

我正在研究项目欧拉程序是为了“启蒙”，而不仅仅是解决它们。我已经在 80x80 矩阵上使用动态程序解决了问题 81，但是当我尝试使用统一成本搜索解决它时，我的程序消失在永无止境。我只想知道使用统一成本搜索是否可以解决这个问题？该问题可在 this link 找到.

Answer 1

UCS 绝对有效。

from Queue import PriorityQueue
with open('matrix.txt') as f:
    data = map(lambda s: map(int, s.strip().split(',')), f.readlines())
seen = set()
pq = PriorityQueue()
pq.put((data[0][0], 0, 0))
while not pq.empty():
    (s, i, j) = pq.get()
    if (i, j) not in seen:
        seen.add((i, j))
        if i + 1 < len(data):    pq.put((s + data[i + 1][j], i + 1, j))
        if j + 1 < len(data[i]): pq.put((s + data[i][j + 1], i, j + 1))
        if i + 1 >= len(data) and j + 1 >= len(data): print s