Finding highest scoreing path

This topic is 3683 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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?

Share on other sites
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.

Share on other sites
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.

Share on other sites
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)

Share on other sites
Quote:
 Original post by Deaken FrostA 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.
You 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.

Share on other sites
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.

Share on other sites
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]);        }

Share on other sites
Yes, but you are solving it by brute force, I want to know how to solve it without having to figure every path.

Share on other sites
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

Share on other sites
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.

• 10
• 18
• 14
• 19
• 15