回溯算法

理论依据： 多米诺性质

典型实例

八皇后问题：

int flag[8]//标志数组，下标代表列数，值代表行数
伪代码：

for j=1 to 8:
　　if flag[j]==0:
　　　 if 处于同一对角线
　　　 then 不做处理
　　　 else flag[j]=i;

时间复杂度：O(n^n)其实我也不是很清楚

0-1背包问题

getValue(index,value,weight)
空间结构：子集树 时间复杂度O(a^n) 2 ^ n

货郎问题

空间结构：排列树：时间复杂度O(n!)[如果给定结点那么(n-1)!，如果没有给定结点则n!]

整数不等式问题

注意，这里有一个巧妙的变换。因为-x3不满足多米诺性质，所以需要化减为加

装载问题

子集树：时间复杂度O(2^N)
很简单的问题，用递归的回溯很好实现，难点在于用伪码的实现。感觉伪代码很难实现递归


模拟局部过程：如果1100100和1100011都是可行解
算法肯定会先经过1100100，之后i=8进行Backtrack(8)
1100000：i=6时再进行while，得到结果1100011
i=8进行Backtrack(8)。当i=7时间，置1为0再i++，此时i=8
进入while,结果1100010
i=8进行Backtrack(8)。当i=6时间，置1为0再i++，此时i=7
进入while,结果1100001
i=8进行Backtrack(8)。当i=7时间，置1为0再i++，此时i=8
进入while,结果1100000
此时再进入Backtrack后，就会i=2再置i为0，说明回溯算法有效
关键点在于，Backtrack后返回的i是i++

着色问题

时间复杂度：n个节点，每个节点都有m种着色的可能。着色的时候判断是否相邻着色需要O（n）
降低时间复杂度的方法：对于第一个节点，只需判断一种着色方案 分配个数*m
或者对于第一个和第二个节点，判断一种着色 *m(m-1)

蒙特卡洛方法