我正在尝试一系列不同的算法来寻找旅行商问题的近似最优解,其中一种方法是蛮力方法 - 检查n个城市之间的每条可能路径,并简单地返回最佳路径.这是一个O(n!)算法,因此很自然地需要很长时间才能执行大量城市.
我想提高我的暴力实施的效率,我注意到的一件事是你不必检查城市的每一个排列.例如,如果您有城市1,2,3和4,则路径(1-2-3-4)与路径(2-3-4-1)的长度相同.路径(3-4-1-2)和(4-1-2-3)也是如此.通过利用这一事实,我们应该能够将蛮力算法的复杂性从O(n!)降低到O((n-1)!),甚至O((n-1)!/ 2)如果我们意识到所有路径都可以反转而不影响它们的长度.
基本上,我正在寻找一种能够从一组不同的整数生成循环排列的算法.如果算法将"镜像"排列视为等效(例如1-2-3和3-2-1是相同的,因此只需要其中一个),这也是很好的.有谁知道这样做的方法？Java实现会很精彩,但我会采取任何措施!
我想从[2,3,4,5,6,7,8]中找到拔除3、4或5个数字的所有排列，允许重复，这样它们的总和为16。所以[8,5,3 ]，[8,3,5]和[4,3,3,3,3]是有效的排列。同样，也应删除循环排列，以使[3,3,3,3,4]也不会添加到答案中。我可以在Ruby中执行此操作，而无需允许这样的重复：
d = [2,3,4,5,6,7,8]
number_of_divisions = [3,4,5]
number_of_divisions.collect do |n|
d.permutation(n).to_a.reject do |p|
p[0..n].inject(0) { |sum,x| sum + x } != 16
end
end
如何允许重复，以便包含[3,3,3,3,4]？
鉴于问题：查找字符串的所有循环排列
例如：给定一个字符串：“abcd”
字符串的所有循环排列将是：“abcd”、“dabc”、“cdab”、“bcda”
这是我尝试过的：
for(int i = 0; i < str.size(); i++){
permu.push_back(str);
str.insert(0, 1, str[str.size()-1]);
str.erase(str.end()-1);
}
由于插入和擦除函数需要 O(n) 使整体解决方案 O(n^2)
有没有办法在 O(n) 或更少的时间内解决这个问题？