分支定界法python程序

㈠ C++:用分支界限法解决n皇后问题(急)

//改动n的值变成n皇后问题
#include<iostream.h>

const int n = 8 ; //8皇后问题.改动n可变成N皇后问题
const int n_sub = n - 1 ;
int queen[n] ; //N个棋子.N对应每一列,如n=0的棋子只下在0列,1下1....类推
bool row[n] ; //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive[2*n-1] ; //斜率为1的斜线方向上是不是有皇后
bool negative[2*n-1] ; //斜率为负1的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为0

int main()
{
int cur = 0 ;//游标,当前移动的棋子(哪一列的棋子)
bool flag = false ; //当前棋子位置是否合法
queen[0] = -1 ; //第0列棋子准备,因一开始移动的就是第0列棋子
int count = 0 ; //一共有多少种下法 ;
cout<<"开始！若n较大，运行很慢"<<endl ;

while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag) //当还不确定当前位置是否可下
{
queen[cur]++ ;
// cout<<"第"<<cur<<"列棋子开始走在第"<<queen[cur]<<"行"<<endl ;
// cin.get() ;
if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)
// cout<<"当前行是非法行,当前列棋子走完,没有合法位置,回溯上一列棋子"<<endl ;
// cin.get() ;
queen[cur] = -1 ; //当前列棋子置于准备状态
cur-- ; //回溯到上一列的棋子
if(cur>=0) {
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
//由于要移下一步,所以回溯棋子原位置所在行应该没有棋子啦.置row[]为false
//并且棋子对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;
}
else {
//先判断棋子所在行没有棋子
if(row[queen[cur]] == false) { //当前行没有棋子
// cout<<"棋子"<<cur<<"所在行没有其他棋子,正在检查斜线"<<endl ;
flag = true ; // 暂设为true,或与之前棋子斜交,则再设为false ;
//以下检查当前棋子是否与之前的棋子斜线相交
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
// cout<<"出现斜线相交,该位置不合法"<<endl ;
}
else
flag = true ;
if(flag) { //没有斜交,位置合法
// cout<<"斜线也没有相交,该位置合法"<<endl ;
if(cur == n-1) //如果是最后一个棋子
{
// cout<<"棋子走完一轮,总走法加1"<<endl ;
count++ ; //总走法加一 ;
}
row[queen[cur]] = true ;// 当前行设为有棋子
passive[queen[cur] + cur] = true ;//当前行正斜率方向有棋子
negative[n_sub + cur - queen[cur]] = true ; //当前行负斜率方向上也有棋子
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
}
flag = false ;
}
}
}//else
}
}
cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl ;
return 0 ;
}

㈡ 分支定界法的算法步骤

(1)求整数规划的松弛问题最优解。
(2)若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步。
(3)任意选一个非整数解的变量 ，在松弛问题中加上约束 及 +1组成两个新的松弛问题，称为分支。新的松弛问题具有如下特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题足求最小值时，目标值是分支问题的下界。
(4)检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于(max)等于其他分支的目标值，则将其他分支剪去不再计算，若还存在非整数解并且目标值大于( max)整数解的目标值，需要继续分支，再检查，直到得到最优解。

㈢ 什么是分支定界法

先不考虑整数限制，求出相应的线性规划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分可行域，将可行域D分成D1、D2两部分（分枝） ，然后分别求解这两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继续去掉不包含整数解的部分可行域，将可行域或分成与两部分，再求解与对应的线性规划，……，在计算中若已得到一个整数可行解，则以该解的目标函数值作为分枝的界限，如果某一线性规划的目标值Z≤Z0，就没有必要继续分枝，因为分枝（增加约束）的结果所得的最优解只能更差。反之若Z＞Z0，则该线性规划分枝后，有可能产生更好的整数解，一旦真的产生了一个更好的整数解，则以这个更好的整数解目标值作为新的界限，继续进行分枝，直至产生不出更好的整数解为止。

㈣ python做整数规划有什么算法包吗，要有分支定界的

lingo会自动选用求解器 整数规划会用integer solver 主要会用到分支定界法和枚举 你可以在lingo的option里面自己稍微调整 但是具体的算法不是你能改的 如果你要用自己的算法去做 需要自己写程序 lingo解决不了

㈤ 什么是分支定界法基本思想是什么一般用于解决什么问题

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：

1 ．产生当前扩展结点的所有子结点；

2 ．在产生的子结点中，抛弃那些不可能产生可行解（或最优解）的结点；

3 ．将其余的子结点加入活结点表；

4 ．从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

分支定界法本质还是一种枚举法，但是是隐枚举法。它是整数规划领域中非常重要的一类算法思想。是很多重要算法的源头。它能解决的实际问题很多，最着名的一个应该就是求解背包问题。

㈥ python做整数规划有什么算法包吗，要有分支

帮你找到一段简单的python代码，可能不是很全，不过有分支定界。

Mixed-Integer-Linear-Programmi

㈦ 分支定界法的介绍

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。

㈧ 3-2用分支定界法这两个题怎么做，求解

把以下程序存为ILP.m,%然后：clc;clear f=[4 4] A=[2 5;2 -2] b=[15;5] Aeq=[];beq=[]; LB=[0 0];UB=[]; [xn,yn]=ILp(f,A,b,Aeq,beq,LB,UB,[1 1],1,[])[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB,UB) 结果：xn =0 ...

㈨ 什么是分支定界法基本思想是什么

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。

基本思路
分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。

对于两个变量的整数规划问题，使用网格的方法有时更为简单。

㈩ 特征选择 分支定界法

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法.但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树。

分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后。

将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。

分支定界法算法分析：

1、算法优点：可以求得最优解、平均速度快。

因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。

2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。

存在的问题：分支定界法可应用于大量组合优化问题。其关键技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别。