0

Suppose you have a n x n gaming board and you have a character that can move like a knight on a chess board except he can't move up or left. And each block he moves to has a value which can be accumulated to his points. The player is trying to maximize points and reach T

I came up with a solution but im wondering where it could fail and its run time.

My idea was to create a directed weighted graph (points as weights) to each possible destination and run Dijkstra's algorithm on the graph, however instead of shortest path, we try and find the longest path.

Picture

I am guessing the run-time would be O (some thing + |E|+|V|log||V|)

Im not sure what something is.

Ali
  • 56,466
  • 29
  • 168
  • 265
RandomGuy
  • 4,949
  • 4
  • 16
  • 15
  • It seems to me that the graph is acyclic, in that case there are fast algorithms: [ref1](http://cs.stackexchange.com/questions/11295/finding-shortest-and-longest-paths-between-two-vertices-in-a-dag) [ref2](http://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph), [ref3](https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths) –  Feb 16 '14 at 04:45
  • The algorithm doesn't work there can be cyclic cases – RandomGuy Feb 16 '14 at 05:07
  • Hm I thought your restriction to down and right movement would make this acyclic. –  Feb 16 '14 at 05:13
  • I'm sorry what I meant to say was it moves like a Knight on chess board black lines on picture but its messing parts of the movement of the knight – RandomGuy Feb 16 '14 at 05:39
  • Sure, got that, but I couldn't find a circle anyway. Maybe I am just missing an obvious case. –  Feb 16 '14 at 05:48
  • Yes you are right it can not come back to a point it has already been, but what would the runtime of graph construction be? – RandomGuy Feb 16 '14 at 06:02
  • Assuming you index the nodes by their position on the field (x,y) then you can get each neighbour for a given node in constant time dynamically, so the runtime of the algorithms should not be affected. –  Feb 16 '14 at 06:08
  • Since there are only types of moves allowed, this seems to be some special case of Bresenham's algorithm (except for the allowed permutations of the X,Y steps) – wildplasser Feb 16 '14 at 15:33

1 Answers1

1

Dijkstra is not good for finding maximum path. In ordrer to find the maximum path you should multiply each edge weight by -1 and it is well known that dijkstra does not operate correctly on graph with negative weight edges. Instead you will need to use Bellman-Ford algorithm. The complexity will then be O(| V | · | E |) as stated in the wikipedia article.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Your answer works, but i think Dijkstra will also work because there will never be a negative edge either. I never thought of multiplying by -1 and finding shortest path, its clever. – RandomGuy Feb 21 '14 at 16:05
  • @RandomGuy if you multiply all edges by `-1` **all** edges will be negative – Ivaylo Strandjev Feb 21 '14 at 16:46