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

Question

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

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

Answer 2

这里（作为参考）是在 c++ 中使用统一成本搜索-O2的解决方案，在 i7 上编译只需不到一秒（没有优化需要 3 秒）：

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct Node { 
    size_t i, j; int cost;
    Node(size_t i, size_t j, int cost) : i(i), j(j), cost(cost) {}
};
bool operator<(const Node& a, const Node& b) { return b.cost < a.cost; }
bool operator==(const Node& a, const Node& b) { return a.i == b.i && a.j == b.j; }

int main() {
    const size_t SIZE = 80;
    ifstream fis("matrix.txt");
    int matrix[SIZE][SIZE];
    char crap;
    for (size_t i = 0; i < SIZE; i++)
        for (size_t j = 0; j < SIZE; j++) {
            fis >> matrix[i][j];
            if (j < SIZE - 1) fis >> crap;
        }
    vector<Node> open;
    set<Node> closed;
    open.push_back(Node(0, 0, matrix[0][0]));
    make_heap(open.begin(), open.end());
    while (!open.empty()) {
        Node node = open.front();
        pop_heap(open.begin(), open.end()); open.pop_back();

        if (node.i == SIZE - 1 && node.j == SIZE - 1) {
            cout << "solution " << node.cost << endl;
            return 0;
        }
        closed.insert(node);
        Node children[] = { Node(node.i + 1, node.j, node.cost + matrix[node.i + 1][node.j]),
                            Node(node.i, node.j + 1, node.cost + matrix[node.i][node.j + 1]) };
        for (int k = 0; k < 2; k++) { 
            Node child = children[k];
            if (!closed.count(child)) {
                vector<Node>::iterator elem = find(open.begin(), open.end(), child);
                if (elem == open.end()) { 
                    open.push_back(child); push_heap(open.begin(), open.end());
                } else if (child.cost < (*elem).cost) {
                    (*elem).cost = child.cost;
                    make_heap(open.begin(), open.end());
                }
            }
        }
    }
}

这个解决方案会有点慢，因为它需要make_heap在打开的节点列表中替换元素，这会重建向量中的堆，但不应该永远落地，并证明可以使用 UCS 解决问题。一个建议是使用 Project Euler 问题陈述中给出的基本案例来调试您的解决方案。