ruby - 为 TSP 实现 map 的最佳方式

Question

用 ruby​​ 实现解决旅行商(旅游)问题的 map 的最佳方法是什么？大约有 25 个城市？最好使用图表并将到每个城市的每个距离作为顶点添加吗？或者 ruby​​ 是否有更好的方法来实现这一点？

Answer 1

这是一个人迹罕至的地区。 :)

“旅行推销员的行程表(#142)- Morton Goldberg

一位推销员想要拜访他的客户，每个客户都位于不同的城市。他要求您为他准备一个行程，以尽量减少他的驾驶里程。行程必须把他带到每个城市恰好一次，然后把他送回他的起点。你能写一个 Ruby 程序来生成这样的行程吗？

这个问题很有名并且已知是 NP 完全问题。那么，作为周末 Ruby 测验项目，您怎么能期望解决它呢？很不合理吧？是的，除非条件有所放宽。”

在 rubyquiz 的侧边栏中查看完整页面和多个解决方案