3
我已經實現了d * -Lite算法（這裏有一個description，它是做尋路時邊緣成本隨時間變化的算法），但我有跟做邊成本的更新問題。它主要工作，但有時它會卡在一個循環中，在兩個頂點之間來回切換。我試圖創建一個展現此行爲的測試用例，此時它在某些情況下發生在大型應用程序中，這使得它很難調試。尋路算法創建循環
我，只要我能得到一個測試用例，但也許有人能發現我所做的僞要去C++馬上錯誤。
（下面有包括一個測試用例）文章介紹的優化版本，圖4，這是一個我實現。僞代碼粘貼在下面。
來源爲我實現菱here。
如果有幫助，我在我的代碼使用這些類型：
struct VertexProperties { double x, y; };
typedef boost::adjacency_list<boost::vecS,
boost::vecS,
boost::undirectedS,
VertexProperties,
boost::property<boost::edge_weight_t, double> > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef DStarEuclidianHeuristic<Graph, Vertex> Heuristic;
typedef DStarPathfinder<Graph, Heuristic> DStarPathfinder;
如果只問需要有關使用任何詳細信息，但只是太多的粘貼。爲d * -Lite
僞代碼：
procedure CalculateKey(s)
{01」} return [min(g(s), rhs(s)) + h(s_start, s) + km;min(g(s), rhs(s))];
procedure Initialize()
{02」} U = ∅;
{03」} km = 0;
{04」} for all s ∈ S rhs(s) = g(s) = ∞;
{05」} rhs(s_goal) = 0;
{06」} U.Insert(s_goal, [h(s_start, s_goal); 0]);
procedure UpdateVertex(u)
{07」} if (g(u) != rhs(u) AND u ∈ U) U.Update(u,CalculateKey(u));
{08」} else if (g(u) != rhs(u) AND u /∈ U) U.Insert(u,CalculateKey(u));
{09」} else if (g(u) = rhs(u) AND u ∈ U) U.Remove(u);
procedure ComputeShortestPath()
{10」} while (U.TopKey() < CalculateKey(s_start) OR rhs(s_start) > g(s_start))
{11」} u = U.Top();
{12」} k_old = U.TopKey();
{13」} k_new = CalculateKey(u));
{14」} if(k_old < k_new)
{15」} U.Update(u, k_new);
{16」} else if (g(u) > rhs(u))
{17」} g(u) = rhs(u);
{18」} U.Remove(u);
{19」} for all s ∈ Pred(u)
{20」} if (s != s_goal) rhs(s) = min(rhs(s), c(s, u) + g(u));
{21」} UpdateVertex(s);
{22」} else
{23」} g_old = g(u);
{24」} g(u) = ∞;
{25」} for all s ∈ Pred(u) ∪ {u}
{26」} if (rhs(s) = c(s, u) + g_old)
{27」} if (s != s_goal) rhs(s) = min s'∈Succ(s)(c(s, s') + g(s'));
{28」} UpdateVertex(s);
procedure Main()
{29」} s_last = s_start;
{30」} Initialize();
{31」} ComputeShortestPath();
{32」} while (s_start != s_goal)
{33」} /* if (g(s_start) = ∞) then there is no known path */
{34」} s_start = argmin s'∈Succ(s_start)(c(s_start, s') + g(s'));
{35」} Move to s_start;
{36」} Scan graph for changed edge costs;
{37」} if any edge costs changed
{38」} km = km + h(s_last, s_start);
{39」} s_last = s_start;
{40」} for all directed edges (u, v) with changed edge costs
{41」} c_old = c(u, v);
{42」} Update the edge cost c(u, v);
{43」} if (c_old > c(u, v))
{44」} if (u != s_goal) rhs(u) = min(rhs(u), c(u, v) + g(v));
{45」} else if (rhs(u) = c_old + g(v))
{46」} if (u != s_goal) rhs(u) = min s'∈Succ(u)(c(u, s') + g(s'));
{47」} UpdateVertex(u);
{48」} ComputeShortestPath()
編輯：
我已經成功地創建了測試用例足見其erronous行爲。與pastebin中的代碼一起運行，它將在最後的get_path調用中掛起，在節點1和2之間來回切換。在我看來，這是因爲節點3從未被觸摸過，所以這樣做無限的成本。
#include <cmath>
#include <boost/graph/adjacency_list.hpp>
#include "dstar_search.h"
template <typename Graph, typename Vertex>
struct DStarEuclidianHeuristic {
DStarEuclidianHeuristic(const Graph& G_) : G(G_) {}
double operator()(const Vertex& u, const Vertex& v) {
double dx = G[u].x - G[v].x;
double dy = G[u].y - G[v].y;
double len = sqrt(dx*dx+dy*dy);
return len;
}
const Graph& G;
};
struct VertexProp {
double x, y;
};
int main() {
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
VertexProp, boost::property<boost::edge_weight_t, double> > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;
typedef DStarEuclidianHeuristic<Graph, Vertex> Heur;
typedef boost::property_map<Graph, boost::edge_weight_t>::type WMap;
Graph g(7);
WMap weights = boost::get(boost::edge_weight, g);
Edge e;
// Create a graph
e = boost::add_edge(0, 1, g).first;
weights[e] = sqrt(2.);
e = boost::add_edge(1, 2, g).first;
weights[e] = 1;
e = boost::add_edge(2, 3, g).first;
weights[e] = 1;
e = boost::add_edge(1, 4, g).first;
weights[e] = 1;
e = boost::add_edge(3, 4, g).first;
weights[e] = 1;
e = boost::add_edge(3, 5, g).first;
weights[e] = sqrt(2.);
e = boost::add_edge(2, 6, g).first;
weights[e] = sqrt(2.);
e = boost::add_edge(5, 6, g).first;
weights[e] = 1;
e = boost::add_edge(6, 7, g).first;
weights[e] = 1;
g[0].x = 1; g[0].y = 0;
g[1].x = 0; g[1].y = 1;
g[2].x = 0; g[2].y = 2;
g[3].x = 1; g[3].y = 2;
g[4].x = 1; g[4].y = 1;
g[5].x = 2; g[5].y = 3;
g[6].x = 1; g[6].y = 3;
g[7].x = 1; g[7].y = 4;
DStarPathfinder<Graph, Heur> dstar(g, Heur(g), 0, 7);
std::list<std::pair<Edge, double>> changes;
auto a = dstar.get_path(); // Find the initial path, works well
std::copy(a.begin(), a.end(), std::ostream_iterator<Vertex>(std::cout, ","));
// Now change the cost of going from 2->6, and try to find a new path
changes.push_back(std::make_pair(boost::edge(2, 6, g).first, 4.));
dstar.update(changes);
a = dstar.get_path(); // Stuck in loop
std::copy(a.begin(), a.end(), std::ostream_iterator<Vertex>(std::cout, ","));
return 0;
}
編輯2：更多進展。如果我用U != Ø（U不爲空）代替ComputeShortestPath中的while循環中的中斷條件，則會找到路徑！它的速度很慢，因爲它總是檢查圖中的每個節點，這不應該是必需的。此外，由於我使用無向圖，我添加了一些代碼到{40"}來更新u和v。
使用下劃線：知道 - > k_new，gold-> g_old等。它使人們更容易解析代碼 - 我的大腦看到'黃金'並且想到金屬！ – Skizz
好點。修正了。 – carlpett
在你對fred的迴應中，你寫道曼哈頓距離是abs（dx + dy）。你的意思是abs（dx）+ abs（dy），對嗎？ – Clark