pet*_*ust 4 mapping algorithm plot bipartite
我试图从图形xy图中提取语义,其中绘制点并且一些或全部都有标签.标签被绘制成"靠近点",这样人类通常可以理解哪个标签与哪个点相关.例如,在该图中,清楚哪个标签(数字)属于哪个点(*),并且基于欧几里德距离的算法将起作用.(标签和点没有语义排序 - 例如散点图)
*1
*2
*3
*4
在拥挤的图中,创作软件/人可以将标签放置在不同的方向上以避免重叠.例如在
1**2
**4
3
人类读者通常可以确定哪个标签与哪个标签相关联.
我接受的一个解决方案是创建欧几里德距离矩阵并对行进行混洗以获得函数的最小值(例如,对角线或其他启发式上的距离的总和平方).在第二个例子中(从NW角顺时针标记为a,b,c,d的点),我们有一个距离矩阵(到1 dp)
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答案将附近的点与路径相关联并不能作为答案,因为给出了通过点的路径.
你有一个完整的二分图,一部分是数字,另一部分是分数.此图中边缘的权重是数字和点之间的欧氏距离.而你的任务是找到最小重量的匹配.
这是已知问题,并且具有众所周知的算法,命名为Hungarian Algorithm:
来自维基:
给出非负n×n矩阵,其中第i行和第j列中的元素表示将第j个点分配给第i个数的成本.我们必须找到具有最低成本的数字的分配点.如果目标是找到产生最大成本的分配,则可以通过将每个成本替换为减去成本的最大成本来更改问题以适应设置.
如果我们使用二分图来表示问题,则该算法更容易描述.我们有一个完整的二分图G =(S,T; E),有n个顶点(S)和n个点顶点(T),每个边有一个非负成本c(i,j).我们希望找到最低成本的完美匹配.匈牙利方法是一种组合优化算法,它解决了多项式时间内的赋值问题,并预测了后来的原始对偶方法.F
有关详细的算法和代码,您可以查看topcoder文章 ,也可以使用此pdf
有一个媒体文件来描述它.(此视频解释了为什么匈牙利算法有效)
算法:步骤1: - 准备成本矩阵.如果成本矩阵不是方矩阵,则添加具有零成本元素的虚拟行(列).
步骤2: - 从相应行的所有元素中减去每行中的最小元素.
步骤3: - 通过从各列的所有元素中减去每列的最小元素来进一步修改所得到的矩阵.获得修改后的矩阵.
步骤4: - 然后,绘制水平和垂直线的最小数量,以覆盖所得矩阵中的所有零.小数最小的行数为N.现在有2种可能的情况.
情况1 - 如果N = n,其中n是矩阵的阶数,则可以进行最优分配.然后进行分配以获得所需的解.
情况2 - 如果N小于n,则进入步骤5
步骤5:确定矩阵中最小的未覆盖元素(未被N行覆盖的元素).从所有未覆盖的元素中减去该最小元素,并在水平线和垂直线的交点处添加相同的元素.获得第二个修改的矩阵.
步骤6: - 重复步骤(3)和(4)直到我们得到步骤4的情况(1).
步骤7: - (进行零分配)连续检查行,直到行为顺序正好单个零是found.circle(o)这个零来进行赋值.然后在所有零上标记一个十字(x),如果躺在圆圈零的列,表明它们不能被考虑用于将来的分配.继续以这种方式,直到所有的零都被检查.对列也重复相同的过程.
步骤8: - 成功地重复步骤6,直到出现以下情况之一 - (i)如果没有留下未标记的零,则该过程结束或(ii)如果在任何列或行中存在多于一个未标记的零然后,任意圈出一个未标记的零,并在其行或列中标记剩余零的单元格中的十字.重复该过程,直到矩阵中没有未标记的零.
步骤9: - 因此在每行中确切地标记一个带圆圈的零,并且获得矩阵的每列.与这些标记的圆零相对应的赋值将给出最佳赋值.
有关详细信息,请参阅wiki和http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf