Problem 83 of Project Euler is the natural continuation of Problem 81 and 82 which we have already solved. The problem reads
NOTE: This problem is a significantly more challenging version of Problem 81.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.
131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331 Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.
The main difference between this and the previous problems is that we can’t use dynamic programming here since we cannot make smaller sub problems since we can move in any direction. So we need to look into something else, here a path finding algorithm would be the obvious choice.
Looking into that kind it seems that A is the industry choice at the moment. I like to explain the algorithms to you, but in case of A I must admit that I have read this introduction to the A* algorithm and realised that there is no way I can do it better. So before proceeding I would suggest that you follow the link and read through. Don’t forget to come back though.
Ok, so you are back? Just one more note, when I searched for the planning algorithm I came across this rather interesting book call C# Game Programming As you will know by now the A* relies on heuristics so lets look briefly into my choice of Heuristics.
Heuristics
We need a best guess for how far the there is from a square to the goal. This guess has to be smaller than or equal to the real length. So the approach I took was to find the minimal value of the matrix and multiply that by the number of squares that we have to move in order to get to the goal. That way we do fulfil the requirements of the heuristics, and I don’t see a way to improve it.
For the 5×5 example the H matrix would look something like this
162 144 126 108 90 144 126 108 90 72 126 108 90 72 54 108 90 72 54 36 90 72 54 36 18
The open and closed lists
The difficult part of the algorithm as I see it is keeping track of the open list such that we always investigate the square with the most potential.
I did two things to keep track of the open list. The most important of them was to use a SortedList where the key is the F value of the square and the value is a tuple with the x and y coordinates. There is one small issue with that, since keys have to be unique. So in order to ensure that there were no similar keys I made the key a tuple with the first entry being the F value and the second being an integer to make it unique. I am sure this is not the fastest way, but it works for this problem.
The second thing I did was for speedup. I have to maintain a closed list, which I started by making a bool matrix and setting them to true when I closed a square. In the final implementation I changed it to an integer array such that 0 means unexplores, 1 means in the open list and 2 means in the closed list. That way I only had to access the open list to update a square if it was in the open list and that was quite a speed up.
Implementing A*
I don’t think there is too much to say about the implementation that we haven’t already been through. So here is the code
//init arrays int minval = readInput(filename); int gridSize = grid.GetLength(0); int[,] g = new int[gridSize, gridSize]; int[,] h = new int[gridSize, gridSize]; int[,] searched = new int[gridSize, gridSize]; SortedList, Tuple> openList = new SortedList, Tuple>(); for (int i = 0; i < gridSize; i++) { for (int j = 0; j < gridSize; j++) { h[i, j] = minval*(2*(gridSize-1)+1-i-j); g[i, j] = int.MaxValue; } } //Add the start square g[0,0] = grid[0,0]; openList.Add(new Tuple(g[0, 0] + h[0, 0],0), new Tuple(0, 0)); while (searched[gridSize-1, gridSize-1] < 2) { Tuple current = openList.ElementAt(0).Value; openList.RemoveAt(0); int ci = current.Item1; int cj = current.Item2; searched[current.Item1, current.Item2] = 2; //Check the four adjacent squares for (int k = 0; k < 4; k++) { int cinew = 0; int cjnew = 0; switch (k) { case 0: //Check the square above cinew = ci - 1; cjnew = cj; break; case 1: //Check the square below cinew = ci + 1; cjnew = cj; break; case 2: //Check the square right cinew = ci; cjnew = cj+1; break; case 3: //Check the square left cinew = ci; cjnew = cj -1; break; } if (cinew >= 0 && cinew < gridSize && cjnew >= 0 && cjnew < gridSize && searched[cinew, cjnew] < 2) { if (g[cinew, cjnew] > g[ci, cj] + grid[cinew, cjnew]) { g[cinew, cjnew] = g[ci, cj] + grid[cinew, cjnew]; if(searched[cinew, cjnew] == 1){ int index = openList.IndexOfValue(new Tuple(cinew, cjnew)); openList.RemoveAt(index); } int l = 0; while(openList.ContainsKey(new Tuple(g[cinew, cjnew] + h[cinew, cjnew],l))) l++; openList.Add(new Tuple(g[cinew, cjnew] + h[cinew, cjnew],l), new Tuple(cinew, cjnew)); searched[cinew, cjnew] = 1; } } } }
Wrapping up
The code for this A* algorithm is rather specific for this exact problem and probably not very robust. But it is a sample implementation of an algorithm which I consider very strong. When we run the algorithm it gives us the following result
In the 80x80 grid the min path is 425185 Solution took 26,1002 ms
So it is significantly slower than the dynamical programming. However, it can likely be faster if we employ binary heaps as suggested in the tutorial.
The full source code for this problem is found here. How did you solve the problem, and if you used the A* algorithm did you find a better implementation technique?
I used Dijkstra’s algorithm. I think it’s more fitting here, since I can’t see how any heuristic would be beneficial for solving this problem.
I do believe that the A* algorithm is Dijkstra’s algorithm without the Heuristics. So if you remove the Heuristics you would be back at Dijkstra’s algorithm. Djikstra’s algorithm seem to empty the whole search space, so with a bit of luck A* should be able to cut of a few notes.
However, for this problem I don’t think there will be much of a difference. That being said I think it is a hugely interesting field to work in. So much fun.
/Kristian
First I did backtracking with recursion, since I never had to traverse a graph in my life before 😀 and never being heard of Dijkstra or so. Using global minimum path-sum(dropping search if current path-sum goes above that) took miserable ten minutes. (and dramatic total 180k visits to nodes)
I got dramatic speed-ups thorough doing Dijkstra multiple times – until none of the path-sums are updated.
Hi
So the global minimum path-sum you mention. Do you search every path basically, and drop them once you reach the current minimum? In that case, yes that should take a while.
Hi
I also used Dijkstra’s algorithm, but my heap implementation was wrong. As I was a little desperate, I jumped the heaps and just sorted a list with a quick search algorithm for inserting and deleting. At the end, I also forgot to add the weight on the 1,1 position, so I was about 4,000 low from correct answer.
(just started doing pe problems again after taking a 2 year break that was caused by the frustration of (not) solving #78)
About the heuristic calculation: a better and more accurate estimation of the minimal cost from a given node to the end is to take the lowest n values of the matrix where n is the minimum distance, and then add them together. So the heuristic matrix for the example matrix would look like:
767 617 486 365 254
617 486 365 254 151
486 365 254 151 55
365 254 151 55 18
254 151 55 18 0
Using this heuristic, I get the solution in 939ms. I’m not sure if the different heuristic is responsible for the performance improvement, but it’s the only obvious difference I could see. Note that I am caching the heuristic for each distance so they only need to be calculated once.
It makes sense to improve the heuristics like that, you could try to use both heuristics to see if you get a performance difference. It would be an interesting comparison.
I have used Dijkstra too. Considered the matrix to be a graph of size n * n . The edge cost for (u, v) is matrix[ln, col], where ln = u/n and col = u%n and v is a neighbor in the matrix (4 values at most, (ln+-1)*n + col, ln*n + col+-1).
I tried to convert your code to C++. I admit I was so lazy to rewrite 🙂
Due to differences between C# and C++, it didn’t work.
So I decided to implement from scratch.
It’s a Dijkstra derivative since I don’t care about heuristics. And since the path itself is irrelevant, nodes don’t have parent nodes.
It seems pretty fast, finding correct answer in ~0.6 ms (only dijkstra part, reading input file is not included).
If anyone is interested, here is the code: http://pastebin.com/FjbuGrbU
I agree that A* is a very strong minimum-path tactic, but not very suitable for this problem with a relative small grid (only 1600 nodes) without any uncertainty. Which translates to: no uncertainty -> no heuristics needed (imo)
For my C# solution I (too) used Dijkstra, which ran in 8 ms.
Source at https://gist.github.com/anonymous/68dc59a289fcc20abc5b
Hi your link for the explanation is broken,
This one works
http://www.policyalmanac.org/games/aStarTutorial.htm