A * implementation in PHP validation

Question

This is the code I got from the site here , and I would like to know if this implementation of A * is correct. I looked at it and compared it to the wikipedia page, and it seems valid. The reason I ask is because the site says that there is an error in this code, I tried to find it, but I can not find it. I want to change it, so that it accepts the beginning and assignment as an input parameter

<?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; } } ?> 

The code in Pqueue can be found here.

Answer 1

The site suggests that the error may be in the PQueue class.

In PQueue::pop this

 $j+1 < $m 

is a check whether the node at $i heap has one child (in $j ) or two (in $j and $j+1 ).

But $m here count($h) only at the first iteration through the loop, since --$m in the loop condition is evaluated every time.

Move --$m next to array_pop where it belongs, and it will be smaller.

---

Now for AStarSolver .

Variables (relative to Wikipedia pseudocode ):

• $o - open the set as a priority queue;
• $l - open the set as a card with a key by index;
• $c - a closed task in the form of a card with a key by index;
• $n - current node (x);
• $m - neighbor node (y) ?;
• $j is the neighboring index node.

The problems that I see:

• $n = $o->pop() does not follow unset($l[$n['i']]) . Since both $o and $l represent the same set, they must be kept in sync.

• According to Wikipedia, a closed set is used only if the heuristic is monotonic (and I think the heuristic in the distance is monotonic), in which case when a node is added to the closed set, I never visited again. This code seems to implement some other pseudo code that removes nodes from the private set. I think this defeats the goal of the closed set, and the first condition in the inner loop should be

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

  Then we can remove unset($c[$j]) .

• $m['g'] in this condition there must be a g-account of the current neighbor indexed by $j . But $m has any value left over from the previous loop: node, corresponding to $j in the previous iteration.

  We need a way to find the node and its g-score on the node index. We can store the node in the array $l : instead of $l[$j] = TRUE do $l[$j] = $m , and the above condition becomes

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

• Now a difficult bit. If the found node is not in the open set, we add it there (which is $o->push and $l[$j] = ).

  However, if it is in an open set, we just found a better way for it, so we need to update it. The code does not, and it is difficult because the priority queue does not provide a routine to increase the priority of an element. However, we can completely restore the priority queue, and the last bit of code in the inner loop will become

  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']);
}

  This is not very effective, but it is a starting point. Changing an item in the priority queue is ineffective anyway, because you need to find it first.

---

Even without these changes, the algorithm finds the path, not the best path. You can see this in the labyrinths mentioned:

• In the crazy maze in the third inner chain: the upper path traveled is a little longer than the lower path would be due to obstacles on the left.

• In the big maze in the upper right part of the path there is an unnecessary upward loop.

---

Since this was in my opinion, I implemented my own version of the algorithm and posted it in response to your previous question .