二分图匹配问题

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。（见下图）

如图蓝线所示是一种最大二分匹配方案，匹配数=3 警告：使用IE6浏览会极不正常，不信你把图片下载下来用看图工具看看。

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

（以上除图片均来自百度百科）

Continue reading “用于二分图匹配的匈牙利算法”

自学康托展开（做8数码问题）去网上查资料，无无一明白，又苦于资料太少，讲的太含蓄
然而《周易》云：天行健，君子以自强不息
于是奋战6h作此文
为像我一样的菜扫清前行障碍，故名曰：“详解”
如有不当之处，恳请指正
~_~_~_~_~_~_~_华丽的分割线_~_~_~_~_~
康托展开(x)的实际意义:对于一个长度为n的数列包含元素[0..n-1]
x表示此数列是{0,1,2…n-1}全排列中第几小的。最小的为0
(但是通常应用的康托展开有时是[1..n])
例如当n=3时(默认[1..n]):
{1,2,3}x=0;{1,3,2}x=1;
{2,1,3}x=2;{2,3,1}x=3;
{3,1,2}x=4;{3,2,1}x=5;
(针对0..n-1是连续自然数 )
其计算方法:
\(
X=a[n]\times (n-1)!+a[n-1]\times (n-2)!+…a[i]\times (i-1)!a[2]\times 1!+a[1]\times 0! \\
\)
X=a[n]*(n-1)!+a[n-1]*(n-2)!+…a[i]*(i-1)!+a[2]*1!+a[1]*0!;
或(d对于第一位为a[1],下面代码即是如此):
\(
X=a[1]\times (n-1)!+a[2]\times [n-2]!+…+a[n-1]\times 1!+a[n]\times 0! \\
\)
X=a[1]*(n-1)!+a[2]*[n-2]!+…+a[n-1]*1!+a[n]*0！
其中a[i]表示元素arr[i]在还未出现的数字中排第几,简而言之就是其后面有多少元素比arr[i]小
核心代码：

实际代码（C实现）个人认为比较详细了，如果有不理解，切记看完上面说明
Continue reading “康托展开详解”