英语原文共 28 页，剩余内容已隐藏，支付完成后下载完整资料
附录X 译文
引言：一些典型的问题
1.1 第一个问题：稳定匹配
作为一个开始的主题，我们先看一个算法问题，这个问题对我们将要强调的许多问题做了很好的阐明。它来自一些非常自然的实际问题，从这些我们得到关于问题的清晰简洁的形式化陈述。解决这个问题的算法也非常的清晰，我们的主要工作就是证明它的正确性，并且对于为得到一个解决所占用的时间量给出一个可以接受的范围，这个问题—稳定匹配问题—有几个起源。
1.1.1 问题
稳定匹配问题一部分起源于在1962年，当时David Gale和 Lloyd Shapley，两个数理经济学家问了这个问题：可以设计一个学校的入学或工作招聘处理过程，使得它是自强化的？他们的这句话意味着什么呢？
为了提出问题，让我们首先简略地想一下这种情况。可能有一组朋友，都在学院主修计算机科学专业的学生，开始申请到公司暑假实习。申请过程的关键是两类不同的参与者：公司（雇主）和学生（申请人）之间的互相影响。每个申请人对公司有一个优先排序，一旦申请人来到公司，每个公司对它的申请人也构成一个优先排序。基于这些优先排序，公司对他们的一些申请人发出录取通知书、申请人选择某个通知书来接受，于是人们开始进入暑假实习。
Gale和Shapley考虑了这种情况在缺少任何强制保持现状的机制下可能要出来的几类问题。假设，例如你的朋友Raj刚接受了一个大电信公司CluNet的暑假工作。一个小的创业公司WebExodus，它做了最后的决策时慢了几步，几天后它也打电话给Raj，也给了他一个暑假的工作。现在，也许是由于这种随意的什么都能做的氛围的吸引，Raj实际上更愿意去WebExodus而不是CluNet。于是这个新的发展也可能使他取消接受CluNet的录用，而去WebExodus。由于突然少了一个暑假实习者，因此CluNet向待聘的一个申请人提供一项工作，这个人马上取消他早先从一家软件巨人Babelsoft接受的录用，那么情况开始连续失控。
形式看起来不好，但从另一个方面来看，这还不算太坏，假如Raj的朋友Chelsea已经预定去Babelsoft，她刚听说了Raj的事。于是，她打电话给WebExodus的人说：“你知道，我暑假真的愿意去你们哪里，而不是Babelsoft”。他们发现这很可信，接着看了Chelsea的申请，感到他们更愿意聘用她，而不是实际上被安排在WebExodus暑假实习的另一个学生。在这种情况下，如果WebExodus不是那种顾虑多的公司，它可能找到某种适当的方式取消对另一个学生的录用，转而聘用Chelsea。
像这样的情况可能乱成一团。许多人—申请人和雇主双方—都对这种处理和结果感到不开心。究竟什么地方出了问题？一个基本的问题是这个过程不是自强化的—如果允许人们以他们自己的兴趣做事，那么他就有毁掉的风险。
我们可能更喜欢下面比较稳定的情况，在这种情况下兴趣本身就能防止录用通知被取消和重寄。考虑另一个学生，他已经被安排在CluNet暑期实习，但是他打电话给WebExodus并且表示更愿意为他们工作。在这种情况下，鉴于录用通知已经被接受，他们可以回答：“不，实际情况是我们宁愿要已经接受的每个学生，所以恐怕我们对你帮不上忙。”或者考虑一个雇主，他处心积虑想招来那些排名在前的申请人，而这些人去了其他地方，结果每个人都告诉他，“不，我在这里非常满意”。在这种情况下，所有的结果都是稳定的，不再有进一步可行的情况。
所以这就是Gale 和Shapley问的问题：给定一组雇主和申请人之间的优先权，我们能否把申请人分配给雇主，使对每个雇主，以及没分配为工作的每个申请人，至少下面两种情况之一成立？
（i）对他所接受的每个申请人比更满意；或者
（ii）对他现在的情况比为雇主工作更满意。
如果这种情况成立，结果是稳定的：个人兴趣将防止任何申请人/雇主进行幕后交易。
Gale 和Shapley对这一问题继续提出了一个显著的算法计算，不久我们就会讨论它。在此之前，注意这不是稳定匹配问题的唯一起源。原来Gale 和Shapley工作的十年前，具有同样潜在的动机，已经在一个类似的过程中使用过国家匹配计划，将医生和医院进行匹配。对此他们并不知情。的确，这一系统至今仍在使用，几乎没做什么改变。
这证实了问题的基本吸引力。从本书的观点看，为导出某些基本的组合定义以及在这些定义之上的算法，这个问题为我们提供了第一个好的领域。
问题形式化 了解这个概念的本质有助于问题尽可能的清晰。公司和申请人的世界包含了某些混乱的不均匀性。每个申请人正在找一家公司，而每家公司正在找多个申请人；另外，可能存在着比暑假工作的有效位置更多（或者在某些时候更少）的申请人。最后，每个申请人通常不会申请每一家公司。
至少在开始的时候是有用的，排除这些复杂的因素，得到一个“露骨的”问题描述。个申请人中的每个人对个公司中的每个公司提出申请，每个公司想接受单一的申请人。我们将看到这样做可以保留问题固有的基本特点；特别是我们对这个简化描述的解将被直接推广到更一般的情况。
跟随Gale 和 Shapley的思路，我们观察到这个特殊的情况可以看做一个系统设计问题，通过这个设计使得个男人和个女人中的每个人最终都成婚了。我们的问题自然地模拟了两种“性别”—申请人的公司—在这种情况下，我们正在考虑的是，每个人都在寻找与恰好一个相反性格的人配对①。
①Gale 和Shapley也考虑了同性的匹配问题，其中只有一种单一性别，这也由相关的应用所推动，但是已经被证明在技术层面上是相当不同的。鉴于我们这里正在考虑的申请人-雇主的应用，我们将关注具有两个性别的问题。
所以考虑个男人的集合和个女人的合集，令表示所有可能的形成如的有序对的集合，其中，。一个匹配是来自的有序的集合，并且具有下述性质：每个的成员和每个的成员至多出现在的一个有序对中。一个完美匹配是具有下述性质的匹配：的每个成员和的每个成员恰好出现在的一个对里。
匹配和完美匹配是贯穿这本书频繁出现的术语；在广泛的算法问题建模领域中它们都会自然的出现。在现在的情况下，一个完美匹配仅仅对应于一种男人和女人配对的方式，以这种方式，每个人最终与某个人结婚，并且没有人与多个人结婚—既没有单身的也没有一夫多妻的或者一妻多夫的。
现在我们在这个背景下增加优先的概念。每个男人对所有的女人的排名，如果给的排名高于，我们就说偏爱超过。我们将把的按顺序的排名作为他的优先表，但我们不允许排名中出现并列。类似的，每个女人也对所有的男人排名。
给一个完美匹配，它可能出错吗？按照我们在雇主和申请人方面初始的动机，我们应该担心下述情况：在中存在两个对 和（如图1.1所示）。它们具有更偏爱而不爱，且更偏爱而不爱的性质。在这种情况下，没有什么能阻止和放弃他们当前的伴侣并且转过来走到一起，婚姻的集合不再是自强化的。我们说这样的对是一个相对于的不稳定因素：不属于，但是和双方都偏爱另一方面而不爱他们在中的伴侣。
图1.1 具有不稳定因素的完美匹配
然后我们的目标就是一个不含有稳定因素的婚姻集合，我们说一个匹配是稳定的，如果（i）它是完美的，并且（ii）不存在相对于的不稳定因素。头脑中马上出现两个问题：
·对每组优先表是否存在一个稳定匹配？
·给一组优先表，如果存在稳定匹配，我们能够有效地把它构造出来吗？
一些例子 为说明这些定义，考虑下面两个非常简单的稳定匹配问题的例子。
第一个例子，假设我们有两个男人的集合和两个女人的集合。优先表如下：
更偏爱而不爱。
更偏爱而不爱。
更偏爱而不爱。
更偏爱而不爱。
如果我们直观上考虑这组优先表，它描述了完全的一致性：男人和女人的顺序上一致，且女人在男人的顺序上也一致。存在一个由和对组成的唯一的稳定匹配。另一个由和组成的完美匹配不是稳定匹配，因为对构成了相对这个匹配的不稳定因素（和双方都想离开他们各自的伴侣而组成一对）。
下一个例子，情况更复杂一点，假设优先表是：
更偏爱而不爱。
更偏爱而不爱。
更偏爱而不爱。
更偏爱而不爱。
在这种情况下会发生什么？两个男人的优先表完全互相协调（他们把不同的女人排为第一），两个女人的优先表同样完全协调。但是男人的优先表与女人的优先表完全冲突。
在第二个例子中，存在两个不同的稳定匹配。由和对组成的匹配是稳定的，因为两个男人已经是最满意的了，因此没有人想离开他们匹配的伴侣。而由 和对组成的匹配也是稳定的，这是由于两个女人也是最满意这一互补的理由。这是我们向下进行时要记住的一个要点—对于一个实例可能有多于一个的稳定匹配。
1.1.2 设计算法
我们现在来证明对于每组男人和女人中的优先表，存在一个稳定匹配。进一步，我们证明这一点的方法也将回答上面问到的第二个问题：我们将给出一个有效的算法，它以这些优先表为输入并且构造出一个稳定匹配。
让我们考虑推动这个算法的某些基本思想。
最初，每个人都是未婚的。假设一个未婚的男人选择了他的优先表排名最高的女人，并且向她求婚。我们能够立即声明将是最后的稳定匹配中的一对吗？不一定：因为在将来的某个时候，女人偏爱的男人可能向她求婚。另一方面，对来说，立即拒绝可能是危险的；她可能还没有接收到来自她的优先表上排名像那样高的某个人的求婚。于是，一种自然的想法是使这个对进入一种中间状态—约会。
假设我们现在处于某种状态，某些男人和女人是自由的—没有约会—且某些是有约会的。下一步看起来可能是这样的。任意一个自由的那人选择他还没有求过婚的最高排名的女人，且向她求婚。如果也是自由的，那么和就会成为约会状态。否则，已经在与某个其他的男人约会。在这种情况下，她来决定和哪个人在她的优先表中的排名更高；排名更高的男人变成与约会而另一个人变成自由的。
最后，当没有一个人是自由的，算法将结束；此刻所有的约会将被宣告为最后的结果，并且将返回最终的完美匹配。
这里是Gale-Shapley算法的具体描述，用图1.2描写了算法的一种状态。
初始所有的和都是自由的。
Whlie存在男人是自由的且还没对每个女人都求过婚
选择这样一个男人
令是的优先表中还没求过婚的最高排名的女人
If 是自由的then
变成约会状态
Else 当前与约会
If 是更偏爱而不爱 then
保持自由
Else更偏爱而不爱。
变成约会状态
变成自由
Endif
Endif
Endwhile
输出已约会对象的集合
图1.2 当自由男人向女人求婚时，G-S算法的一个中间状态
一个令人感兴趣的事情是，尽管G-S算法叙述起来相当简单，但是也不是立刻就能看出它返回一个稳定匹配，或者甚至一个完美匹配。我们现在就通过一系列中间的事实来证明这一点。
1.1.3 算法的分析
首先考虑女人在算法执行时的看法。此刻暂时还没有一个人向她求过婚，她是自由的。然后，男人可能向她求婚，并且她变成约会状态，随着时间的继续，她可能收到另外一些求婚，且只接受比她的伴侣的排名更高的那些。于是，我们发现下述事实：
(1.1) 从接受对她的第一次求婚开始保持约会状态，且她正在约会的一系列伴侣变得越来越好（按照她的优先表）。
男人在运算执行中的看法相当不一样。直到向他的表中排名最高的女人求婚之前他都是自由的；在这次求婚时，他可能或者不可能变成约会状态。随着时间继续，他可能在自由和约会状态之间交替，但是保持下面的性质。
(1.2) 求过婚的一系列女人变的越来越差（依照他的优先表）。
现在我们证明这个算法终止，并且给出终止所需要的最大迭代次数的界。
(1.3) G-S算法在至多次Whlie循环的迭代之后终止。
证明 正如我们这里打算做的，一个给出算法运行时间上界的有用策略是找出进展的度量标准，即我们找出某种精确的方法说这个运算执行的每一步使它离终止更接近。
在当前这个算法的情况下，每次迭代由某个男人向一个以前没有求过婚的女人（唯一的一次）求婚构成。于是，如果令表示到迭代结束已经向求过婚的那些对的集合，我没看到，对所有的，的大小严格大于的大小。但是总计只存在个可能的男人和女人的对，因此的值在算法的整个过程中至少可能增加次，从而得到至多可能存在次迭代。
关于前面的事实和它的证明有两点值得注意。第一点，根据确定的优先表，算法的某些执行有可能包含着接近于次的迭代，因此这个分析与最佳可能的结果差距不大。第二点，有许多量不像算法的进展度量表现的那么好，因为它们在每次迭代中不是严格增加的。例如，单个自由人的数目，可能从一次迭代到下一次迭代保持常数，同样可能的还有参与约会的对数，于是，这些量不能按照前一段的方式直接用来给出最大可能迭代的上界。
让我们确定在算法终止时得到的集合事实上是一个完美匹配。为什么这一点不是显而易见的呢？本质上，我们必须证明没有男人可以在他的优先表结束前“落空”；Whlie循环终止的唯一方式就是不存在自由的男人，在这种情况下，约会的那些对的集合的确是一个完美匹配
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[484289]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
