Title Text:What’s the complexity class of the best linear programming cutting-plane techniques? I couldn’t find it anywhere. Man, the Garfield guy doesn’t have these problems…

Origin:https://xkcd.com/399/

https://www.explainxkcd.com/wiki/index.php/399:_Travelling_Salesman_Problem

旅行推销员 2.0

https://songshuhui.net/archives/49037

旅行商问题是计算机科学中的一个经典问题。说明这个问题的直观方法是，给定一个城市列表及其成对距离，任务是找到最短路径，每个城市只访问一次，然后返回原始城市。一个天真的解决方案解决了O（n！）时间（其中n是列表的大小）的问题，只需检查所有可能的路由，并选择最短的路由。更有效的动态编程方法在O（n22n）时间内产生解决方案。这些时间是使用Big O表示法给出的，Big O表示法通常用于计算机科学以显示解决方案或算法的效率或复杂性。

笑话是在线销售的销售人员（比如在eBay，亚马逊商城或其他虚拟市场上）不必担心这个问题，因为他不需要旅行（这使得时间找到最佳解决方案O（1）旅行推销员愤怒地回答，“闭嘴。”

标题文本想知道切割平面方法的时间复杂性，有时用于解决优化问题。

最后一句话暗示了兰德尔绘制漫画关于计算机科学的不利因素;他有时会遇到无法找到答案的问题，而像加菲尔德这样简单漫画的作者却没有这个问题。这也可能是78加菲尔德的参考，它模仿了加菲尔德的朴素。

地图几乎肯定描绘了美国，突出显示的位置（从左到右）：西雅图，旧金山，洛杉矶，凤凰城，丹佛，明尼阿波利斯，达拉斯，圣安东尼奥，休斯顿，芝加哥（切断），底特律，亚特兰大，迈阿密，华盛顿特区，费城，纽约和波士顿。

这是迄今为止唯一一部以布朗帽子为特色的漫画。

另见前面的条带287：NP-Complete。