学习回溯算法过程中的一些体会
这么久跟着老师学习,用回溯的算法做了很多题目,其中包括:1集合求子集问题
2.集合求子集的全排列
2.迷宫问题
3.n皇后问题
4.0/1背包问题
5.两个城市之间夹杂多个城市,要求通过2者之间的所有城市,求两个城市的最小距离(不是图里的最短路径问题哦)
通过做了上面5道题,基本理解了回溯算法,她就是树的深搜不同结果,到最后一层就退回上一层,当然不满足她的约束条件也返回到上一层(有人将她亲切称为剪枝),她其实有个编程框架:
主函数(……int k)//用k表示深搜到树的第k层了
{
if(到了最后一层的下一层)
{
将结果print出来(如果要求最优路径就先缓一缓,将结果存在一个临时数组里, 用个min比较一下结果,最后存下最小的结果)
}
else
{
if(满足条件) //一般有个chenk()函数和一个数组flag标记走过了哪一步
{
将走过的flag标记为已走过了
for(int i=0;i<n;i++) //n表示第k层有几个分支
{
主函数(……k+1) //递归调用进入k+1层
}
最后千万记住将flag标记还原为未走过,这个非常重要//当然有时也不用还原
}
}
}
我现在也在学习总结阶段,可能总结的不好（其实这种框架很多书上都有）,请大家见谅,有个学习算法的学习方法推荐给像我一样迷茫的初学者,"记住----->应用------->忘记-------->创造", 这个方法适合很多方面的学习,今天太晚了,有时间会发源代码给希望学习的初学者,大家有任何问题都可以讨论一下,我不聪明,也曾经懒惰过(现在仍然会懒惰),我半年前连c中指针传址传值还不能完全弄懂,直到一天,我看到了一句话:
每个人都有潜在的能量，只是很容易:被习惯所掩盖，被时间所迷离,被惰性所消磨!
我知道我必须改变自己,也许不聪明,也许反应慢,但我可以花别人十倍的时间去理解那些对我有用的知识(当然我现在也花过别人十倍的时间去玩游戏),希望每个像我一样被习惯所掩盖、被时间所迷离、被惰性所消磨的朋友大家一起努力激发自己的无限潜能改变所有人对你的看法，如果你可以为网络游戏玩n个通宵， 为什么不能为了学习数据结构而编n个通宵的代码呢？（我曾为了玩三国志这种单机游戏玩过30个通宵，所以，我把编程当成三国志玩，希望早日“一统天下”，就算我不够聪明（三国我只玩吕布的，智力低成20多真没救了），就算时间会很长，我依然坚持着）。
我很罗嗦的，但仍然处在迷茫阶段的初学者请记住我最后一句话
“既然选择了就千万不要后悔，因为后悔是一种耗费精神的情绪.后悔是比损失更大的损失,比错误更大的错误.所以请不要后悔。 ”
[此贴子已经被作者于2007-5-28 21:54:14编辑过]
