回溯算法是以深度优先搜索解的方法,以前还不是很熟悉递归,不过今天仔细想了想递归回溯搜索解确实是个简单快速的求解方法,就是有时候想的有点烧脑...
题目:给出abcd...这些字母求他们的全部排列组合
这个实际上用matlab自带的perms函数一下就能求解一个全排列矩阵,然后把1,2,3...这些数用a,b,c...字母代替就行,不过那样复杂度就大了,毕竟没有原生为字母排列的函数,那么用回溯法递归求解该问题matlab可编写如下:
function result = abcPerms(n) result.count = 0; result.cell = {}; result = traceback(result, \'\', 0:n-1); function result = traceback(result, cur, arr) base = abs(\'a\'); if isempty(arr) result.count = result.count + 1; result.cell{result.count} = cur; disp(cur); return; end for i = 0:length(arr)-1 result = traceback(result, [cur,char(base+arr(i+1))], arr(~(arr==arr(i+1)))); end end end
如执行abcPerms(3)即可得到结果:
>> abcPerms(3)
abc
acb
bac
bca
cab
cba
ans =
包含以下字段的 struct:
count: 6
cell: {\'abc\' \'acb\' \'bac\' \'bca\' \'cab\' \'cba\'}
请发表评论