为了分析启发式是如何发挥作用的，除了上面举的乔治通过“反其道而行之”这个启发式找到了工作和女朋友的例子之外，我们再来考虑一个著名的旅行商问题。在这个问题中，一个推销员必须到25个城市推销产品，然后才能回家，要求是他完成这次旅行所走的路程必须尽可能短。推销员面对的这个问题有很多种可能的解决方案。他可以先去那25个城市中的任何一个，然后再去其余24个城市中的任何一个……这个选择过程将继续下去，直到他只剩最后一个城市没有去过为止。这些数字相乘，得到的就是全部可能路线的数量，这是一个巨大的数字，远远超过了10亿。除了极少数情况之外，在这数10亿条路线中，恰好有两条是总路程最短的。为什么会有两条？因为任何一条路线都可以在不改变距离的情况下沿相反方向再走一次。
假设，这个推销员叫奥里特，她是从新墨西哥州阿尔伯克基市开始并结束这个旅程的。将阿尔伯克基市记为A。同时为了简便，假设奥里特要去的其他城市的名字首字母分别为B（比如说，波士顿）、C……Z（比如说，俄亥俄州的曾斯维尔市）。
一条可能的路线
新墨西哥州阿尔伯克基市（Albuquerque）、肯塔基州路易斯维尔市（Louisville）、明尼苏达州的米苏拉市（Missoula）、伊利诺伊州的开罗市（Cairo）……加利福尼亚州的尤里卡市（Eureka）、加利福尼亚州的圣地亚哥市（San Diego），然后回到阿尔伯克基市。
任何一条路线都可以写成一个以字母A开头、并以字母A结尾的字母表，两个字母A之间有25个除A之外的所有其他字母。这就是对于可能路线的一个视角。
某个视角中的路线
ALMCVHFNGHUOWZKXQYWIPBTJRESA
旅行商问题是这一类经典难题中的其中一个，计算机科学家将这类问题称为非确定性多项式问题（nondeterministic polynomial, NP）。在一个典型的NP难题中，随着城市数量N的增大，解决该问题所需要的计算量迅速增加，甚至比N2、N3增加得更快，有人甚至认为，比Nn都增加得快。因此，一旦N（城市数量）变得比较大，找到最佳路线所需时间就会太多。幸运的是，虽然找到最佳路线需要花费大量的计算时间，但是奥里特还是可以通过使用某种仅需尝试不同路线的搜索启发式找到一条好的路线，甚至是一条相当好的路线。启发式不一定能找到最佳的解决方案，但是可以帮我们找到较好的解决方案。用赫伯特·西蒙的话来说，启发式能够令我们感到满意，因为找到了一个相当好的解决办法。
在解决旅行商问题时，一种广泛使用的启发式是将路线中的相邻城市互换。例如，从上面列出的路线开始，这种启发式可能会要求互换田纳西州的诺克斯维尔市（K）与俄亥俄州的齐尼亚市（X）在路线中的位置。
应用启发式对路线进行互换
ALMCVHFNGHUOWZKXQYWIPBTJRESA
将变为：
ALMCVHFNGHUOWZXKQYWIPBTJRESA
如果新的路线距离较短，那么就将它作为“现状”。这个启发式是“贪婪”的，它可以接受任何改进，可以一次又一次地应用它将城市进行互换，并接受距离更短的路线。不难看出，能够减少路线距离的互换次数是有限的。因此，在运用这种启发式一定次数后，肯定会遇到不可能再进一步改进的情况。用这种启发式最终确定的路线不一定是最佳的，但是在大多数情况下都不会过于糟糕。同样，它足以保证我们会相当满意。
互换城市也不是解决旅行商问题的唯一启发式。也可以随机选择一个城市，并将它随机移动到序列中的某个位置。如果新的路线与旧的路线相比有所改善，就可以接受这个随机切换。像这样的随机启发式效率虽然不是很高，但是却能够避免陷入搜索糟糕的解决方案中。还有另一种启发式则是对被一个城市隔开的两个城市进行互换处理。这种启发式表面看起来似乎有点奇怪，但它是有自己的基本逻辑的。前面列出的路线中，匹兹堡（P）位于印第安纳波利斯（I）和波士顿（B）之间，切换波士顿和匹兹堡或者匹兹堡和印第安纳波利斯没什么意义。然而，如果T代表托莱多，W代表华盛顿，那么将波士顿和印第安纳波利斯互换，就可以让奥里特的路线缩短1 020千米（见图2-1）。
图2-1 被一个城市隔开的两个城市之间的互换
只要稍稍花点功夫，就可以推广这个例子，以说明启发式所拥有的超加性潜力。如前所述，当一条路线陷入了局部高峰时，通过将“互换两个相邻城市”这个启发式改良为“互换被一个城市隔开的两个城市”，这样就可以提高效率。但是，改良后的这个启发式还是可能卡在另一条路线上，这时，就可以重新启用“互换两个相邻城市”的启发式来进一步加以改进。通过这种方式，改进叠加改进，就可以创造超加性效应。
