Re: a chessboard type problem

On May 4, 1:07 pm, maxfla...@xxxxxxxxx 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

I think you should use Floyd-Warshall algorithm which finds the
shortest weighted path between every possible pair of nodes in a
weighted directed graph that has no "negative dicycles". Since your
pawn in always moving forward, there are no cycles at all, and in
particular there are no directed cycles with a total negative weight.
This should run in polynomial time on the order of n^6.

To set up the problem: Consider each square on the chess board as a
node in a graph with one directed edge representing each legal move.
Now add one additional "start" node (corresponding to the location of
the pawn before you place it on the board) and edges directed from the
start node to each of the first rank nodes. No weight each edge with
the negative of the weight of the square corresponding to the end of
the edge (the square the pawn in entering). You need to use the
negatives of the weights since the algorithm finds the minimal path
and you want the maximal one. Alternatively you could adjust the
algorithm itself to maximize. Now you can run the Floyd-Warshall
Algortihm which is described nicely with psuedocode on wikipedia
(http://en.wikipedia.org/wiki/Floyd-Warshall_algorith). You result
will give you the shortest path for each pair. The pairs you care
about from the start node to one of the last rank nodes. You could
also add an "end" node with edges directed from each last rank nodes
into the end node. Then the overall best path will be given by the
best path from the start to the end.

If you want to know the best path starting with a particular node you
will need to add the "end" node and weight the edges with the negative
of the square you are leaving, or add one node with one edge into each
of the first rank nodes.

-Hope this helps.

.

Relevant Pages

  • Re: a chessboard type problem
    ... algorithm would be great. ... particular there are no directed cycles with a total negative weight. ... Consider each square on the chess board as a ... about from the start node to one of the last rank nodes. ...
    (comp.theory)
  • Re: the "hat" container class [C++]
    ... Craig Nicol wrote: ... I notice however that your selection algorithm ... I store the cumulative chances. ... according to their weight. ...
    (comp.programming)
  • Re: What I learned from Class Viewer
    ... displaced by such a trivially easy algorithm? ... by simply assuming that the weight is a distance between nodes ... while is not a valid circuit as a node is omitted. ...
    (comp.lang.java.programmer)
  • Re: Finding longest path in graph between two vertices
    ... a topological sort and than a relaxation to find the critical path ... Bellman-Ford Algorithm (due to the weight negation it should find not ... DAG shortest path algorithm (which for each topologically sorted vertex ...
    (sci.math)
  • Re: COMPLEX VALUED NEURAL NETWORK
    ... % Weight initialization stage ... ; % hidden activaton unit ... SquaredOfTheError; % sum of the square of the error ... (HiddenOutput) ...
    (comp.soft-sys.matlab)