玩 30 秒俄罗斯方块,你就在解一个让计算机科学家头疼 50 年的 NP-hard 问题。
规则变了:方块不会消行,你的目标是把空间塞得越满越好。15 个方块后自动结束。
把右边的物品拖进行李箱。放完后对比算法的结果,看你的直觉能打败 First-Fit 吗。
你在俄罗斯方块里练了几十年的技能,计算机科学叫它「在线装箱问题」。
衣服、书本、锅碗瓢盆塞进有限的纸箱。经典 2D/3D 装箱问题,物流公司每天都在解。
马士基每年运 1200 万个集装箱,每个集装箱的空间利用率提高 1% = 节省数亿美元。
操作系统把程序塞进 RAM,malloc() 用的就是 First-Fit / Best-Fit 策略。碎片化 = 空隙。
AWS 把虚拟机塞进物理机器。VM 大小不一,和俄罗斯方块的方块一模一样。
装箱问题已被证明是 NP-hard(Garey & Johnson, 1979)。物品数量一多,穷举所有可能摆放方式的时间超过宇宙年龄。
离线版本可以先看完所有物品再决定(你打包行李时可以这样做)。在线版本一个一个来,放下就不能动——俄罗斯方块就是在线版本。
研究表明人类在 2D 装箱任务中平均能达到最优解的 85-92%。你的大脑在做一种快速的「视觉启发式搜索」。
俄罗斯方块是在线 2D 装箱问题的一个变体。每次落下一个方块,你在有限信息下做出不可撤销的决策。这跟 AWS 分配虚拟机、快递员装车、操作系统分配内存,本质上是同一件事。区别只在于:游戏里失误了可以重来,现实里不行。