統一成本搜索項目歐勒＃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 

Answer 2

這裏（作爲參考）是使用在C Uniform-cost search ++溶液中，用-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稱爲make_heap用於在重建矢量堆中的開放節點列表中進行元素替換，但不應該永久登陸並證明可以使用UCS解決問題。建議使用Project Euler問題陳述中給出的基本案例來調試解決方案。