{讨论}{算法}稳定婚姻模型和延迟认可算法
yzniu.hong
因为此前教算法课的老师要我们大家选题做小的研究性的作业,我就做了这个问题,参考了一些文献,最近发现被老师看中了,他也觉得比较有意思,所
以我倒时候应该要上台去给大家讲这个问题...
说实话PPT做的很烂,解决稳定婚姻问题,我列出了三种方法:
一是延迟认可算法,这是最经典的.
二是回溯算法,
三是在回溯方法上进行改进的回跳算法....
现在的问题是:我们经常说:针对一个问题,给出一个算法,证明这个算法是有效的必须证明:
该算法可以有限步停机;该算法在任何一个合法的输入情况下,都可以得到满足题目要求的解........
遗憾的是,对延迟认可算法的可停机性证明,我所查的所有论文都直接给我一句话说:
"显然可以知道该延迟认可算法在有限步内可以得到解"................
明摆着是忽悠吧,我一直没看出怎么显然来着,虽然从直觉上我认定它是可以有限步停机的............
今天上午一直在图书馆尝试用一个严格的数学证明来证明,在n步之后,所有人都可以找到配偶,而且满足稳定特性..... 但是我失败
了,所以想请教各位高人怎么样证明这个显然的问题?
-----------------------------------------------------------------------------------
如果对稳定婚姻模型不是很熟悉的人:)可以参考下面的描述:
问题:question:
A是n个男子的集合,B是n个女子的集合,每个男子按照自己的意愿将n个女子排成一列;同样每个女子按照自己的意愿也将n个男子排成一列.将他们组成夫
妇,如果存在这样一个男子和女子,这两人不是夫妇,但是他们互相喜欢的程度胜于对自己配偶的喜爱,这样的n对夫妇称为不稳定婚姻.
对于给出的2个n*n阵列,每个位置为Mi->Wj或者Wi->Mj的喜爱程度,求解出稳定婚姻匹配状态.
延迟认可算法:
第一次,每个人都去向自己最喜欢的女子求爱---那么每个女子从向自己求爱的k个人选出自己 最喜欢 的1个其他被拒.(k可能是0,但是没有关系,每
个女子最终总会有人向她表白…,且这个最喜欢不一定就是真正最喜欢的!)
第二次,那些没有成功的男士继续向自己次喜欢的女子求爱,这个时候如果已经有男伴的女子发现当前有更喜欢的男子向她求爱,那么选择替换掉原来的.要求男
子不能主动提出解除关系.
按照上述过程继续下去,即第i个过程中那些还没有女伴的男子继续向自己次爱的女子求爱,那些有男伴的女子可以在这一轮的求爱者当中按意愿点选择替换
所有文献都说显然可以知道该算法一定可以有限步停机.....
可是我不知道为什么?
Shujie Shang
--
Shujie Shang
College of Computer Science, Zhejiang University,China.
msn: ssj...@hotmail.com
yzniu.hong
定义函数f(i)表示i次这种车轮式的求爱之后,共有几对配偶已经产生了
那么我要问的是:f(n)>=n 或者是存在某个0<k<n可以使得f(k)==n?
算法本身是没什么问题,不管你怎么理解这个问题,现在我只想证明这个算法至多只需要n步就可以停机得到正确解...
On 4月11日, 下午1时27分, Shujie Shang <henoc...@gmail.com> wrote:
> 有点类似匹配啊
>
> 2009/4/11 yzniu.hong <hongyz...@126.com
RoBa
的下一个略差的目标求爱，而他的目标一共只有N个，所以他最多被拒了N次，也就结束了，没有死循环的可能。我想你真正担心的问题是：会不会到最后出现光
棍的情况？
实际上这也是不可能的。因为男女是一一配对的，如果有男光棍存在，必定有女光棍存在。而我们可以证得女光棍是不可能存在的：如果一个女人曾经被某个/或
某些男人求爱过，那么她就不可能再变成光棍（因为只要在某一轮有人向她求爱，她就会从其中选择一个，而以后她总是在与当前男人断绝关系的同时接受另一个
男人）。所以，如果有女光棍，那么她就是从未被任何人求爱过。但我们知道每个男人的列表里是N个女人都包含的，所以这个女光棍也是一定出现在他们的列表
里的，那么如果这个女光棍从未被任何人求爱过，那只能说明她在所有男人的列表里都比较排靠后，而所有的男人都在还没考虑到她之前已经和别的女人确定关系
并且一直保持到最后了。但这样的话男光棍就不存在了，如果男光棍不存在的话，女光棍也不可能存在。于是这就出现了一个矛盾。得证。
呼......累死我了......
On 4月11日, 下午1时20分, "yzniu.hong" <hongyz...@126.com> wrote:
> 群上的朋友肯定有知道稳定婚姻模型和著名的延迟认可算法的
> 因为此前教算法课的老师要我们大家选题做小的研究性的作业,我就做了这个问题,参考了一些文献,最近发现被老师看中了,他也觉得比较有意思,所
> 以我倒时候应该要上台去给大家讲这个问题...
> 说实话PPT做的很烂,解决稳定婚姻问题,我列出了三种方法:
> 一是延迟认可算法,这是最经典的.
> 二是回溯算法,
> 三是在回溯方法上进行改进的回跳算法....
>
> 现在的问题是:我们经常说:针对一个问题,给出一个算法,证明这个算法是有效的必须证明:
> 该算法可以有限步停机;该算法在任何一个合法的输入情况下,都可以得到满足题目要求的解........
> 遗憾的是,对延迟认可算法的可停机性证明,我所查的所有论文都直接给我一句话说:
> "显然可以知道该延迟认可算法在有限步内可以得到解"................
> 明摆着是忽悠吧,我一直没看出怎么显然来着,虽然从直觉上我认定它是可以有限步停机的............
>
> 今天上午一直在图书馆尝试用一个严格的数学证明来证明,在n步之后,所有人都可以找到配偶,而且满足稳定特性..... 但是我失败
> 了,所以想请教各位高人怎么样证明这个显然的问题?
> --------------------------------------------------------------------------- --------
> 如果对稳定婚姻模型不是很熟悉的人:)可以参考下面的描述:
> 问题:question:
>
> A是n个男子的集合,B是n个女子的集合,每个男子按照自己的意愿将n个女子排成一列;同样每个女子按照自己的意愿也将n个男子排成一列.将他们组成夫
> 妇,如果存在这样一个男子和女子,这两人不是夫妇,但是他们互相喜欢的程度胜于对自己配偶的喜爱,这样的n对夫妇称为不稳定婚姻.
> 对于给出的2个n*n阵列,每个位置为Mi->Wj或者Wi->Mj的喜爱程度,求解出稳定婚姻匹配状态.
>
> 延迟认可算法:
>
> 第一次,每个人都去向自己最喜欢的女子求爱---那么每个女子从向自己求爱的k个人选出自己 最喜欢 的1个其他被拒.(k可能是0,但是没有关系,每
> 个女子最终总会有人向她表白...,且这个最喜欢不一定就是真正最喜欢的!)
yzniu.hong
> > 可是我不知道为什么?- 隐藏被引用文字 -
>
> - 显示引用的文字 -
Mingfei Li
>就是匹配,不过我要证明的是
>
>定义函数f(i)表示i次这种车轮式的求爱之后,共有几对配偶已经产生了
>
>那么我要问的是:f(n)>=n 或者是存在某个0<k<n可以使得f(k)==n?
>
>算法本身是没什么问题,不管你怎么理解这个问题,现在我只想证明这个算法至多只需要n步就可以停机得到正确解...
>
>
不一定会在n步面停机吧，但是会在有限步内停机。这个算法应该是如果一个哥们儿被一个mm拒了，就不能再向她求婚了。所以，一个哥们儿最多只能被拒n次，所以就肯定不会一直进行下去了。
Silwile
另也可以参考一下由Jon Kleinberg and Éva Tardos教授的Algorithm Design的课程主页。
Jeff Ye
世泉(raymond)
2. 对于n个女人中任何一个Ni，喜欢他的男人可以按照喜欢的深度量化，从而分为K组（不喜欢的为0，最喜欢的假设为MAX(Ni）），
1<=k<=n，如果两个男人对Ni的喜欢程度相同，则这两个男人属于一组。
3. 显然，这个女人Ni最多更换配偶的次数是K-1次，这种情况发生在男人向Ni求爱的次序恰好是Ni对这些男人喜欢深度的反序。这是很容易证明的，
因为任何一组的男人只能有一个获得Ni的青睐，而且该组的其他男人在下次的选择一定不会向Ni求爱（因为我们设定男人失败后会向次爱的女人求爱，而同一
个组的男人对一个Ni的喜欢是相同的，所以次爱的女人一定不是Ni）
4.因为任何一个女人都最多经历K-1更换男人（加上第一次选择，最多K次接触男人），而K属于[1,N]，所以，显然，最多N次肯定停机。
这个问题真别扭，我好像觉得男人女人都像电子和质子一样，不舒服。呵呵
On 4月11日, 下午1时20分, "yzniu.hong" <hongyz...@126.com> wrote:
> 群上的朋友肯定有知道稳定婚姻模型和著名的延迟认可算法的
> 因为此前教算法课的老师要我们大家选题做小的研究性的作业,我就做了这个问题,参考了一些文献,最近发现被老师看中了,他也觉得比较有意思,所
> 以我倒时候应该要上台去给大家讲这个问题...
> 说实话PPT做的很烂,解决稳定婚姻问题,我列出了三种方法:
> 一是延迟认可算法,这是最经典的.
> 二是回溯算法,
> 三是在回溯方法上进行改进的回跳算法....
>
> 现在的问题是:我们经常说:针对一个问题,给出一个算法,证明这个算法是有效的必须证明:
> 该算法可以有限步停机;该算法在任何一个合法的输入情况下,都可以得到满足题目要求的解........
> 遗憾的是,对延迟认可算法的可停机性证明,我所查的所有论文都直接给我一句话说:
> "显然可以知道该延迟认可算法在有限步内可以得到解"................
> 明摆着是忽悠吧,我一直没看出怎么显然来着,虽然从直觉上我认定它是可以有限步停机的............
>
> 今天上午一直在图书馆尝试用一个严格的数学证明来证明,在n步之后,所有人都可以找到配偶,而且满足稳定特性..... 但是我失败
> 了,所以想请教各位高人怎么样证明这个显然的问题?
> -----------------------------------------------------------------------------------
> 如果对稳定婚姻模型不是很熟悉的人:)可以参考下面的描述:
> 问题:question:
>
> A是n个男子的集合,B是n个女子的集合,每个男子按照自己的意愿将n个女子排成一列;同样每个女子按照自己的意愿也将n个男子排成一列.将他们组成夫
> 妇,如果存在这样一个男子和女子,这两人不是夫妇,但是他们互相喜欢的程度胜于对自己配偶的喜爱,这样的n对夫妇称为不稳定婚姻.
> 对于给出的2个n*n阵列,每个位置为Mi->Wj或者Wi->Mj的喜爱程度,求解出稳定婚姻匹配状态.
>
> 延迟认可算法:
>
> 第一次,每个人都去向自己最喜欢的女子求爱---那么每个女子从向自己求爱的k个人选出自己 最喜欢 的1个其他被拒.(k可能是0,但是没有关系,每
> 个女子最终总会有人向她表白...,且这个最喜欢不一定就是真正最喜欢的!)
hongyzniu
世泉(raymond)
肯定的.我这种方法仍然感觉在说理，而不是在数学证明，呵呵。
On 4月12日, 下午10时43分, hongyzniu <hongyz...@126.com> wrote:
> n次不一定可以停机。。。。
>
> 在2009-04-12?21:51:49，"世泉(raymond)"?<shiqu...@gmail.com>?写道：
>
> >1.?男人不能首先提出分手
> >2.?对于n个女人中任何一个Ni，喜欢他的男人可以按照喜欢的深度量化，从而分为K组（不喜欢的为0，最喜欢的假设为MAX(Ni）），
> >1<=k<=n，如果两个男人对Ni的喜欢程度相同，则这两个男人属于一组。
> >3.?显然，这个女人Ni最多更换配偶的次数是K-1次，这种情况发生在男人向Ni求爱的次序恰好是Ni对这些男人喜欢深度的反序。这是很容易证明的，
> >因为任何一组的男人只能有一个获得Ni的青睐，而且该组的其他男人在下次的选择一定不会向Ni求爱（因为我们设定男人失败后会向次爱的女人求爱，而同一
> >个组的男人对一个Ni的喜欢是相同的，所以次爱的女人一定不是Ni）
> >4.因为任何一个女人都最多经历K-1更换男人（加上第一次选择，最多K次接触男人），而K属于[1,N]，所以，显然，最多N次肯定停机。
>
> >这个问题真别扭，我好像觉得男人女人都像电子和质子一样，不舒服。呵呵
>
> >On?4月11日,?下午1时20分,?"yzniu.hong"?<hongyz...@126.com>?wrote:
> >>?????????群上的朋友肯定有知道稳定婚姻模型和著名的延迟认可算法的
> >>?????因为此前教算法课的老师要我们大家选题做小的研究性的作业,我就做了这个问题,参考了一些文献,最近发现被老师看中了,他也觉得比较有意思,所
> >>?以我倒时候应该要上台去给大家讲这个问题...
> >>?????????说实话PPT做的很烂,解决稳定婚姻问题,我列出了三种方法:
> >>????????一是延迟认可算法,这是最经典的.
> >>???????二是回溯算法,
> >>???????三是在回溯方法上进行改进的回跳算法....
>
> >>??????现在的问题是:我们经常说:针对一个问题,给出一个算法,证明这个算法是有效的必须证明:
> >>???????该算法可以有限步停机;该算法在任何一个合法的输入情况下,都可以得到满足题目要求的解........
> >>???????遗憾的是,对延迟认可算法的可停机性证明,我所查的所有论文都直接给我一句话说:
> >>??????"显然可以知道该延迟认可算法在有限步内可以得到解"................
> >>????????明摆着是忽悠吧,我一直没看出怎么显然来着,虽然从直觉上我认定它是可以有限步停机的............
>
> >>????????今天上午一直在图书馆尝试用一个严格的数学证明来证明,在n步之后,所有人都可以找到配偶,而且满足稳定特性.....??但是我失败
> >>?了,所以想请教各位高人怎么样证明这个显然的问题?
> >>?-----------------------------------------------------------------------------------
> >>???????如果对稳定婚姻模型不是很熟悉的人:)可以参考下面的描述:
> >>?问题:question:
>
> >>?A是n个男子的集合,B是n个女子的集合,每个男子按照自己的意愿将n个女子排成一列;同样每个女子按照自己的意愿也将n个男子排成一列.将他们组成夫
> >>?妇,如果存在这样一个男子和女子,这两人不是夫妇,但是他们互相喜欢的程度胜于对自己配偶的喜爱,这样的n对夫妇称为不稳定婚姻.
> >>?对于给出的2个n*n阵列,每个位置为Mi->Wj或者Wi->Mj的喜爱程度,求解出稳定婚姻匹配状态.
>
> >>?延迟认可算法:
>
> >>?第一次,每个人都去向自己最喜欢的女子求爱---那么每个女子从向自己求爱的k个人选出自己?最喜欢?的1个其他被拒.(k可能是0,但是没有关系,每
> >>?个女子最终总会有人向她表白...,且这个最喜欢不一定就是真正最喜欢的!)
>
> >>?第二次,那些没有成功的男士继续向自己次喜欢的女子求爱,这个时候如果已经有男伴的女子发现当前有更喜欢的男子向她求爱,那么选择替换掉原来的.要求男
> >>?子不能主动提出解除关系.
>
> >>?按照上述过程继续下去,即第i个过程中那些还没有女伴的男子继续向自己次爱的女子求爱,那些有男伴的女子可以在这一轮的求爱者当中按意愿点选择替换
>
> >>?所有文献都说显然可以知道该算法一定可以有限步停机.....
>
> >>?可是我不知道为什么?
