A * реализация в проверке PHP - PullRequest
Новая
       24

A * реализация в проверке PHP

6 голосов
/ 26 февраля 2011

Это код, который я получил с сайта здесь , и я хотел бы знать, правильна ли эта реализация 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 можно найти здесь

1 Ответ

9 голосов
/ 02 марта 2011

Сайт предполагает, что ошибка может быть в классе PQueue.

В PQueue::pop это 

$j+1 < $m

- это проверка, имеет ли узел кучи в $i один дочерний (в $j) или два (в $j и $j+1).

Но $m здесь count($h) только на первой итерации цикла, поскольку --$m в условии цикла вычисляется каждый раз.

Переместите это --$m рядом с array_pop, к которому оно относится, и это будет на одну ошибку меньше.

Теперь для AStarSolver.

Переменные (относительно псевдокод Wikipedia ):

  • $o - открыть, установить в качестве приоритетной очереди;
  • $l - открыть набор как карта с индексом;
  • $c - закрытый набор как карта с индексом;
  • $n - текущий узел ( x );
  • $m - соседний узел ( y )?;
  • $j - индекс соседнего узла.

Проблемы, которые я вижу:

  • $n = $o->pop() не сопровождается unset($l[$n['i']]). Поскольку $o и $l представляют один и тот же набор, они должны быть синхронизированы.

  • Согласно Википедии закрытое множество используется, только если эвристика монотонна (и я думаю, что эвристика расстояния монотонна), и в этом случае, когда узел добавляется в закрытое установить, это никогда не посещается снова. Этот код, кажется, реализует некоторый другой псевдокод , который удаляет узлы из закрытого набора. Я думаю, что это противоречит цели закрытого множества, и первое условие во внутреннем цикле должно быть

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

    Тогда мы можем удалить unset($c[$j]).

  • $m['g'] в этом состоянии должен быть g -счет текущего соседа, проиндексированного $j. Но $m имеет значение, оставшееся от предыдущего цикла: узел, соответствующий $j на предыдущей итерации.

    Нам нужен способ найти узел и его g -счет по индексу узла. Мы можем сохранить узел в массиве $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 в правой верхней части пути есть ненужная петля.

Так как я думал об этом, я реализовал собственную версию алгоритма и опубликовал ее в ответ на ваш предыдущий вопрос .

...