Re: a chessboard type problem
- From: Babua <pinaki@xxxxxxxxxxxxx>
- Date: 6 May 2007 00:12:29 -0700
On May 6, 4:39 am, Yeyui <danielwe...@xxxxxxxxx> wrote:
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.
Since the graph is a DAG we can perform the computation much faster
than using Floyd & Warshall here if we perform topological sorting.
Subsequently single source shortest path can be computed in O(|V| + |
E|)
time. [Johnson] Here |V| = |E| = O(n^2). So all pair shortest path can
be
computed in O(n^4) time.
In the graph with negated edge weights the longest path problem
reduces
to the shortest path computation and can be solved in the same time
complexity.
Thanks.
--- Pinaki
============================================================
.
- Follow-Ups:
- Re: a chessboard type problem
- From: Patricia Shanahan
- Re: a chessboard type problem
- References:
- a chessboard type problem
- From: maxflat83
- Re: a chessboard type problem
- From: Yeyui
- a chessboard type problem
- Prev by Date: Re: a chessboard type problem
- Next by Date: Re: a chessboard type problem
- Previous by thread: Re: a chessboard type problem
- Next by thread: Re: a chessboard type problem
- Index(es):
Relevant Pages
|
