关注我们：

solidot新版网站常见问题，请点击这里查看。

研究人员证明走遍韩国 8 万酒吧的最短路径

数学
Wilson (42865)发表于 2025年04月24日 17时14分 星期四

来自苏珊娜之歌
韩国有 81,998 家酒吧，走遍所有酒吧的最短路径是一个典型的旅行商问题。而旅行商问题则属于 NP 困难问题，即随着数量的增长计算所需时间将会超多项式级别增长。罗斯基勒大学和滑铁卢大学的研究人员报告，他们证明走遍韩国 81,998 家酒吧所需时间最短为 15,386,177 秒，即 178 天 1 小时 56 分 17 秒。科学家表示他们不推荐试图走遍这些酒吧的人喝酒而是喝水喝茶或无糖可乐。


www.math.uwaterloo.ca/tsp/korea/index.html
www.math.uwaterloo.ca/tsp/korea/computation.html
回复