Sign in to follow this  
xDS4Lx

Finding highest scoreing path

Recommended Posts

xDS4Lx    126
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 this post


Link to post
Share on other sites
discman1028    212
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 this post


Link to post
Share on other sites
Deaken Frost    133
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 this post


Link to post
Share on other sites
xDS4Lx    126
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)
Photobucket

Share this post


Link to post
Share on other sites
EdR    117
Quote:
Original post by Deaken Frost
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.
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 this post


Link to post
Share on other sites
ToohrVyk    1596
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 this post


Link to post
Share on other sites
ginkeq    133
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 this post


Link to post
Share on other sites
ginkeq    133
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 this post


Link to post
Share on other sites
xDS4Lx    126
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.

Share this post


Link to post
Share on other sites
ginkeq    133
works for me, this one is cleaned up and calculates paths

[sourcelang ="C#"]

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
public class ColRow
{
public ColRow(int col, int row)
{
this.col = col;
this.row = row;
}
public int col;
public int row;
}

internal class Program
{
public const int N_ROW = 8;
public const int N_COL = 8;

private static void Main(string[] args)
{

int[,] someArray = new int[N_ROW, N_COL]
{
{6, 1, 6, 2, 3, 4, 1, 1},
{4, 1, 1, 8, 3, 8, 3, 2},
{5, 1, 1, 5, 3, 3, 9, 4},
{5, 8, 6, 5, 1, 2, 1, 6},
{4, 9, 7, 5, 3, 6, 4, 4},
{9, 6, 5, 8, 6, 1, 7, 7},
{2, 5, 3, 1, 1, 6, 3, 9},
{4, 1, 4, 8, 9, 8, 1, 3}
};
ArrayList bestPath = GetHighestScore(someArray);
}


public static ArrayList GetHighestScore(int[,] array)
{
ArrayList moves = new ArrayList();
for (int x = 0; x < N_ROW; ++x)
{
int savedVal = highestVal;
ArrayList l = GetHighestScore(array, x, 0, 0);
if(highestVal > savedVal)
{
moves = l;
}
}
moves.Reverse();
return moves;
}

private static int highestVal = 0;


public static ArrayList GetHighestScore(int [,] array, int row, int col, int scoreOnThisPath)
{
if (row >= N_ROW || row < 0)
{
return null;
}
if(col >= N_COL)
{
if(scoreOnThisPath > highestVal)
{
highestVal = scoreOnThisPath;
ArrayList path = new ArrayList();
path.Add(new ColRow(col, row));
return path;
}
return null;
}
ArrayList l1 = GetHighestScore(array, row, col + 1, scoreOnThisPath + array[row, col]);
ArrayList l2 = GetHighestScore(array, row + 1, col + 1, scoreOnThisPath + array[row, col]);
ArrayList l3 = GetHighestScore(array, row - 1, col + 1, scoreOnThisPath + array[row, col]);
if(l3 != null)
{
l3.Add(new ColRow(col, row));
return l3;
}
if(l2 != null)
{
l2.Add(new ColRow(col, row));
return l2;
}
if(l1 != null){
l1.Add(new ColRow(col, row));
return l1;
}
return null;
}
}
}









[Edited by - ginkeq on April 19, 2008 5:05:10 PM]

Share this post


Link to post
Share on other sites
iMalc    2466
I think the main thing is to not calculate the cost of getting to each square more than once.
For any given column the best path to a particular cell is either from diagonally above to that cell, or from directly to the left to that cell, or from diagonally below to that cell. If you have stored the results for all columns to the left already, then you can choose the best amoungst those two or three answers and provide a best path answer for that cell. The next row can then use that cached value for some of its calculations.

So, just calculate and cache the best path to each cell of row 1 (a no brainer) and using the results of row n-1, calculate and cache the best path to the cells of row n.
So all you need is an 8x8 array of lists.

Some code, untested and unoptimised, but it illustrates the idea:
typedef std::pair<int, int> cell;
typedef std::list<cell> path;

path findBestpath(int grid[8][8])
{
path moves[8][8];
int totals[8][8] = {0};
// Set up values and paths for the first column
for (int y=0; y<8; ++y)
{
totals[0][y] = grid[0][y];
moves[0][y].push_back(cell(0, y));
}
// Calculate paths and values for subsequent columns
for (int x=1; x<8; ++x)
{
for (int y=0; y<8; ++y)
{
int bestPos = y;

if (y > 0 && totals[x-1][y-1] > totals[x-1][bestPos])
bestPos = y-1;

if (y < 7 && totals[x-1][y+1] > totals[x-1][bestPos])
bestPos = y+1;

totals[x][y] = totals[x-1][bestPos] + grid[x][y];
moves[x][y] = moves[x-1][bestPos];
moves[x][y].push_back(cell(x, y));
}
}
// Find which path to the right hand column was highest-value
int bestPos = 0;
for (int y=1; y<8; ++y)
{
if (totals[7][y] > totals[7][bestPos])
bestPos = y;
}
return moves[7][bestPos];
}

Of course the first thing you'd do to optimise this is to not store the full path at each point, but instead store the y value of the cell to the left from which you came from in each cell. The path can then be reconstituted by following this backwards from the end. Or you could solve it right to left and then extract the path forwards from the left.
It would then be O(n*m) for a grid of size n*m.

[Edited by - iMalc on April 19, 2008 5:23:59 PM]

Share this post


Link to post
Share on other sites
EdR    117
Quote:
Original post by xDS4Lx
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.
That's not going to be remotely as efficient as Dijkstra's algorithm.

Share this post


Link to post
Share on other sites
xDS4Lx    126
Quote:
Original post by Edward Ropple
Quote:
Original post by xDS4Lx
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.
That's not going to be remotely as efficient as Dijkstra's algorithm.


As long as its better then brute force I don't care. I've looked at Dijkstra's and just don't understand how it applies to this, since its used to calculate the distance between points. If you could explain it better then what I've found on google using "djikstra's algorithm" as a search id be most appreciative.

Share this post


Link to post
Share on other sites
swiftcoder    18437
Quote:
Original post by xDS4Lx
I need to find the best path from left to right, allowing for diagonal moves, that generates the highest score.
Obviously no one else has been confused by your problem description, but this statement seems very vague to me.

What is the 'best' path that maximises the score? By my reckoning, the path with the highest score is the path that visits all squares once, and the 'best' path is the horizontal path across the centre. Are you just trying to find a trade-off between the two, or am I missing something here?

Share this post


Link to post
Share on other sites
xDS4Lx    126
You have to start in the left most column and travel to the right most column. You can only move from left to right, but you can go diagionaly up and down to the right or just plain to the right, you cant go to 2 squares in the same column and you can only move to squares that touch each other. Look at the image i posted.

Share this post


Link to post
Share on other sites
kiwibonga    183
Go through each node in the leftmost column one by one... For each node, do a depth-first search, and store the sum of the longest possible branch for each node.



The first image is what you have to calculate for the first node. The second image is what you have to calculate for the second node... The third image is what you actually have to calculate for the second note if you simply keep track of what was already visited.

This is probably the best way to optimize this. You'll only need to make a temporary table that has as many elements as the "play area" ; each node in it will have to store a sum of the node weights from the "heaviest branch" coming out of it and a pointer to the next node along that heaviest branch.

Share this post


Link to post
Share on other sites
ginkeq    133
Quote:
Original post by xDS4Lx
Quote:
Original post by Edward Ropple
Quote:
Original post by xDS4Lx
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.
That's not going to be remotely as efficient as Dijkstra's algorithm.



As long as its better then brute force I don't care. I've looked at Dijkstra's and just don't understand how it applies to this, since its used to calculate the distance between points. If you could explain it better then what I've found on google using "djikstra's algorithm" as a search id be most appreciative.


Attach 2 extra nodes, one node would connect to every beginning column, and have a weight of 0, and another would be hooked onto the last column with a weight of
0.

Then you could call dijkstra with the last column node, and it would store the weights. Rather than looking at the lowest weights, you would want to follow the highest weights and that would be the optimal path.

Share this post


Link to post
Share on other sites
xDS4Lx    126
But all these suggestions are still brute force. The programmer who told me to solve this says their is a O(n) solution. I'm now thinking that this is going to require solving for the first 4x8 section and then finding those paths that connect in the second 4x8 to the highest paths in the first section.

Share this post


Link to post
Share on other sites
iMalc    2466
Okay, everybody that has posted since my post above need to go back and re-read it. It is in fact the asymtopically optimal solution you are looking for.

Let me clarify a few things here:
There is an O(n) solution to this problem if you take n to be the number of cells, NOT if you take n to be the number of columns only. I broke that O(n) answer down into O(x * y) where x and y are the number of cells horizontally and vertically, where x*y = n. If you apply the optimisation I mentioned at the end, then it is the O(n) solution you've been told about.

The only furthur improvement you could add to it is to use an A* approach where you consider the current best paths first. This however might not always mean less checking nodes, and would likely still end up taking as long.

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by kiwibonga
Isn't the solution I gave O(n)?

EDIT: Did I basically repeat what iMalc said with a nice mspaint picture and vague explanation? lol :P
Actually you're right, you are describing the same thing as me.

Here's a working program showing it, after applying the optimisations I spoke of:
#include <list>
#include <iostream>

#define N_COL 8
#define N_ROW 8

const int grid[N_ROW][N_COL] = {
{6, 1, 6, 2, 3, 4, 1, 1},
{4, 1, 1, 8, 3, 8, 3, 2},
{5, 1, 1, 5, 3, 3, 9, 4},
{5, 8, 6, 5, 1, 2, 1, 6},
{4, 9, 7, 5, 3, 6, 4, 4},
{9, 6, 5, 8, 6, 1, 7, 7},
{2, 5, 3, 1, 1, 6, 3, 9},
{4, 1, 4, 8, 9, 8, 1, 3}
};

typedef std::pair<int, int> cell;
typedef std::list<cell> path;

path findBestpath(const int grid[N_ROW][N_COL])
{
int totals[N_ROW][N_COL] = {0};
int joins[N_ROW][N_COL] = {0};
// Set up values for the last column
for (int y=0; y<N_ROW; ++y)
{
totals[y][N_COL-1] = grid[y][N_COL-1];
}
// Calculate joins and values for all other columns
// This code was copied from Gamedev.net
for (int x=N_COL-1; x>0; --x)
{
for (int y=0; y<N_ROW; ++y)
{
int bestPos = y;

if (y > 0 && totals[y-1][x] > totals[bestPos][x])
bestPos = y-1;

if (y < N_ROW-1 && totals[y+1][x] > totals[bestPos][x])
bestPos = y+1;

totals[y][x-1] = totals[bestPos][x] + grid[y][x-1];
joins[y][x-1] = bestPos;
}
}
// Find the starting point that had the highest-valued path
// This code was copied from Gamedev.net
int bestPos = 0;
for (int y=1; y<N_ROW; ++y)
{
if (totals[y][0] > totals[bestPos][0])
bestPos = y;
}
// Generate the resulting path
// This code was copied from Gamedev.net
path moves;
moves.push_back(cell(0, bestPos));
for (int x=1; x<N_COL; ++x)
{
bestPos = joins[bestPos][x-1];
moves.push_back(cell(x, bestPos));
}
return moves;
}

int main()
{
path res = findBestpath(grid);
for (path::const_iterator it = res.begin(); it != res.end(); ++it)
{
std::cout << "(" << it->first << "," << it->second << ")" << std::endl;
}
return 0;
}


My previous code had x & y reversed and was calculating the best vertical path, which also appeared to be correct.

So how did you come across this problem?

Edit: Okay I recommend simply googling what Toohrvyk posted earlier. This page contains the problem description and a description matching my solution.

[Edited by - iMalc on April 20, 2008 12:21:07 AM]

Share this post


Link to post
Share on other sites
xDS4Lx    126
Thanks for the link, it helped a lot. The problem was given to me by another programmer at work. Thanks for the help!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this