在PHP驗證

Question

A *的實現。這是我從網站here有一個代碼，我想知道這個實現A *的是否正確。我已經看過它，並將其與維基百科頁面進行比較，它似乎是有效的。我之所以問，是因爲在該網站中它說這個代碼中仍然存在一個錯誤，我試圖找到它，但找不到任何。我希望如此，它需要的出發地和目的地作爲輸入參數

<?php 

class AStarSolver 
{ 
    function solve(&$s) 
    { 
     include_once('PQueue.class.php'); 
     $o = new PQueue(); 
     $l = array(); 
     $c = array(); 
     $p = array(); 
     $a = $s->getStartIndex(); 
     $z = $s->getGoalIndex(); 
     $d = $s->goalDistance($a); 

     $n0 = array('g'=>0, 'h'=>$d, 'i'=>$a, 'p'=>NULL, 'f'=>$d); 
     $o->push($n0, -$d); 
     $l[$a] = TRUE; 

     while (! $o->isEmpty()) 
     { 
      $n = $o->pop(); 

      if ($n['i'] == $z) 
      { 
       while ($n) 
       { 
        $p[] = $n['i']; 
        $n = $n['p']; 
       } 
       break; 
      } 

      foreach ($s->getNeighbors($n['i']) as $j => $w) 
      { 
       if ((isset($l[$j]) || isset($c[$j])) && isset($m) && $m['g'] <= $n['g']+$w) 
        continue; 

       $d = $s->goalDistance($j); 
       $m = array('g'=>$n['g']+$w, 'h'=>$d, 'i'=>$j, 'p'=>$n, 'f'=>$n['g']+$w+$d); 

       if (isset($c[$j])) 
        unset($c[$j]); 

       if (! isset($l[$j])) 
       { 
        $o->push($m, -$m['f']); 
        $l[$j] = TRUE; 
       } 
      } 
      $c[$n['i']] = $n; 
     } 
     return $p; 
    } 

} 

?> 

到Pqueue的代碼可以發現here

Answer 1

該網站顯示，該bug可能在PQueue類雖然改變它。

在PQueue::pop此

$j+1 < $m 

是測試在$i堆節點是否有一個子（在$j）或兩個（在$j和$j+1）。

但$m這裏是count($h)只在循環的第一次迭代，因爲每循環條件--$m進行評估。

將--$m移動到它所屬的array_pop旁邊，那樣會減少一個錯誤。

---

現在爲AStarSolver。

的變量是（相對於Wikipedia pseudocode）：

• $o - 開集作爲優先級隊列;
• $l - 開集作爲地圖由索引鍵;
• $c - 閉集作爲地圖由索引鍵;
• $n - 當前節點（X）;
• $m - 鄰居節點（Ý）？;
• $j - 鄰居節點索引。

的問題，我看到：

• $n = $o->pop()後面沒有unset($l[$n['i']])。由於$o和$l代表相同的集合，因此它們應保持同步。

• 根據維基百科的閉集，如果啓發式是單調只使用（和我想的距離啓發式是單調的），並且在這種情況下，一旦一個節點被添加到閉集，這是從來沒有再次訪問。此代碼似乎實現了一些other pseudocode，它從關閉的集合中刪除節點。我認爲這違背了閉集的目的，並在內部循環的首要條件應該是

  if (isset($c[$j]) || isset($l[$j]) && isset($m) && $m['g'] <= $n['g']+$w)

  然後，我們可以刪除unset($c[$j])。

• $m['g']在此條件下應該是克通過$j索引的當前相鄰的 -score。但是$m具有前一個循環遺留的任何值：在先前的迭代中對應於$j的節點。

  我們需要的是一種查找節點及其節點索引的方法。我們可以存儲陣列$l在節點：代替$l[$j] = TRUE我們做$l[$j] = $m和上述條件變得

  if (isset($c[$j]) || isset($l[$j]) && $l[$j]['g'] <= $n['g']+$w)

• 現在有點棘手。如果我們剛發現的節點不在開放集合中，我們在那裏添加它（這是$o->push和$l[$j] =）。

  但是，如果它是在開放集合中，我們只是找到了一條更好的路徑，所以我們必須更新它。代碼沒有這樣做，這很棘手，因爲優先級隊列沒有提供增加元素優先級的例程。但是，我們可以完全重建優先級隊列和代碼在內部循環的最後一個比特

  if (! isset($l[$j])) {
   $o->push($m, -$m['f']);
   $l[$j] = $m; // add a new element
} else {
   $l[$j] = $m; // replace existing element
   $o = new PQueue();
   foreach ($l as $m)
      $o->push($m, -$m['f']);
}

  這不是非常有效，但它是一個起點。無論如何改變優先隊列中的元素效率並不高，因爲你首先必須找到它。

---

即使沒有這些變化，算法確實找到一個路徑，只要不是最佳路徑。你可以看到它在提到迷宮：

• 在第三內部電路crazy迷宮：拍攝上的路徑周圍是略長於下路本來因爲左邊的障礙。

• 在路徑右上角的big迷宮中存在不必要的循環。

---

因爲這是在我的腦海，我實現我自己的算法的版本，並張貼在回答你的previous question。