爲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並不需要更新到整體節省空間一對夫婦的說明和時間。