StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POA* Admissible Heuristic for die rolling on grid
text
Body
copied!<p>I need some help finding a good heuristic for the following problem:</p> <blockquote> <p>You are given an <strong><code>R</code></strong>-by-<strong><code>C</code></strong> grid and a six-sided die. Let <strong><code>start</code></strong> and <strong><code>end</code></strong> be two distinct cells on this grid. Find a path from <code>start</code> to <code>end</code> such that the sum of the faces of the die looking up, as the die is turning along the path, is minimal.</p> <p>The starting orientation of the die is the following (the "2" is facing south):</p> <p><img src="https://i.stack.imgur.com/4gMMs.jpg" alt="enter image description here"></p> </blockquote> <p>The way I modeled this problem is by considering the value of the die's face as the cost of an edge in a graph. The graph's vertices are of the form <code>(row, col, die)</code> (i.e, a position in the grid and the current state/orientation of the die). The reason a vertex is not simply <code>(row, col)</code> is because you can end up on the same cell with multiple configurations/orientations of the die.</p> <p>I used A* to find the solution to the problem; the answers given are correct, but it is not efficient enough. I've determined that the problem is the heuristic I'm using. Currently I'm using Manhattan distance, which is obviously admissible. If I multiply the heuristic with a constant, it's no longer admissible: it runs much faster but it doesn't always find the right answer.</p> <p>I need some help in finding a better heuristic than Manhattan distance.</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