Ask the algorithm to find the N shortest path of the global knight

Question

I'm fixated on a curious issue.

I have an unlimited chessboard, N knights, starting locations and N target locations.

The challenge is to find the minimum number of moves for all knights to get to all target locations.

I know that the shortest path problem for one knight can be solved with a breadth-first search, but how can it be solved for several knights?

Sorry for my English, I rarely use it.

Answer 1

I assume that you know how to do this for one Knigt.

You can reformulate your problem as a linear program:

I will use the following notation:

We have N knights and N en places.

xij = 1 if you chose knight i to go to location j and 0 otherwise

cij - minimum length of a moving knight i to location j

Then you have the following linear program:

Variables

xij for i j in [0, N]

Cost function:

C = SUM (cij.xij for (i, j) in [0, N] x [0, N])

<strong> limitations:

SUM (xij for j in [1, N]) = 1 // exactly one knigt goes from i to j

SUM (xij for i in [1, N]) = 1

(The matrix (xij) is a stochastic matrix)

if X is a matrix (xij), you have n! possible matrix. This problem may be (there is no simple solution to this system, the system solution is quite similar to testing all possible solutions).

---

EDIT:

This problem is called the assignment problem and there are many algorithms for solving it in polynomial time. (see @purav example for an example)

As @Purav mentioned, although such problems can be NP-hard, in this case it can be solved in O (n ^ 3)

---

---

---

About the problem @j_random_hacker raised:

Problem

If the knight is at the endpoint, the following knights should not go through this endpoint. Therefore, Cij may need to be updated after each knight moves.

Notes:

1. several optimal ways:

Since there are no restrictions on the side of the chessboard (limited chessboard), the order in which you make your move to achieve the shortest path is irrelevant, therefore there is always a lot of other shortest path (I won’t combinatorics here).

An example with two knights

Say you have 2 K and 2 endpoints ('x'), the optimal path extends.

  -x | | x | K-- --K 

you move the right K to the first point (1 step), the second cannot use the optimal path.

  -x | | K | K-- --: 

But I can easily create a new optimal path, instead of moving 2 from the right 1 up, then 2 up 1 to the right. 1 can move 2 up 1 right 1 up 2 right (just the opposite)

  --K | - | K | | : --: 

and any combination of paths works:

1 U 2 R, then 2 U 1 R, etc .... while I keep the same number of UP LEFT DOWN and RIGHT moves and that they are valid.

2. Knights moving order:

Secondly, I can choose the order of my movement.

Example:

with the previous example, if I decided to start with the left knight and go to the upper end point, you no longer need to limit the end point.

  -K | | x | :-- --K -K | | K | :-- --: 

With these two remarks, one could prove that there is no situation where the calculated lower bound is not optimal.

Answer 2

You can calculate the cost matrix suggested by Ricky using the first width search. so now the cost [i] [j] means the cost of choosing knight i for final location j. Then you can use the Hungarian algorithm to find the final answer that can be calculated in complexity O (N ^ 3).

Answer 3

BFS can still work here . You need to tweak your states a bit, but it will still work:

let S be the set of possible states:
S={((x1,y1),(x2,y2),...,(xn,yn))|knight i is in (xi,yi)}

For each s of S, determine:
Successors(s)={all possible states, moving 1 knight on the board}

Your target states are, of course, all permutations of your target points [you really do not need to develop these permutations, just check if you have reached a state in which all the squares are filled, which is easy to check]

start=(start_1,start_2,...,start_n) where start_i is the starting location of knight i.

Starting BFS from start [the starting position of each knight] is guaranteed to find a solution if it exists [since BFS is complete ]. It is also guaranteed as the shortest possible solution.

(*) Note that the case for single knight is a particular instance of this solution , with n = 1.

Although BFS will work, it will take a long time! the branching coefficient is 4n here, so the algorithm will need to develop the vertices O((4n)^d) , where n is the number of knights, and d is the number of steps needed to solve.

Possible optimizations:

• Space: Note that since BFS uses a lot of memory [ O((4n)^d) ], you may want to use Iterative Deepening DFS , which behaves like BFS, but consumes much less memory [ O(nd) ], but takes up more time to run.
• Time . To speed up the search for a solution, you can use the Star with a valid heuristic function . In addition, the solution, if it exists, also ensures that the solution found is optimal, and probably [with good heuristics] it is necessary to develop fewer vertices, then BFS.

Answer 4

So, I have found a solution.

BFS will not work on an unlimited chessboard. It makes no sense to use the shortest path algorithm - the number of knights moving from location a to location b can be calculated O (1) times - M. Deza, Dictionary of Distance, p. 251

http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW

The assignment problem can be solved using the mincost-maxflow algorithm (for example, Edmonds-Karp):

http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm