分支定界法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、缺點：要存儲很多葉子結點的限界和對應的耗費矩陣。花費很多內存空間。

存在的問題：分支定界法可應用於大量組合優化問題。其關鍵技術在於各結點權值如何估計，可以說一個分支定界求解方法的效率基本上由值界方法決定，若界估計不好，在極端情況下將與窮舉搜索沒多大區別。