將非單調啓發式添加到A * php implimentation

Question

我使用aaz的A* search algorithm in PHP來幫助我找到節點的三維圖形中的最短路徑。

它做得很好，但它返回的是它找到的第一條路線，它可能不是最佳路線。由於節點集合是3D，啓發式是非單調的。我將如何去適應這種精神去尋找最佳路線，而不僅僅是最短路線？

class astar extends database 
{ 
// Binary min-heap with element values stored separately 

var $map = array(); 
var $r; // Range to jump 
var $d; // distance between $start and $target 
var $x; // x co-ords of $start 
var $y; // y co-ords of $start 
var $z; // z co-ords of $start 


function heap_float(&$heap, &$values, $i, $index) { 
    for (; $i; $i = $j) { 
     $j = ($i + $i%2)/2 - 1; 
     if ($values[$heap[$j]] < $values[$index]) 
      break; 
     $heap[$i] = $heap[$j]; 
    } 
    $heap[$i] = $index; 
} 

function heap_push(&$heap, &$values, $index) { 
    $this->heap_float($heap, $values, count($heap), $index); 
} 

function heap_raise(&$heap, &$values, $index) { 
    $this->heap_float($heap, $values, array_search($index, $heap), $index); 
} 

function heap_pop(&$heap, &$values) { 
    $front = $heap[0]; 
    $index = array_pop($heap); 
    $n = count($heap); 
    if ($n) { 
     for ($i = 0;; $i = $j) { 
      $j = $i*2 + 1; 
      if ($j >= $n) 
       break; 
      if ($j+1 < $n && $values[$heap[$j+1]] < $values[$heap[$j]]) 
       ++$j; 
      if ($values[$index] < $values[$heap[$j]]) 
       break; 
      $heap[$i] = $heap[$j]; 
     } 
     $heap[$i] = $index; 
    } 
    return $front; 
} 

function a_star($start, $target) { 
    $open_heap = array($start); // binary min-heap of indexes with values in $f 
    $open  = array($start => TRUE); // set of indexes 
    $closed = array();    // set of indexes 

    $g[$start] = 0; 
    $d[$start] = 0; 
    $h[$start] = $this->heuristic($start, $target); 
    $f[$start] = $g[$start] + $h[$start]; 
    while ($open) { 
     $i = $this->heap_pop($open_heap, $f); 
     unset($open[$i]); 
     $closed[$i] = TRUE; 

     if ($i == $target) { 
      $path = array(); 
      for (; $i != $start; $i = $from[$i]) 
       $path[] = $i; 
      return array_reverse($path); 
     } 

     foreach ($this->neighbors($i) as $j => $rng) 
      if (!array_key_exists($j, $closed)) 
       if (!array_key_exists($j, $open) || $d[$i] + $rng < $d[$j])  { 
        $d[$j] = $d[$i]+$rng; 
        $g[$j] = $g[$i] + 1; 
        $h[$j] = $this->heuristic($j, $target); 
        $f[$j] = $g[$j] + $h[$j]; 
        $from[$j] = $i; 

        if (!array_key_exists($j, $open)) { 
         $open[$j] = TRUE; 
         $this->heap_push($open_heap, $f, $j); 
        } else 
         $this->heap_raise($open_heap, $f, $j); 
       } 
    } 

    return FALSE; 
} 

function jumpRange($i, $j){ 

    $sx = $this->map[$i]->x; 
    $sy = $this->map[$i]->y; 
    $sz = $this->map[$i]->z; 
    $dx = $this->map[$j]->x; 
    $dy = $this->map[$j]->y; 
    $dz = $this->map[$j]->z; 

    return sqrt((($sx-$dx)*($sx-$dx)) + (($sy-$dy)*($sy-$dy)) + (($sz-$dz)*($sz-$dz)))/9460730472580800; 
} 

function heuristic($i, $j) { 

    $rng = $this->jumpRange($i, $j); 
    return ceil($rng/$this->r); 
} 

function neighbors($sysID) 
{ 
    $neighbors = array(); 
    foreach($this->map as $solarSystemID=>$system) 
    { 
     $rng = $this->jumpRange($sysID,$solarSystemID); 
     $j = ceil($rng/$this->r); 
     $this->map[$solarSystemID]->h = $j; 
     if($j == 1 && $this->map[$solarSystemID]->s) 
     { 
      $neighbors[$solarSystemID] = $rng; 
     } 
    } 
    arsort($neighbors); 
    return $neighbors; 
} 

function fillMap() 
{ 
    $res = $this->query("SELECT * FROM mapSolarSystems WHERE SQRT(
    (
    ($this->x-x)*($this->x-x) 
) + (
    ($this->y-y)*($this->y-y) 
) + (
    ($this->z-z)*($this->z-z) 
) 
)/9460730472580800 <= '$this->d'","SELECT"); 
    while($line=mysql_fetch_object($res)) 
    { 
     $this->map[$line->solarSystemID] = $line; 
     $this->map[$line->solarSystemID]->h = 0; 
     $this->map[$line->solarSystemID]->s = false; 
    } 
    $res = $this->query("SELECT solarSystemID FROM staStations UNION SELECT solarSystemID FROM staConqureable","SELECT"); 
    while($line=mysql_fetch_object($res)) 
    { 
     if(isset($this->map[$line->solarSystemID])) 
      $this->map[$line->solarSystemID]->s = true; 
    } 
} 
} 

Answer 1

你的啓發式似乎是單調的直線距離。 在你的a_star方法中，你永遠不會檢查當前是否有更便宜的節點。

你可以修改你的$ open_heap數組來跟蹤開銷，而不是在每次迭代時彈出前端節點，從最便宜的彈出。

Answer 2

這個問題已經在2年前問過了（當時我正在回答），但是在我的回答中有一個明顯的誤解。

簡單來說：
A*發現給予admissible啓發函數的optimum溶液。

啓發式功能是admissible，如果它永遠不會高估。

例如看看下面的（粗糙）圖：

如果h從來沒有（在搜索空間中的任何狀態下）變爲了上文H *它證明，A*會發現給出最佳的解決方案因爲它是啓發式功能。

所以單調性不會影響最優性！

然後，Q：「我將如何去適應這個實現搜索最佳行車路線不只是最短？」

一個：可惜你沒有提供的究竟是什麼你的意思是最優的，但沒有什麼變化。只要改變你的啓發式功能，讓最渴望的狀態成爲最佳點，並儘可能使其儘可能敏感，同時不要高估即使是單一狀態。