Finding highest scoreing path
Author
Ok I'm having a problem trying to figure out how to solve this, well other then going at it with brute force. The problem is I have an 8x8 grid of random numbers, each number is randomly generated from 1 to 9. I need to find the best path from left to right, allowing for diagonal moves, that generates the highest score. You can only move to a new square if it is touching the square you are in. I was able to do this by brute force calculations but I'm stuck trying to figure it out without doing so. I've been thinking that I could do something like this:
Calculate the score of all moves in the first two columns ( there would be 22 posabilites), then take the top 10 paths and only calculate the score of the next 2 boxes that are accessible from this first row. Repeat again for the next 2 boxes until you get a full path. Is there anything wrong with this logic? Or could anyone suggest a better way?
I think with that logic you might miss a path that sucked in the first two columns but was awesome in the next eight. :-/ (If I understand the problem correctly.)
Though I can't think of a non-brute-force way to do it offhand.
Though I can't think of a non-brute-force way to do it offhand.
A shortest-path algorithm like Dijkstra's algorithm should do the trick. You can think of the numbers on the cells as edge costs. In contrast the the normal use case you would try to maximize the path cost not minimize it.
Edit: On second thought, this will propably not work. But a "longest path" algorithm should work.
Edit: On second thought, this will propably not work. But a "longest path" algorithm should work.
Author
I was looking into longest path but I'm not sure that would work. Here is an example (i used brute force to solve this)
Quote:Original post by Deaken FrostYou sure it wouldn't? I would think that Dijkstra's algorithm would work fine for this...then again, it's been years since I've had to do it.
A shortest-path algorithm like Dijkstra's algorithm should do the trick. You can think of the numbers on the cells as edge costs. In contrast the the normal use case you would try to maximize the path cost not minimize it.
Edit: On second thought, this will propably not work. But a "longest path" algorithm should work.
Possibility one: dynamic programming.
Possibility two: dijkstra.
The first is easier and faster, but it's more difficult to find info about it online. Both find an optimal result.
Possibility two: dijkstra.
The first is easier and faster, but it's more difficult to find info about it online. Both find an optimal result.
I like this method, of course, you have to modify it to include path information, but it's probably less code than implementing dijsktras algorithm
public static void GetHighestScore(int[,] array) { for (int x = 0; x < N_ROW; ++x) { GetHighestScore(array, x, 0, 0); } } private static int highestVal = 0; public static void GetHighestScore(int [,] array, int row, int col, int scoreOnThisPath) { if (row >= N_ROW || row < 0) { return; } if(col >= N_COL) { if(scoreOnThisPath > highestVal) { highestVal = scoreOnThisPath; } return; } GetHighestScore(array, row, col + 1, scoreOnThisPath + array[row, col]); GetHighestScore(array, row+1, col + 1, scoreOnThisPath + array[row, col]); GetHighestScore(array, row - 1, col + 1, scoreOnThisPath + array[row, col]); }
Author
Yes, but you are solving it by brute force, I want to know how to solve it without having to figure every path.
Oh, i thought you just wanted a nice looking brute force algorithm. But yeah you would have to implement dijsktras algorithm and go through the trouble of looping through the whole thing in order to make it into a graph.
If it was really 8x8 there is no problem with doing brute force, the time difference wont even be noticeable
If it was really 8x8 there is no problem with doing brute force, the time difference wont even be noticeable
Author
It is only 8x8. I have no problem solving it using brute force but I want to do it without having to calculate every path. Oh and I tried your alogrithm and it did not solve it correctly.
Edit:
I don't want to use dDijsktras, so I'm thinking something like this:
Calculate the 22 combinations for the first 2 columns, the second 2, third 2, and fourth 2.
Go through the first 2 columns and take the combinations with a score of 10 or more.
Look into the next 2 columns and find the possible combinations where its score is 10 or more and add to the previous column, repeat till u hit the end.
Edit:
I don't want to use dDijsktras, so I'm thinking something like this:
Calculate the 22 combinations for the first 2 columns, the second 2, third 2, and fourth 2.
Go through the first 2 columns and take the combinations with a score of 10 or more.
Look into the next 2 columns and find the possible combinations where its score is 10 or more and add to the previous column, repeat till u hit the end.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement