1700435338
图1-6 维克·维索斯基， 约1982年（贝尔实验室供图）
1700435339
1700435340
不久以后，维克搬去贝尔实验室的其他驻地，从事“卫兵”（Safeguard）导弹防御系统方面工作。后来，他又回到墨里山，担任计算科学研究中心的执行总监，成了在我上面好几级的老板。
1700435341
1700435342
1968年春天，我着手解决博士论文中我的导师彼得·韦纳（Peter Weiner）给的一个图划分（graph partitioning）问题（图1-7）：给定一些由边线连接的节点，试将这些节点切分为大小相同的两组，且从一组中的节点到另一组中的节点的连接边数尽可能少。
1700435343
1700435344
1700435345
1700435346
1700435347
图1-7 图划分问题示例
1700435348
1700435349
表面上看，这来源于实际问题：如何将程序切分为多个部分，放到不同的内存页中，当程序运行时，程序页进出内存的交换量保持最小。节点代表代码块，边线代表代码块与代码块之间的可能交换，每条边有一个衡量交换频率的权值，从而可以估算出不同内存页中的代码块的交换代价。
1700435350
1700435351
从某种意义上讲，这是一个生造出来的问题，但它也是某些现实事物的合理抽象，而且还有其他具体问题符合这个抽象模型。例如，电路板上的元件如何布置才能减少电路板与电路板之间的昂贵连接？另一个不太恰当的例子是，如何将员工分配到不同楼层，才能让经常交谈的人在同一个楼层？
1700435352
1700435353
这是一个合适的博士论文选题，但我进展甚缓。1968年夏天，当我回到贝尔实验室开始第二段实习期时，我向林申（Shen Lin）请教。那时他刚为经典的“旅行商问题”找到当时最有效的算法：对于一组城市，给出最短路线，必须访问每座城市且每座城市仅访问一次，然后返回。
1700435354
1700435355
林申提出了一种图划分算法，这种算法虽然无法保证能得出最优解，但看来可靠。我想出了高效地实现它的路子。我用大量图来做实验，评估该算法在实践中的有用程度。该算法看起来相当有效，但我们没办法找到最优解。我也找了一些有趣的特殊图，对于这些图，可以给出既快又能得到最优解的算法。以上工作的成果对于一篇论文是足够了，在暑期结束时，我已经全获所需。我在秋天着手撰写论文，并于1969年1月通过毕业答辩（从普林斯顿大学3年毕业的乐观估计最后变成了4年半毕业）。
1700435356
1700435357
一周后，我开始到贝尔实验室计算科学研究中心工作。没面试，实验室在上一年秋天就给我发了录用通知，但有个要求：必须先完成论文。高我两个行政级别的研究中心主任萨姆·摩根（Sam Morgan）告诉我：“我们不招博士肄业生。”完成论文绝对是好事一桩——12月，我又收到一封信，说我得到大幅加薪，而我当时都还没去报到！
1700435358
1700435359
说句题外话，林申和我找不到既高效又总能给出最优解的图划分算法确实情有可原，不过，当时我们还不知道这一点。有人一直在研究图划分之类的组合优化问题的固有困难，并发现了某些有趣的一般关系。
1700435360
1700435361
1971年，多伦多大学的数学家和计算机科学家斯蒂芬·库克（Stephen Cook）做出了非凡的成果，证实包括图划分在内的许多难题是等价的。也就是说，如果我们能找到解决其中一个难题的有效算法（即比尝试所有可能性更好的方法），就能找到解决所有难题的有效算法。在计算机科学领域，这类难题是否真的很难，还是悬而未决的问题，但我认为它们确实很难。库克因为这项工作获得了1982年的图灵奖。
1700435362
1700435363
1969年，我正式加入贝尔实验室时，没人告知我具体要做什么事。惯例如此：把你介绍给其他人，让你随意晃荡，去寻找自己的研究课题和协作者。回想起来，这似乎是下马威，但我不记得有什么麻烦。周边有那么多新鲜事在发生，想找点儿东西来研究，或者找个人来合作，根本不成问题。两个夏天之后，我已经认识所有人，也了解了一些项目情况。
1700435364
1700435365
贝尔实验室向来缺乏明确的管理层指示。1127中心的项目不由管理层指派，而是自下而上，由对某个课题感兴趣的人员自主成立项目组。贝尔实验室的其他部门也是如此：如果我参与了某个开发组，也许会“利诱”科研同事也来参加，不过他们得自愿加入。
1700435366
1700435367
无论如何，有一段时间，我继续和林申一起研究组合优化问题。林申对这类问题特别有见地。他用纸笔画一些示例，就能察觉到有前途的攻击路线。他对旅行商问题有了新的想法，大幅改进了他以前的算法（已经是当时最有名的算法），我用Fortran程序实现了他的新算法。这个算法工作得很好，此后多年间一直是最顶尖的算法。
1700435368
1700435369
这类工作既有趣又能带来成就感，而我善于将想法转化为可工作的代码，却完全不擅长算法，所以我逐渐涉足其他阵地：文档编制软件、专用编程语言，还有一点点图书写作。
1700435370
1700435371
我也会时不时回来和林申一起工作，其中一次是为AT&T客户的私有网络优化设计提供一套复杂工具。在相对纯正的计算机科学与对公司切实有用的系统间来回切换是件好事。
1700435372
1700435373
贝尔实验室公关部门对林申在旅行商问题上的成果产生了兴趣，拿他做了好几回宣传主角。图1-8所示为其中一次的模糊剪报，我在右下角。图1-9引自实验室某本装点面子的杂志，报道主题是我们在图划分方面的工作，时间大概在我们拿到算法专利之后。
1700435374
1700435375
1700435376
1700435377
1700435378
图1-8 林申，约1970年（贝尔实验室供图）
1700435379
1700435380
1700435381
1700435382
1700435383
图1-9 公关图片，约1970年（贝尔实验室供图）
1700435384
1700435385
可以注意到，在图1-9中，我系着领带，这很不符合我的一贯形象。几年后，丹尼斯·里奇和我为另一本内刊，大概是Western Electric Engineer（西部电气工程师）吧，撰写关于C语言的文章。刊物出版前，编辑要我们寄几张肖像照片过去做配图，我们照办了。几星期后，他们说照片丢了。我们说，没问题，那就再寄一次好了。他们回复：“这次可以系上领带吗？”我们严词拒绝，后来他们奇迹般地找到了之前没系领带的照片，并且刊印了。
1700435386
1700435387
我开始以长期雇员身份工作时，办公室在2号楼5层9号梯附近，在那里我待了30年。世界变幻，我自岿然。在那些年里，走廊上的邻居有肯·汤普森、丹尼斯·里奇、鲍勃·莫里斯（Bob Morris）、乔 · 奥桑纳（Joe Ossanna），还有杰勒德·霍尔兹曼，大名鼎鼎的约翰 · 莱昂斯（John Lions）、安迪·塔嫩鲍姆（Andy Tanenbaum）和戴维·惠勒（David Wheeler）也来造访过。