TSP 与 Word Unscrambler
TSP vs. Word Unscrambler
输出给定的乱序词是否是真正的英文单词的任务是否与旅行商问题等价？一个众所周知的策略是生成给定单词的所有排列，并将它们与英语词典中的所有单词进行比较。该算法的时间复杂度为 O(N!)。我可以想象这两者在一个重要方面有所不同：一旦找到与单词匹配的排列，就可以停止生成排列，而使用 TSP 时，无论如何都必须尝试所有路径组合。然而，我编写了一个算法，它不是生成长度为 n 的给定单词的所有排列，而是对给定单词中的字母进行排序并对字典，然后比较两个排序后的字符串（此方法 100% 有效）。我的算法使用默认的Java排序，研究后发现它运行在O(n log n)。总的来说，我的程序在 O(n log n) 运行，因为随着 n 接近无穷大，该项增长最大。该算法的运行时间少于多项式时间。
那么，如果问题是等价的，难道不能用类似的方法来解决TSP问题吗？这与 P 与 NP 有什么关系？
很抱歉，如果这些没有任何意义或者我没有正确使用术语，我在这个领域没有经验
存在解决两个问题的相同复杂度的算法这一事实并不一定意味着这些问题具有相同的复杂度，因为对于其中一个问题可能存在更有效的算法，但对于另一个问题则不存在。
关联不同问题复杂性的正确方法是归约：如果你能证明问题A的任何实例都可以是转换为问题 B 的实例，转换实例的答案与原始实例的答案相同，然后是问题 B至少和问题A一样复杂（因为求解B的算法也可以求解A).如果你也可以显示相反方向的减少，A 和 B 同样复杂。
对于您的情况，目前没有已知的方法可以将任意 TSP 问题转换为等效的解密问题，因此（据我们所知）这些问题并不具有相同的复杂性。
输出给定的乱序词是否是真正的英文单词的任务是否与旅行商问题等价？一个众所周知的策略是生成给定单词的所有排列，并将它们与英语词典中的所有单词进行比较。该算法的时间复杂度为 O(N!)。我可以想象这两者在一个重要方面有所不同：一旦找到与单词匹配的排列，就可以停止生成排列，而使用 TSP 时，无论如何都必须尝试所有路径组合。然而，我编写了一个算法，它不是生成长度为 n 的给定单词的所有排列，而是对给定单词中的字母进行排序并对字典，然后比较两个排序后的字符串（此方法 100% 有效）。我的算法使用默认的Java排序，研究后发现它运行在O(n log n)。总的来说，我的程序在 O(n log n) 运行，因为随着 n 接近无穷大，该项增长最大。该算法的运行时间少于多项式时间。
那么，如果问题是等价的，难道不能用类似的方法来解决TSP问题吗？这与 P 与 NP 有什么关系？
很抱歉，如果这些没有任何意义或者我没有正确使用术语，我在这个领域没有经验
存在解决两个问题的相同复杂度的算法这一事实并不一定意味着这些问题具有相同的复杂度，因为对于其中一个问题可能存在更有效的算法，但对于另一个问题则不存在。
关联不同问题复杂性的正确方法是归约：如果你能证明问题A的任何实例都可以是转换为问题 B 的实例，转换实例的答案与原始实例的答案相同，然后是问题 B至少和问题A一样复杂（因为求解B的算法也可以求解A).如果你也可以显示相反方向的减少，A 和 B 同样复杂。
对于您的情况，目前没有已知的方法可以将任意 TSP 问题转换为等效的解密问题，因此（据我们所知）这些问题并不具有相同的复杂性。