0 c++ recursion traveling-salesman brute-force
我试图通过检查所有可能的排列来解决使用Brute Force程序的旅行商问题.我用c ++完成了.
主要问题是:代码适用于小输入大小.但是当我给出包含16个笛卡尔坐标的文件作为输入并运行程序时,控制台会挂起.它没有显示任何东西.好像它会永远运行.这是什么主要原因？我正在使用Code Blocks编译器.
用于旅行商问题的强力算法具有大约O(N!)的复杂度.
这意味着,例如,10个项目有大约3,628,800组合供您检查.仅仅为了讨论,让我们说你的计算机可以在半秒内完成.
在这种情况下,你试图用16分来解决.这不到两倍大,所以看起来好像不应该花更长的时间,对吗？事实上,16!是20,922,789,888,000.如果10个项目的工作需要0.5秒,则需要大约5,765,760*.5秒,大约需要33.4天 - 即每天24小时运行超过一个月.
当然,半秒钟只是一个猜测 - 如果它只是十分之一秒,那么我们预计16件版本只需要一周时间.另一方面,如果它真的接近一整秒,那么16项任务应该需要几个月左右.