[173] Movie Seating

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

解决方案[编辑]

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Categories