java回溯模板（Java回溯演算法）

本文目錄一覽：

• 1、Java或者C/C++怎麼用回溯法解決最小長度電路板排列問題
• 2、java回溯法如何執行
• 3、JAVA回溯編程，如何實現圖中的功能

Java或者C/C++怎麼用回溯法解決最小長度電路板排列問題

以java為例，希望能夠幫到你。

電路板排列問題

問題描述

將n塊電路板以最佳排列方式插入帶有n個插槽的機箱中。n塊電路板的不同排列方式對應於不同的電路板插入方案。設B={1, 2, …, n}是n塊電路板的集合，L={N1, N2, …, Nm}是連接這n塊電路板中若干電路板的m個連接塊。Ni是B的一個子集，且Ni中的電路板用同一條導線連接在一起。設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入的電路板編號是x[i]。x所確定的電路板排列Density (x)密度定義為跨越相鄰電路板插槽的最大連線數。

例：如圖，設n=8, m=5，給定n塊電路板及其m個連接塊：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中兩個可能的排列如圖所示，則該電路板排列的密度分別是2，3。

左上圖中，跨越插槽2和3,4和5，以及插槽5和6的連線數均為2。插槽6和7之間無跨越連線。其餘插槽之間只有1條跨越連線。在設計機箱時，插槽一側的布線間隙由電路板的排列的密度確定。因此，電路板排列問題要求對於給定的電路板連接條件(連接塊)，確定電路板的最佳排列，使其具有最小密度。

問題分析

電路板排列問題是NP難問題，因此不大可能找到解此問題的多項式時間演算法。考慮採用回溯法系統的搜索問題解空間的排列樹，找出電路板的最佳排列。設用數組B表示輸入。B[i][j]的值為1當且僅當電路板i在連接塊Nj中。設total[j]是連接塊Nj中的電路板數。對於電路板的部分排列x[1:i]，設now[j]是x[1:i]中所包含的Nj中的電路板數。由此可知，連接塊Nj的連線跨越插槽i和i+1當且僅當now[j]0且now[j]！=total[j]。用這個條件來計算插槽i和i+1間的連線密度。

重點難點

演算法具體實現如下：

//電路板排列問題 回溯法求解

#include “stdafx.h”

#include iostream

#include fstream

using namespace std;

ifstream fin(“5d11.txt”);

class Board

{

friend int Arrangement(int **B, int n, int m, int bestx[]);

private:

void Backtrack(int i,int cd);

int n,      //電路板數

m,      //連接板數

*x,     //當前解

*bestx,//當前最優解

bestd,  //當前最優密度

*total, //total[j]=連接塊j的電路板數

*now,   //now[j]=當前解中所含連接塊j的電路板數

**B;    //連接塊數組

};

template class Type

inline void Swap(Type a, Type b);

int Arrangement(int **B, int n, int m, int bestx[]);

int main()

{

int m = 5,n = 8;

int bestx[9];

//B={1,2,3,4,5,6,7,8}

//N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}

cout”m=”m”,n=”nendl;

cout”N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}”endl;

cout”二維數組B如下：”endl;

//構造B

int **B = new int*[n+1];

for(int i=1; i=n; i++)

{

B[i] = new int[m+1];

}

for(int i=1; i=n; i++)

{

for(int j=1; j=m ;j++)

{

finB[i][j];

coutB[i][j]” “;

}

coutendl;

}

cout”當前最優密度為:”Arrangement(B,n,m,bestx)endl;

cout”最優排列為：”endl;

for(int i=1; i=n; i++)

{

coutbestx[i]” “;

}

coutendl;

for(int i=1; i=n; i++)

{

delete[] B[i];

}

delete[] B;

return 0;

}

//核心代碼

void Board::Backtrack(int i,int cd)//回溯法搜索排列樹

{

if(i == n)

{

for(int j=1; j=n; j++)

{

bestx[j] = x[j];

}

bestd = cd;

}

else

{

for(int j=i; j=n; j++)

{

//選擇x[j]為下一塊電路板

int ld = 0;

for(int k=1; k=m; k++)

{

now[k] += B[x[j]][k];

if(now[k]0  total[k]!=now[k])

{

ld ++;

}

}

//更新ld

if(cdld)

{

ld = cd;

}

if(ldbestd)//搜索子樹

{

Swap(x[i],x[j]);

Backtrack(i+1,ld);

Swap(x[i],x[j]);

//恢復狀態

for(int k=1; k=m; k++)

{

now[k] -= B[x[j]][k];

}

}

}

}

}

int Arrangement(int **B, int n, int m, int bestx[])

{

Board X;

//初始化X

X.x = new int[n+1];

X.total = new int[m+1];

X.now = new int[m+1];

X.B = B;

X.n = n;

X.m = m;

X.bestx = bestx;

X.bestd = m+1;

//初始化total和now

for(int i=1; i=m; i++)

{

X.total[i] = 0;

X.now[i] = 0;

}

//初始化x為單位排列並計算total

for(int i=1; i=n; i++)

{

X.x[i] = i;

for(int j=1; j=m; j++)

{

X.total[j] += B[i][j];

}

}

//回溯搜索

X.Backtrack(1,0);

delete []X.x;

delete []X.total;

delete []X.now;

return X.bestd;

}

