Select numbers rectangle numbers

Question

I have a pretty big problem with the invention of the algorithm.

I have two groups of nodes. Say we have 4 nodes in the first group and 4 more nodes in the second. The following figure shows the following:

I want to associate nodes from the first group with nodes from the second group. They should be associated with the best tracks. - The length of all routes should be as close as possible , and each node can be connected to only one route. Something like that:

I do not want to do this, as in the following figure, because the routes are very different in length.

The following table shows the lengths between all nodes. And from this table I want to choose the best solution. The best solution is surrounded.

And how can I find the best solution when I have groups with hundreds of nodes? If I try each combination, there will be 100! combinations, and that a lot. I can not come up with any algorithm for this.

Answer 1

As Thomas @ noted in the comments, the solution to the problem depends on your definition of "as close as possible." Let the set of edges in the solution be S Assuming that the definition was chosen so as to minimize max(S) - min(S) (which in practice is a reasonable assumption), then this problem can definitely be solved in polynomial time.

Here is an example solution. For 100 nodes, it only takes a few seconds.

one

First of all, you should know the maximum correspondence problem for bipartite graphs and that it can be solved in a polynomial time. The most straightforward Hungarian algorithm takes O(nm) , in which n is the number of nodes and m is the number of edges. And for the planar graph, which is your case, there are more complex algorithms that can further increase productivity .

Define this as the Max_Match(X) function, which returns the maximum number of matches in the set of edges of X

This Max_Match can be calculated less than O(n^1.5) , in which n is the number of nodes. For n=100 we have only n^1.5 = 1000 .

---

2

Then translate your problem into a maximally matched problem.

We define the set of edges E to all edges that we can choose. In your case, there are n*n edges in E , where n is the number of nodes on one side.

Let us define the function F(E, low, high) = {e | e in E and |e| >= low and |e| <= high } F(E, low, high) = {e | e in E and |e| >= low and |e| <= high } F(E, low, high) = {e | e in E and |e| >= low and |e| <= high } which means the edges of a subset of E whose length is between [low, high]

Then for a given pair of low and high numbers, your problem has a solution if and only if

Max_Match( F (E, low, high)) == n

---

3

However, how do we calculate the low and high values?

The possible values ​​of low and high are all possible numbers in {|e|, e in E} that have numbers n^2 . Therefore, trying all possible combinations of low and high will cost n^4 . It's a lot.

If we already know low , can we define high without listing? The answer is yes. Note:

lemma 1

If for the number h we have Max_Match( F (E, low, h)) == n

Then for any number h' >= h we also have

Max_Match( F (E, low, h')) == n

This means that we can use binary search to determine high after fixing low .

---

4

So, the framework for the final decision:

 arr[] = {|e|, e in E}.sort() for i in range(0, len(arr[])): low = i h_left = i, h_right = len(arr[])-1 while h_left <= h_right: mid = (h_left+h_right)/2 if Max_Match( F( E, arr[low], arr[mid]))==n: h_right = mid - 1 else: h_left = mid + 1 if h_left >= low: if arr[h_left] - arr[low] <= ans: ans = arr[h_left] - arr[low] 

And ans will be the minimum difference between the edges in the solution. This algorithm costs O(n^3.5 * log(n)) , in which n is the number of nodes.

Edit: A simple and ugly implementation of the above algorithm in C ++ can be found at: ideone.com/33n2Tg . Since I don't have much time, I manually developed a simple Hungarian algorithm in this solution, which is slow when n large. To achieve better performance, you will need the algorithm included in Part 1 for planar graphs.

Answer 2

I don't think you can easily figure this out with A *. Also brute force will be O (n!). I think we should use heuristics such as a genetic algorithm.

You can implement a gene with an array (the pointer of point A is connected to the point of value B)

Then you need to create a gene pool with random genes. The number of genes cannot be fixed ... so you need to test a little.

you will need a calculation method:

 float GetLength(int indexA, int indexB) { return sqrt((pointA[indexA].x - pointB[indexB].x) * (pointA[indexA].x - pointB[indexB].x) + (pointA[indexA].y - pointB[indexB].y) * (pointA[indexA].y - pointB[indexB].y)); } 

then you also need a fitness function:

 float Fitness(int gene, int count) { float min = GetLength(0,gene[0]); float max = GetLength(0,gene[0]); for(int i = 0; i< count;i++) { min = std::min(min, GetLength(i,gene[i])); max = std::max(max, GetLength(i,gene[i])); } return max-min; } 

Also you need to connect them:

 int* Crossbreed(int* gene1, int* gene2, int count) { int* geneNew = new int[count]; for(int i = 0; i< count; i++) { geneNew[gene1[i]] = gene2[i]; } return geneNew; } 

Crossbreed returns us children;) who must pass a fitness test. You must also introduce a mutant method that gives us a mutated gene. It is important to leave local max.

In the end, you only need to run this in a loop for some time, and you will get a very good result.

Answer 3

Suppose this table has n rows and m columns. This problem is equivalent to choosing n numbers that are in different rows and different columns from this table, so the sum of these numbers is minimal. We can use dfs to find the whole combination in n! but for this problem we can have an A * search algorithm .

For this problem, the heuristic function h (x) is equal to

The complexity of this A * algorithm is difficult to compute, but it often works well.