StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The thing with the <strong>A*</strong> algorithm is that it is <em>complete</em> and <em>optimal</em>. That means that it will find a path to the solution if a path exists but also, that it is guaranteed to find the shortest path first.</p> <p>That is because the heuristic function A* uses must be an <a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm" rel="nofollow">admissible heuristic; that is, it must not overestimate the distance to the goal.</a></p> <p>This in turn ensures that <em>as soon as</em> you find a path to the solution, you <em>know</em> that there are no paths shorter than that one in the rest of the search space.</p> <p>Let's say that the distance to your first solution was <em>d(problem)</em>. Now, my last statement actually means, if you just keep going after you find the first solution <em>d(problem)</em>, and find another solution, <em>d2(problem)</em> there are two possibilities:</p> <ul> <li><em>d2(problem)</em> = <em>d(problem)</em> : you want to keep that one since you want <em>all</em> the optimal paths. Also, all new paths can be equal to or larger than <em>d2</em> = <em>d</em></li> <li><em>d2(problem)</em> > <em>d(problem)</em> : now, the same thing I wrote above is valid: there are no paths <em>shorter</em> than <em>d2</em> anymore. And, <em>d2</em> is already longer than the solutions you are looking for. So, you can discard <em>d2</em> and finish your search</li> <li><strong>note</strong> that there <strong>is no third option</strong>, <em>d2(problem)</em> can never be shorter than the optimal <em>d(problem)</em> you already found because that is one of the basic properties of the algorithm.</li> </ul> <p>So, to summarize: you just keep going after you find the <em>first</em> optimal solutions, and you accept all the solutions that are of the same distance. First path that has a worse (longer) distance, you discard and stop your search.</p> <hr> <p>I just saw the "clockwise" part of the question. You can probably avoid searching for <em>all</em> the optimal solutions by somehow inserting the <em>clockwise</em>-ness in to your heuristic or your cost function. E.g. a trick I've been using sometimes is: you have your cost as an integer number, going from 0 to <em>inf</em>. And then, you add the clockwise-ness component, that can have <em>real</em> values from the interval <em>[0, 1)</em> . This way, wherever it was true <code>a > b</code> before, it will stay so, but the relation <code>a == b</code> might be changed if the clockwise-ness component is different.</p> <p>A different way you can compare, if you do not explicitly want to work with a numeric value, is to have the cost be a <em>pair</em> of values. If the first component of the pair is different in two path costs, you just compare those. If the first components are the same, only then you compare the second values in the pairs.</p> <p>That said, off the top of my head, I am not sure if I would advise you to modify your cost or your heuristic function (or both). Also, I'm not sure if this precise trick will work in your problem, but I believe that you should be able to stir the algorithm towards the most clockwise solution just by modifying one of these functions if you just play a little.</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