研究人员证明走遍韩国 8 万酒吧的最短路径
2025-04-24 17:14 by 苏珊娜之歌
韩国有 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
#数学
2025-04-24 17:14 by 苏珊娜之歌
韩国有 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
#数学
🔥37🤣23👍5🤔5💊1
数学研究生解决加法极限问题
2025-05-23 19:14 by 少女骑士变身记
加法是数学中最简单概念之一，但数学家对于加法所产生的各种模式还有很多尚未解答的疑问。其中一个问题与无和集（Sum-free set）的性质有关。所谓无和集是指该集合中任意取三个数两数相加不会等于第三个数，举例来说，奇数集合中任意两数相加是偶数，奇数集显然是无和集。1965 年著名数学家 Paul Erdős 提出了一个简单问题：无和集有多普遍？这个问题过去几十年进展甚微。在该问题提出 60 年之后，牛津大学研究生 Benjamin Bedert 终于给出了证明：任何整数集合，必定有一个大子集是无和集。随机选择一百万个整数，其中半数是奇数，奇数集是无和集，那么该集合的一个无和子集就包含有大约 50 万个数。Erdos 在 1965 年的论文中仅用几行就推导出了一个下界：N/3——任意包含 N 个整数的集合，至少有一个包含 N/3 个整数的无和子集。最大的无和子集肯定会超过 N/3，但多大？Bedert 的结论是 N/3 + log(log N)。
www.quantamagazine.org/graduate-student-solves-classic-problem-about-the-limits-of-addition-20250522/
en.wikipedia.org/wiki/Sum-free_set
#数学
2025-05-23 19:14 by 少女骑士变身记
加法是数学中最简单概念之一，但数学家对于加法所产生的各种模式还有很多尚未解答的疑问。其中一个问题与无和集（Sum-free set）的性质有关。所谓无和集是指该集合中任意取三个数两数相加不会等于第三个数，举例来说，奇数集合中任意两数相加是偶数，奇数集显然是无和集。1965 年著名数学家 Paul Erdős 提出了一个简单问题：无和集有多普遍？这个问题过去几十年进展甚微。在该问题提出 60 年之后，牛津大学研究生 Benjamin Bedert 终于给出了证明：任何整数集合，必定有一个大子集是无和集。随机选择一百万个整数，其中半数是奇数，奇数集是无和集，那么该集合的一个无和子集就包含有大约 50 万个数。Erdos 在 1965 年的论文中仅用几行就推导出了一个下界：N/3——任意包含 N 个整数的集合，至少有一个包含 N/3 个整数的无和子集。最大的无和子集肯定会超过 N/3，但多大？Bedert 的结论是 N/3 + log(log N)。
www.quantamagazine.org/graduate-student-solves-classic-problem-about-the-limits-of-addition-20250522/
en.wikipedia.org/wiki/Sum-free_set
#数学
🤔21🤯12👍3❤1🔥1