Title Text:It’s like the traveling salesman problem, but the endpoints are different and you can’t ask your friends for help because they’re sitting three seats down.

Origin:https://xkcd.com/173/

https://www.explainxkcd.com/wiki/index.php/173:_Movie_Seating

在美国的大多数电影院里，座位都没有保留。[1]也就是说，门票是在没有座位分配的情况下通过筛选出售的，因此进入的顾客可以占用任何空位。因此，一群进入的顾客可以走进一列并连续占据连续座位的一部分，每个人在他们面前的人旁边拿一个。因此，这些人的顺序取决于他们走进剧院的顺序，这在大多数情况下是随机的。

Cueball对他和他的朋友们在电影院坐下的方式感到不安。问题的一部分是两个显然处于恋爱关系中的人并不坐在一起。因此，他试图用社交图来计算他和他的七个朋友连续坐下的最佳方式，同时考虑到他们之间的所有社交关系。在数学中，这种类型的问题称为组合优化。最流行的例子，旅行商问题，在标题文本以及漫画287和399中引用。

标题文字显示问题的另一部分是Cueball的朋友，他们本可以帮助他计算解决方案，每个人都坐三个座位，所以他不能向他们寻求帮助。

[1]从2017年开始，美国各地的某些马库斯影院现在出售带有预留座位的电影票，无论是在线还是在剧院购买。当您购买机票时，您还可以指定您想要坐的座位。因此，如果您购买多张机票，您可以选择彼此相邻的座位，前提是您在购买之前尽早购买它们。再找两个或更多空座位。

解决方案[编辑]

显示了漫画中提出的特定问题的两个假设解决方案：