需要更好的算法的研究之间的2点的集合映射与最小距离 [英] Need Better Algorithm for Finding Mapping Between 2 Sets of Points with Minimum Distance

问题描述

问题：我有两个重叠的2D图形，A和B，具有相同的像素数量每个形状，但不同的形状。形状的一些部分是重叠的，并有一些片每个是不重叠的。我的目标是将所有的非重叠的像素的形状A到非重叠的像素在形状B.由于像素中每种形状的数量是相同的，我应该能够找到的1对1映射像素。该限制是，我想找到最小化所有的移动像素移动的总距离映射。

Problem: I have two overlapping 2D shapes, A and B, each shape having the same number of pixels, but differing in shape. Some portion of the shapes are overlapping, and there are some pieces of each that are not overlapping. My goal is to move all the non-overlapping pixels in shape A to the non-overlapping pixels in shape B. Since the number of pixels in each shape is the same, I should be able to find a 1-to-1 mapping of pixels. The restriction is that I want to find the mapping that minimizes the total distance traveled by all the pixels that moved.

蛮力：的蛮力的方法来解决这个问题显然是出了问题，因为我将不得不计算其中我觉得有n所有可能的映射的总距离！ （其中n是不重叠的像素在一个形状的数目）次计算距离的每对点在映射中，n，给出总共为O（n * n个！）或类似的东西的计算。

Brute Force: The brute force approach to solving this problem is obviously out of the question, since I would have to compute the total distance of all possible mappings of which I think there are n! (where n is the number of non-overlapping pixels in one shape) times the computation of calculating a distance for each pair of points in the mapping, n, giving a total of O( n * n! ) or something similar.

回溯：只有更好的解决方案，我能想到的是使用回溯，在那里我会跟踪当前最小的，到目前为止并在任何时候，当我评估一个特定的映射如果我达到或超过最低，我就移动到下一个映射。即使这不会做任何为O更好的（N！）。

Backtracking: The only "better" solution I could think of was to use backtracking, where I would keep track of the current minimum so far and at any point when I'm evaluating a certain mapping, if I reach or exceed that minimum, I move on to the next mapping. Even this won't do any better than O( n! ).

有什么办法来解决这个问题，一个合理的复杂性？

Is there any way to solve this problem with a reasonable complexity?

另外请注意，仅仅映射指向它的明显的方法是最匹配的邻居并不总能取得最佳的解决方案。

Also note that the "obvious" approach of simply mapping a point to it's closest matching neighbour does not always yield the optimum solution.

<强>简单的方法：吗作为第二个问题，如果一个可行的解决方案是不存在，一种可能性可能是分割各非重叠部分为小区域，并映射这些区域中，大大减少了映射关系的数量。要计算两个区域之间的距离，我会用质量（像素位置在该地区的平均值）的中心。然而，这presents如何，我应该去这样做分区，以获得接近最佳答案的问题。

Simpler Approach?: As a secondary question, if a feasible solution doesn't exist, one possibility might be to partition each non-overlapping section into small regions, and map these regions, greatly reducing the number of mappings. To calculate the distance between two regions I would use the center of mass (average of the pixel locations in the region). However, this presents the problem of how I should go about doing the partitioning in order to get a near-optimal answer.

任何想法AP preciated !!

Any ideas are appreciated!!

推荐答案

这是最小匹配问题，你是正确的，这是一个困难的问题一般。不过，对于 2D欧几里德偶最小匹配情况下，它是可解的接近O（N²）（见链接）。

This is the Minimum Matching problem, and you are correct that it is a hard problem in general. However for the 2D Euclidean Bipartite Minimum Matching case it is solvable in close to O(n²) (see link).

对于快速逼近，FryGuy是在正确的轨道模拟退火。这是一种方法。

For fast approximations, FryGuy is on the right track with Simulated Annealing. This is one approach.

另外一起来看看近似算法在平面二部和非双向匹配为O（（N /ε）^ 1.5 *登录^ 34（4））（1 +ε）-randomized近似方案。

Also take a look at Approximation algorithms for bipartite and non-bipartite matching in the plane for a O((n/ε)^1.5*log^5(n)) (1+ε)-randomized approximation scheme.

这篇关于需要更好的算法的研究之间的2点的集合映射与最小距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！