algorithm - 二分图中的最佳匹配(例如，将标签与图上的点相关联)

Question

我正在尝试从绘制点的图形 xy 图中提取语义，其中一些点或所有点​​都有标签。标签被绘制在“点附近”，这样人们通常可以理解哪个标签与哪个点对应。例如，在此图中，很明显哪个标签(数字)属于哪个点(*)，并且基于欧几里德距离的算法将起作用。 (标签和点没有语义顺序 - 例如散点图)

 *1
    *2

        *3

      *4

在拥挤的地 block 中，创作软件/人类可能会将标签放置在不同的方向以避免重叠。例如在

1**2
 **4
 3

人类读者通常可以算出哪个标签与哪个标签相关联。

我接受的一个解决方案是创建一个欧几里德距离矩阵并打乱行以获得函数的最小值(例如对角线或其他启发式距离的平方和)。在第二个示例中(从 NW 角顺时针标记为 a、b、c、d 的点)我们有一个距离矩阵(到 1 d.p.)

             a   b   c   d
 1ab2    1  1.0 2.0 2.2 1.4    
  dc4    2  2.0 1.0 1.4 2.2
  3      3  2.0 2.2 1.4 1.0
         4  2.2 1.4 1.0 2.0

我们需要标记a1 b2 c4 d3。交换第 3 行和第 4 行给出对角线的最小总和。这是一个更复杂的示例，其中简单地选择最近的可能会失败

 *1*2*5
  **4
  3 *6

如果这个问题得到解决，那么我将需要处理标签数量可能小于或大于点数的情况。

如果算法是标准的，我将不胜感激指向开源 Java 的指针(例如 JAMA 或 Apache 数学)

注意:这个 SO 回答 Associating nearby points with a path不太适合作为答案，因为给出了通过这些点的路径。

Answer 1

你有一个 complete bipartite graph一部分是数字，另一部分是点。该图中边的权重是数字和点之间的欧氏距离。你的任务是找到 matching重量最小。

这是一个已知问题，有一个众所周知的算法，名为 Hungarian Algorithm :

来自维基:

We are given a nonnegative n×n matrix, where the element in the i-throw and j-th column represents the cost of assigning the j-th point tothe i-th number. We have to find an assignment of the point to thenumbers that has minimum cost. If the goal is to find the assignmentthat yields the maximum cost, the problem can be altered to fit thesetting by replacing each cost with the maximum cost subtracted by thecost.

The algorithm is easier to describe if we formulate the problem usinga bipartite graph. We have a complete bipartite graph G=(S, T; E) withn number vertices (S) and n point vertices (T), and each edge has anonnegative cost c(i,j). We want to find a perfect matching withminimum cost. The Hungarian method is a combinatorial optimizationalgorithm which solves the assignment problem in polynomial time andwhich anticipated later primal-dual methods. f

详细的算法和代码可以看topcoder article还有这个pdf也许使用

有一个media文件来描述它。(此视频解释了匈牙利算法为何有效)

algorithm :step 1:- prepare a cost matrix.if the cost matrix is not a squarematrix then add a dummy row(column) with zero cost element.

step 2:- subtract the minimum element in each row from all theelements of the respective rows.

step 3:- further modify the resulting matrix by subtracting theminimum elememnt of each column from all the elements of therespective columns.thus obtain the modified matrix.

step 4:- then,draw minimum no of horizontal and vertical lines tocover all zeros in the resulting matrix.let the minimum no of lines beN.now there are 2 possible cases.

case 1 - if N=n,where n is the order of matrix,then an optimalassignment can be made.so make the assignment to get the requiredsolution.

case 2 - if N less than n then proceed to step 5

step 5: determine the smallest uncovered element in thematrix(element not covered by N lines).subtract this minimum elementfrom all uncovered elements and add the same elements at theintersection of horizontal and vertical lines.thus the second modifiedmatrix is obtained.

step 6:- repeat step(3) and (4) untill we get the case (1) of step 4.

step 7:- (to make zero assignments) examine the rows successivelyuntill a row-wise exactly single zero is found.circle(o) this zero tomake the assignment.then mark a cross(x) over all zeros if lying inthe column of the circled zero,showing that they can't be consideredfor future assignment.continue in this manner untill all the zeroshave been examined. repeat the same procedure for column also.

step 8:- repeat the step 6 succeccively until one of the followingsituation arises- (i)if no unmarked zeros is left,then the processends or (ii) if there lies more than one of the unmarked zero in anycolumn or row then,circle one of the unmarked zeros arbitrarily andmark a cross in the cell of remaining zeros in its row orcolumn.repeat the process untill no unmarked zero is left in thematrix.

step 9:- thus exactly one marked circled zero in each row and eachcolumn of the matrix is obtained. the assignment corresponding tothese marked circle zeros will give the optimal assignment.

有关详细信息，请参阅 wiki 和 http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf