人工智能原理

E02

  • Problem

    有数个城市，给定每两个城市间的距离，用一致代价搜索找出从起点到终点间的最短路径并输出。UniformCostProblem

  • Code
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct path_node {
    path_node(string f, string d, int cost) : from(f), dest(d), cost(cost) {}
    string from;
    string dest;
    int cost;
};

struct search_node {
    bool operator<=(search_node o) {
        return cost <= o.cost;
    }
    string name;
    int cost;
    search_node *from;
    static vector<search_node*> p;
    static void deleteAll() {
        for_each(p.begin(), p.end(), [](search_node *t) { delete t; });
        p.clear();
    }
    static search_node* create(string name, int cost, search_node *from) {
        search_node *t = new search_node(name, cost, from);
        p.push_back(t);
        return t;
    }
private:
    search_node(string name, int cost, search_node *from) :name(name), cost(cost), from(from) {
        if (from) { cost += from->cost; }
    }
};
vector<search_node*> search_node::p;

class UniformCost
{
public:
    UniformCost() {
    };
    ~UniformCost() {
    };
    static vector<string> search(vector<path_node> t, string start, string target) {
        vector<string> path;
        vector<search_node*> q;
        search_node *cur = nullptr, *next = nullptr;
        unordered_map<string, bool> checked;
        bool finded = false;
        q.push_back(search_node::create(start, 0, nullptr));
        while (!q.empty()) {
            cur = q[0];
            q.erase(q.begin());
            checked[cur->name] = true;
            if (cur->name == target) {
                finded = true;
                break;
            }
            for_each(t.begin(), t.end(), [&](path_node n) {
                next = nullptr;
                if (n.from == cur->name) {
                    next = search_node::create(n.dest, n.cost, cur);

                }
                else if (n.dest == cur->name) {
                    next = search_node::create(n.from, n.cost, cur);
                }
                if (next && !checked[next->name]) {
                    q.push_back(next);
                }
            });
            sort(q.begin(), q.end(), [](search_node *f, search_node *s) { return f->cost < s->cost; });
        }
        if (finded) {
            while (cur) {
                path.insert(path.begin(), cur->name);
                cur = cur->from;
            }
        }

        search_node::deleteAll();
        return path;
    }
};



int main() {
    vector<path_node> v;
    v.push_back(path_node("Arad", "Sibiu", 140));
    v.push_back(path_node("Sibiu", "RiMnicu Vilcea", 80));
    v.push_back(path_node("Sibiu", "Fagaras", 99));
    v.push_back(path_node("RiMnicu Vilcea", "Craiova", 146));
    v.push_back(path_node("RiMnicu Vilcea", "Pitesti", 97));
    v.push_back(path_node("Fagaras", "Bucharest", 211));
    v.push_back(path_node("Craiova", "Pitesti", 138));
    v.push_back(path_node("Pitesti", "Bucharest", 101));

    vector<string> rs = UniformCost::search(v, "Arad", "Bucharest");
    for_each(rs.begin(), rs.end(), [](string name) {cout << "->" << name; });
    cout << endl;
    return 0;
}
  • Result
    UniformCost