Shortest cost path

Question

I have to find the shortest path from point D to R. These are fixed points. This is an example of a situation:

The box also contains walls, through which you cannot pass across them, unless you break them. Each wall break costs you, let's say "a" points, where "a" is a positive integer. Each move which doesn't involve a wall, costs you 1 point.

The mission is to find out of all the paths of minimum cost, the one with the least number of broken walls.

Since, the width of the box can go up to 100 cells, it's irrelevant to use backtracking. It's too slow. The only solution I came up is this one:

1. Go east or south if there are no walls
2. If south has a wall, check if west has wall. If west has wall, break south wall. If west doesn't have wall, go west, until you find a south cell without wall. Repeat this process with south and east until you exceed the cost of a broken wall in this order. If path from west goes into the same place as if I had broken the south wall and costs the same or less than "a" points, then use this path, else brake south wall.
3. If nothing above encounters, brake a south or east wall, depending on the box boundary.

Repeat steps 1, 2, 3 till the "passenger" arrives in point R. Between these 3 steps, there are "else-if" relations.

Can you come up with a better problem algorithm? I program in C++.

Answer 1

Use Dijkstra, but for costs give it 1 for a move that doesn't break a wall, and (a+0.00001) for breaking a wall. Then Dijkstra will give you what you want, the path that breaks the fewest walls among all minimal-cost paths.

Conceptually, imagine a traveler who can jump over walls -- while keeping track of the cost -- and can also split into two identical travelers when faced with a choice of two paths, so as to take them both (take that, Robert Frost!). Only one traveler moves at a time, the one who has incurred the lowest cost so far. That one moves, and writes on the floor "I reached here at a cost of only x". If I find such a note already there, if I got there more cheaply I erase the old note and write my own; if that other traveler got there more cheaply I commit suicide.

Answer 2

The two-part "cost first, then broken walls", can be represented as a pair (c, w) that is compared lexicographically. c is the cost, w is the number of broken walls. That makes it a "single thing" again (in some sense), so it's a thing that you can put into algorithms and so on that expect simply "a cost" (as an abstract thing that it may add an other cost to or compare to an other cost).

So we can just use A*, with a Manhattan Distance heuristic (perhaps there's something smarter that doesn't ignore walls completely, but this will work - underestimating the distance is admissible). The movement cost will, of course, not ignore walls. Neighbours will be all adjacent squares. All costs will be the pair I described above.

Answer 3

This could easily be modeled as a weighted graph and then apply Dijkstra's shortest path algorithm to it. Each square is a node. It is connected to the nodes of the squares it is adjacent to. The weight of the connections is either 1 or "a", based on whether there is a wall or not. This will get you the minimal cost. It's possible that the minimum cost and the minimum number of wall breaks could be different.

Answer 4

Here is a general algorithm (you'll have to do the implementation yourself):

Convert the matrix into a weighted graph:

• For each entry in the matrix, create a Vertex.
• For each Vertex, create an array of Edges, one for each neighboring Vertex.
• For each Edge, define a weight according to the cost of breaking the wall between the two Vertices that the Edge is connecting.

Then, run the Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) on the graph, starting from Vertex D. As an output, you will have the shortest (cheapest) path from Vertex D to any other Vertex on the graph, including Vertex R.