什么样的算法能解决问题？
戴维·盖尔是一名数学家，生于1922年，长期任加利福尼亚大学伯克利分校教授，2008年去世，终年86岁。虽然盖尔是一个数学家，但是他的研究也涉及很多博弈论、经济学等社会科学方面的内容。1980年，他获得了运筹学方面的最高奖项——冯·诺依曼奖。
盖尔发明的TTC算法1974年首次在沙普利和斯卡夫的论文中以“该内容由盖尔首创”的形式公开发表。
因为不是登载在盖尔自己的论文中，所以在写与TTC算法有关的书或者论文时，总要先说明“由盖尔编写的TTC算法”，然后引用沙普利和斯卡夫的论文（本书也是如此）。
可能当时盖尔自己也没太意识到该算法的里程碑意义吧。
TTC算法是在极短的时间内找到强核配置的算法。我们通过下面这个7个学生交换房间的例子来看看该算法是否有这样的威力。
大家能一眼望去就找到强核配置吗？我在上课时经常提这个问题。要找到很难，一般来说找不到。之前最常听到的学生答案是“学生1住房间6，学生2住房间3，学生3住房间5，学生4住房间2，学生5住房间4，学生6住房间7，学生7住房间1”（下表中用□标出）。
经常被错认为是强核配置
这个分配中所有人都可以住在对自己来说满意度排在前两位的房间，看起来确实不错。我每次听到这个答案时也都很佩服能找到这个分配的学生，觉得他很聪明。
但实际上这是一个圈套：该分配并非强核配置。因为如果像下表中画○的那样，学生1、4、5抢在全体前面仅在他们3个人之间进行交换：学生1住房间5，学生4住房间1，学生5住房间4——这样做对他们来说更有利（学生5没有变化）。
并非强核配置
那怎样才是强核配置呢？
答案是：“学生1住房间5，学生2住房间3，学生3住房间2，学生4住房间1，学生5住房间4，学生6住房间6，学生7住房间（7下表中的○）”。强核配置是唯一的，再无其他。
强核配置
现在有7个学生，分配方式总共有7的阶乘——5040种。但在强核配置之外还有5039个组合，无论哪一个都必然会发生某个小集团结盟。考虑到这一点，它的唯一性仍然成立就让人很吃惊。
刚才提到的那个经常被错认为是强核配置的解，看起来确实不错，就连我也这么觉得。一直盯着偏好表看，的确会感觉这个分配很好。但问题是“哪一个是强核配置”？所以它并非正确答案。光用眼睛看很难得到正确答案，需要严谨的解法。
面对这类问题，TTC算法就是解法。采用TTC算法来寻找，比盯着看还要多花费一些时间。但是这个算法结构简单，普通人也能理解。
顺便说一句，我在美国留学时曾经用拙劣的英语向50来岁的主妇们解释这种算法，她们也能理解。当时我的英语很差，甚至“but”的音都发不好（后来稍有进步）。那为什么还可以表述清楚呢，就是因为该算法的构成就像人的动作一样，很容易用感觉来理解。
那么TTC算法是如何寻找强核配置的？我们以上页的偏好表为例逐步讲解：
○第一轮
每个学生用手指出对自己来说排在首位的房间，这里用箭头表示“用手指”，就是：
1→5
2→3
3→4
4→1
5→4
6→7
7→1
例如1→5，就是学生1指了房间5。把箭头连起来就会发现一个闭合循环：
1→5→4→1
所谓循环，顾名思义就是开头和结尾相同的一串箭头的连接。箭头指向想要的东西，按照这个循环分配给学生1房间5，学生5房间4，学生4房间1。这样学生1、4、5的房间确定，他们离开。
○第二轮
现在剩下的学生是2、3、6、7，他们也指出了剩下房间中自己最满意的房间：
2→3
3→2
6→7
7→7
用箭头连接起来就得到循环
2→3→2
7→7
7→7很短，但也是一个完整的循环。和第一轮一样，分给学生2房间3，学生3房间2，学生7房间7。
这样学生2、3、7的房间确定，他们离开。
○第三轮
现在只剩下学生6，他也要指出剩下房间中自己最满意的房间。但是现在只剩下房间6，所以他只能指6，也就是6→6。
学生6被分配了房间6，他也离开了，算法到此结束。将上述结果归纳如下，这就是强核配置。
强核配置
这个例子经过三轮算法结束。在TTC算法中，无论偏好如何，每一轮必定会形成一个循环，所以每次最少会有一个人离开。
也就是说，如果有n个学生，无论花费多少时间，最多经过n轮，所有人就一定会离开，TTC算法结束。
前面说过，有n个学生参与时分配的方法共有n的阶乘n！种，随着n增大，分配方法也会迅速增加。而在实际运用TTC算法时所需要的最多步骤，往往和学生数相等，也是n。
也就是说即使参与者的范围不断扩大，但计算所需的时间增加有限，可以说这个算法的运算速度很快。
我们再来看一个例子熟悉一下TTC算法，这个例子在下节的讨论中还会用到。
○第一轮
每个学生指出对自己来说排在首位的房间：
1→3
2→1
3→2
4→3
5→4
6→4
用箭头连接起来就找到循环1→3→2→1。于是学生1得到房间3，学生3得到房间2，学生2得到房间1，他们离开。
○第二轮
现在剩下的是学生4、5、6，这些学生在剩下的房间中指出自己最满意的房间：
4→6
5→4
6→4
用箭头连接起来会得到循环4→6→4，于是学生4得到房间6，学生6得到房间4，他们离开。
○第三轮
此时剩下的只有学生5了，他指了房间5，循环就是5→5，学生5得到了房间5离开。
所有人都离开了，算法结束。将以上结果归纳如下，就是唯一的强核配置。
强核配置