为d *精简版优化伪代码

Question

我看 DLite的优化​​版本：

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() 

我无法猜测为什么在44行和46被评为一样 条件（如果u 〜= s_goal）。在 进入第43行和第45行中的if/if else之前，将无法评估该行为吗？ 难道是：

if (u != s_goal) 
if (c_old=c(u,v)) 
    rhs(u)=min(rhs(u),c(u,v)+g(v)); 
elseif (rhs(u)=c_old + g(v)) 
    rhs(u)=min_s'(c(u,s')+g(s')) 

会是错的？

问候

Answer 1

这看起来好像它的工作，但如果u是s_goal很少，那么你已经添加了一个测试，几乎每一次迭代，其中rhs并不需要更新到整体节省空间一对夫妇的说明和时间。