论文部分内容阅读
该文推广了Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配的男孩－最优算法。证明了当男孩挑选时，允许某些男孩可以不挑选，则Ｇ－Ｓ匹配的最大步数为ｎ＾２－ｎ＋１。给出了一般情形下的Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配，即有ｍ个男孩，ｎ个女孩时，男孩－最优算法的最大步数是ｍ（ｍ－１）＋１，或ｎ（ｍ－１）＋１；女孩－最估算法的最大步数是ｎ（ｎ－１）＋１，或ｍ（ｎ－１）＋１。