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で1秒もかかりません（最適化なしでは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 で問題を解決できることを証明します。プロジェクト オイラーの問題ステートメントに示されている基本ケースを使用してソリューションをデバッグすることをお勧めします。