算法实验报告回溯法(c语言)

《算法实验报告回溯法(c语言)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、（2015/2016学年第一学期）课程名称算法设计与分析实验名称冋溯法实验时间2016年5月5口指导单位计算机软件学院指导教师费宁学生姓名罗熊班级学号B14050123学院（系）自动化专业自动化实验报告实验名称回溯法指导教师费宁实验类型验证实验学时2实验时间2016.5.5一、实验目的和要求在算法设计中，回溯法是比贪心法更-•般的方法，掌握回溯法的的适用条，熟练地适用冋溯法求解实际问题。在本实验中用冋溯法求解8皇后问题。二、实验环境(实验设备)VC++6.0三、实验原理及内容：实验原理：用冋溯法求解的问题通常需要给岀某些必须满足的约束条件。

2、这些约束条件分为显式约朿和隐式约朿。用于规定每个；d取值的约束条件称为显示约束，显示约朿规定了所冇可能的元组，它们组成了M题的候选解集，称为M题的解空间。隐式约束给出了判定一个候选解集是否为可行解的一般条。宥隐式约束设计一个判定函数P()，使得当且仅当p()为真时，n-元组是问题的满足隐式约束的一个可行解。目标函数用来衡量每个可行解的优劣，使目标函数去最大值或最小值得可行解为问题的最优解。实验代码#include#include#definemax8intqueen[max],sum=0;voidsho

3、w(){inti;printf(”(”)；for(i=0;i

4、

5、abs(queen[i]-queen[n])==(n-i))return1;return0;}voidNQUEENS(intn){inti;for(i=0;i

6、show();}else{NQUEENS(n+1);}}}}intmain(){NQUEENS(O);printf(’’％dn，sum);system("pause’’);return0;}:实验结果：回>>>134114565526056336716776641663130777343416316030446602671220307027053070477343525770362570477034660100177345660724561167111337774566344556670444455555555000011111111222

7、2222222222■C:UsersLXDesktop算法Debughuisu.exe’25713064〉<26174035><26175304><27360514><30471625><30475261><31475026〉<31625704〉<31625740〉<31640752>(31746025><31750246><35041726〉<35716024〉<35720641〉<36074152>(36271405><36415027><36420571〉<37025164〉<37046152〉<37420615><403

8、57162><40731625><40752613〉■J■C:UsersLXDesktop>^^Debughuisu.exeMCDI40752613〉<41357206>(41362750〉<41506372〉<41703625〉<42057136〉<42061753〉——<42736051〉(46027531〉<46031752〉<46137025〉(4615203?〉<46152073〉<46302751〉<47302516〉<47306152〉<50417263〉<51602473〉(51603742〉<52064713〉<

9、52073164〉<52074136〉<52460317><52470316〉<52613704〉▼r^5"C:UsersLXDesktop®?^Debughuisu.exe"i—Ir°iU!实验小结回溯法以深度优先次序生成状态空间树中的结点，并使用剪纸函数减少实际生成的结点数，回溯法是一种广泛适用的算法设计技术。是要问题的解是元组形式，可用状态空问树描述，并采用判定函数识别答案结点，就能采用冋溯法求解。冋溯法使用约束函数剪40752613〉<41357206>(41362750〉<41506372〉<41703625〉<420

10、57136〉<42061753〉——<42736051〉(46027531〉<46031752〉<46137025〉(4615203?〉<46152073〉<46302751〉<