向 A* php 实现添加非单调启发式

Question

我正在使用 aaz 的 PHP 中的 A* 搜索算法来帮助我找到跨节点 3D 图的最短路径。

它做得很好，但它返回的是它找到的第一条路线，这可能不是最佳路线。由于节点集是 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

这个问题已经在两年前被问过（当时我正在回答它），但其中存在一个明显的误解，我想在我的回答中解决。

简单来说：
A* 在给定可接受的启发式函数的情况下找到最佳解决方案。

如果启发式函数从不高估，那么它就是可接受的。

例如，查看下图（粗略）：

如果 h 从不（对于搜索空间中的任何状态）超过 h* ，证明 A* 会找到给定 h 的最佳解决方案，因为它是启发式函数。

所以单调性根本不会影响最优性！

然后，问：“我将如何调整此实现以搜索最佳路线而不仅仅是最短路线？”

A：不幸的是，您没有提供最佳的确切含义，但总体而言没有任何变化。只需更改您的启发式函数，使最理想的状态成为最佳点，并尝试使其尽可能合理，同时即使对于单个状态也不要高估。