分支限界算法解决数独问题

A. 数独高级解法有哪些

具体如下：

1、联除法：在两行三个隔膜中查找相同的数字，然后用它们查找另一行中的位数。该方法适用于中、高级数独。

2、巡格法：找出每个横膈膜数字的频率，找出它的位置。

3、排它法：这种方法是解决问题的关键，容易被普通老百姓所忽视。观察队列或横膈膜，如果有一个位置不能被其他数字填补，填补剩下的数字。

4、待定法：这种方法不常使用，但很有效。在区域中临时定位一个数字，并将其用于排除。

5、行列法：该方法用于提高破阶求解问题的效率。

6、假设法：作为专家，我并不主张这种做法。

7 、频率法：这种方法比以前的方法更有效。列出行中或框中的所有情况，然后选择一个高频率的数字。

8、用候选方法解决数独问题的候选算法首先，必须建立一个候选列表。在不同的条件下，每个宫格不可能的候选人可以逐步和安全地被清除。

候选数方法可以用来解决复杂的数独问题，但是候选数方法的使用不像直觉方法那样直接，需要建立候选人名单的准备过程，所以实际使用可以先用可视化方法解决问题，而不能用候选人的方法来解决问题。

候选人数方法的解决方法是逐步排除不合适候选数的过程，所以在删除候选数时一定要小心，要确定删除的候选人是否安全，否则，多次都要重做的问题。在电脑软件的帮助下，使得候选数表的维护变得轻松起来。

常规解题手法：

依解题填制的过程可区分为直观法与候选数法。

直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。

候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空格做为解题线索的参考，可填数字称为候选数(Candidates，或称备选数)。

直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。

B. dijakstra算法和分支限算法在解决单源最短路径问题的异同

记dijakstra算法为D算法
D算法为贪心算法,每一步的选择为当前步的最优,复杂度为O(n*n) (又叫爬山法)
分支限界算法,每一步的扩散为当前耗散度的最优,复杂度为(没算)

都是A算法的极端情况
(说错了哈,下面我的文字中的的分支限界算法实际上是在说动态规划法,我查了一下书,动态规划法是对分支限界法的改进,分支限界法不属于A算法(启发式搜索算法),但是这时用动态规划法和D算法比较也是有可比性的,而直接用分支限界算法和D算法比较也是可以的)
关键词:耗散度 评估函数
即:对当前优先搜索方向的判断标准为,有可能的最优解
而最优解可以用一个评估函数来做,即已经有的耗散度加上以后有可能的耗度
A算法就是把两个耗散度加在一起,作为当前状态的搜索搜索方向;
但是对以后的耗散度的评估是麻烦的,D算法就是把当前有的路的最短的作为,以后耗散度的评估.
分支限界算法就是只以以前的耗散度为评估函数

你给的两个算法当然是A算法的特例
你还可以参考一下 A*算法 修正的A*算法,相信对你的编程水平有帮助

参考:
队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。按照规则，这样的结点不被列入活结点表。

优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值p来表示。最大优先队列规定p值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，体现最大效益优先的原则。类似地，最小优先队列规定p值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，体现最小优先的原则。采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的p值。

C. 用分支限界法求解0/1背包问题

1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

#include

struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};

int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;

void Init_good()
{
bag=new good [number];

for(int i=0; i {
cout<<"请输入第件"<cin>>bag[i].weight;
cout<<"请输入第件"<cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout< }

}

int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num {
w=w+bag[num].weight;
p=w+bag[num].benefit;
}

*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}

void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界

for(int i=0; i {
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志

if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}

}

void Display()
{

cout<<"可以放入背包的物品的编号为：";
for(int i=0; iif(bag[i].flag>0)

cout<
｝

参考：
http://cache..com/c?word=%B7%D6%D6%A7%3B%CF%DE%BD%E7%3B%B7%A8%3B%C7%F3%BD%E2%3B0%2C1%3B%B1%B3%B0%FC%3B%CE%CA%CC%E2&url=http%3A//www%2Edaxiongonline%2Ecom/dvbbs/dispbbs%2Easp%3FboardID%3D31%26ID%3D1016&b=10&a=0&user=