최적화 된 의사 코드

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

그것은 잘못된 것입니까?

감사 작동 할 것처럼 보이지만, u은 거의 s_goal없는 경우, 당신은 어디 rhs 공간에 전체 몇 지침을 저장 업데이트하지 않아도 거의 모든 반복에 하나 개의 테스트를 추가 한

Answer 1

시간.