StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The site suggests that the bug might be in the <code>PQueue</code> class.</p> <p>In <code>PQueue::pop</code> this</p> <pre><code>$j+1 < $m </code></pre> <p>is a test whether the heap node at <code>$i</code> has one child (at <code>$j</code>) or two (at <code>$j</code> and <code>$j+1</code>).</p> <p>But <code>$m</code> here is <code>count($h)</code> only on the first iteration through the loop, since the <code>--$m</code> in the loop condition is evaluated every time.</p> <p>Move that <code>--$m</code> next to the <code>array_pop</code> where it belongs, and that will be one less bug.</p> <hr> <p>Now for <code>AStarSolver</code>.</p> <p>The variables are (relative to <a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm?oldid=416264305#Pseudocode" rel="nofollow noreferrer">Wikipedia pseudocode</a>):</p> <ul> <li><code>$o</code> – open set as priority queue;</li> <li><code>$l</code> – open set as map keyed by index;</li> <li><code>$c</code> – closed set as map keyed by index;</li> <li><code>$n</code> – current node (<em>x</em>);</li> <li><code>$m</code> – neighbour node (<em>y</em>) ?;</li> <li><code>$j</code> – neighbour node index.</li> </ul> <p>Problems that I see:</p> <ul> <li><p><code>$n = $o->pop()</code> isn't followed by <code>unset($l[$n['i']])</code>. Since both <code>$o</code> and <code>$l</code> represent the same set, they should be kept in sync.</p></li> <li><p>According to Wikipedia the closed set is only used if the heuristic is <em>monotone</em> (and I think a distance heuristic is monotone), and in that case, once a node is added to the closed set, it is never visited again. This code seems to implement some <a href="http://www.heyes-jones.com/pseudocode.html" rel="nofollow noreferrer">other pseudocode</a>, which does remove nodes from the closed set. I think this defeats the purpose of the closed set, and the first condition in the inner loop should be</p> <p><code>if (isset($c[$j]) || isset($l[$j]) && isset($m) && $m['g'] <= $n['g']+$w)</code></p> <p>Then we can remove the <code>unset($c[$j])</code>.</p></li> <li><p><code>$m['g']</code> in this condition should be the <em>g</em>-score of the current neighbour indexed by <code>$j</code>. But <code>$m</code> has whatever value is left over from the previous loop: the node corresponding to <code>$j</code> on a previous iteration. </p> <p>What we need is a way to find a node and its <em>g</em>-score by node index. We can store the node in the <code>$l</code> array: instead of <code>$l[$j] = TRUE</code> we do <code>$l[$j] = $m</code> and the above condition becomes</p> <p><code>if (isset($c[$j]) || isset($l[$j]) && $l[$j]['g'] <= $n['g']+$w)</code></p></li> <li><p>Now the tricky bit. If the node we just found is not in the open set, we add it there (that's the <code>$o->push</code> and <code>$l[$j] =</code>).</p> <p>However, if it is in the open set we just found a better path to it, so we must update it. The code doesn't do this and it's tricky because the priority queue doesn't provide a routine for increasing the priority of an element. However, we can rebuild the priority queue completely and the last bit of code in the inner loop becomes</p> <p><code>if (! isset($l[$j])) {</code><br> <code> $o->push($m, -$m['f']);</code><br> <code> $l[$j] = $m; // add a new element</code><br> <code>} else {</code><br> <code> $l[$j] = $m; // replace existing element</code><br> <code> $o = new PQueue();</code><br> <code> foreach ($l as $m)</code><br> <code> $o->push($m, -$m['f']);</code><br> <code>}</code></p> <p>This is not terribly efficient, but it's a starting point. Changing an element in a priority queue isn't efficient anyway, because you first have to <em>find</em> it.</p></li> </ul> <hr> <p>Even without these changes the algorithm does find a path, just not the best path. You can see it in the mentioned mazes:</p> <ul> <li><p>In the <code>crazy</code> maze in the third inner circuit: the taken upper path around is slightly longer than the lower path would have been because of the obstacles on the left.</p></li> <li><p>In the <code>big</code> maze in the upper-right part of the path there's an unnecessary loop up.</p></li> </ul> <hr> <p>Since this was on my mind, I implemented my own version of the algorithm and posted it in an answer to your <a href="https://stackoverflow.com/questions/5112111/a-search-algorithm-in-php/5169905#5169905">previous question</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload