On May 4, 11:16 pm, max <[EMAIL PROTECTED]> wrote:
> Say you have an n*n "chessboard" where each square is associated with
> a real number (pos or neg). You want to navigate from one side to the
> other by either moving one space ahead or one space ahead and one
> space to the side (either side). I need an relatively efficient
> algorithm that will optimize the path so that the sum of the values of
> the squares that are touched is maximized. An easy to implement
> algorithm would be great.
>
> Thanks in advance.
> Max
This looks like a dynamic programming problem. For each cell, where
row=j
and col=i, the only possible ways of reaching it are from (i-1,j-1),
(i-1,j)
and (i,j+1). Thus the maximum value of reaching that cell is
value[i][j], if i == 0
value_of(i,j) = value[i][j] + max( value_of( i-1, j-1),
value_of( i-1, j), value_of( i-1, j+1), otherwise
Now you can determine the maximum possible value to reach each cell,
and the
highest valued cell to be reached in the last coloumn is the answer.
Hope this helps.
Muntasir
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