template class Type

inline void Swap(Type a, Type b)

{

Type temp=a;

a=b;

b=temp;

}

演算法效率

在解空間排列樹的每個節點處，演算法Backtrack花費O(m)計算時間為每個兒子節點計算密度。因此計算密度所消耗的總計算時間為O(mn!)。另外，生成排列樹需要O(n!)時間。每次更新當前最優解至少使bestd減少1，而演算法運行結束時bestd=0。因此最優解被更新的額次數為O(m)。更新最優解需要O(mn)時間。綜上，解電路板排列問題的回溯演算法Backtrack所需要的計算時間為O(mn!)。

程序運行結果為：

java回溯法如何執行

回溯法也稱為試探法，該方法首先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。 1、回溯法的一般描述 可用回溯法求解的問題P，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關於n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。 解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。 我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（ji）元組（x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反D中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反D中僅涉及到x1，x2，…，xi的一個約束，n≥ij。因此，對於約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。 回溯法首先將問題P的n元組的狀態空間E表示成一棵高為n的帶權有序樹T，把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。樹T類似於檢索樹，它可以這樣構造： 設Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構造方式，E中的一個n元組（x1，x2，…，xn）對應於T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，xn，反之亦然。另外，對於任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應於T中的一個非葉子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個n元組的空前綴（），對應於T的根。 因而，在E中尋找問題P的一個解等價於在T中搜索一個葉子結點，要求從T的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從根出發，按深度優先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。 在回溯法中，上述引入的樹被稱為問題P的狀態空間樹；樹T上任意一個結點被稱為問題P的狀態結點；樹T上的任意一個葉子結點被稱為問題P的一個解狀態結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題P的一個回答狀態結點，它對應於問題P的一個解。 【問題】 組合問題 問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。 例如n=5，r=3的所有組合為： （1）1、2、3 （2）1、2、4 （3）1、2、5 （4）1、3、4 （5）1、3、5 （6）1、4、5 （7）2、3、4 （8）2、3、5 （9）2、4、5 （10）3、4、5 則該問題的狀態空間為： E={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5} 約束集為： x1x2x3 顯然該約束集具有完備性。 問題的狀態空間樹T： 2、回溯法的方法 對於具有完備約束集D的一般問題P及其相應的狀態空間樹T，利用T的層次結構和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為： 從T的根出發，按深度優先的策略，系統地搜索以其為根的子樹中可能包含著回答結點的所有狀態結點，而跳過對肯定不含回答結點的所有子樹的搜索，以提高搜索效率。具體地說，當搜索按深度優先策略到達一個滿足D中所有有關約束的狀態結點時，即「激活」該狀態結點，以便繼續往深層搜索；否則跳過對以該狀態結點為根的子樹的搜索，而一邊逐層地向該狀態結點的祖先結點回溯，一邊「殺死」其兒子結點已被搜索遍的祖先結點，直到遇到其兒子結點未被搜索遍的祖先結點，即轉向其未被搜索的一個兒子結點繼續搜索。 在搜索過程中，只要所激活的狀態結點又滿足終結條件，那麼它就是回答結點，應該把它輸出或保存。由於在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點後，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結點均已被搜索過為止。 例如在組合問題中，從T的根出發深度優先遍歷該樹。當遍歷到結點（1，2）時，雖然它滿足約束條件，但還不是回答結點，則應繼續深度遍歷；當遍歷到葉子結點（1，2，5）時，由於它已是一個回答結點，則保存（或輸出）該結點，並回溯到其雙親結點，繼續深度遍歷；當遍歷到結點（1，5）時，由於它已是葉子結點，但不滿足約束條件，故也需回溯。 3、回溯法的一般流程和技術 在用回溯法求解有關問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般採用非遞歸方法。下面，我們給出回溯法的非遞歸演算法的一般流程： 在用回溯法求解問題，也即在遍歷狀態空間樹的過程中，如果採用非遞歸方法，則我們一般要用到棧的數據結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯過程。 例如在組合問題中，我們用一個一維數組Stack[ ]表示棧。開始棧空，則表示了樹的根結點。如果元素1進棧，則表示建立並遍歷（1）結點；這時如果元素2進棧，則表示建立並遍歷（1，2）結點；元素3再進棧，則表示建立並遍歷（1，2，3）結點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或保存）。這時只要棧頂元素（3）出棧，即表示從結點（1，2，3）回溯到結點（1，2）。

JAVA回溯編程，如何實現圖中的功能

Java回溯沒接觸過。這題是剛開始下一狀態為不可使用狀態，想要實現如何從綠-》紅-》黑的變換嗎？方向是單向的