Proposed initially from a practical circumstance, the traveling salesman problem caught the attention of numerous economists, computer scientists, and mathematicians. These theorists were instead intrigued by seeking a systemic way to find the optimal route. Many attempts have been made along the way and all concluded the nonexistence of a general algorithm that determines optimal solution to all traveling salesman problems alike. In this study, we present proof for the nonexistence of such an algorithm for both asymmetric (with oriented roads) and symmetric (with unoriented roads) traveling salesman problems in the setup of constructive mathematics.
翻译：最初从实际情况出发,旅行推销员问题引起了众多经济学家、计算机科学家和数学家的注意。 这些理论家反而对寻找最佳路线的系统方法感到好奇。 许多尝试都在沿途进行,所有尝试都得出结论,不存在一个决定所有旅行推销员问题的最佳解决办法的通用算法。 在本研究报告中,我们证明在建设性数学的设置中不存在不对称(有面向道路的)和对称(有不面向道路的)旅行推销员问题的这种算法。
相关内容
微信扫码咨询专知VIP会员