java回溯法

⑴ 五大基本演算法——回溯法

回溯法是一種選優搜索法（試探法）。

基本思想：將問題P的狀態空間E表示成一棵高為n的帶全有序樹T，把求解問題簡化為搜索樹T。搜索過程採用 深度優先搜索 。搜索到某一結點時判斷該結點是否包含原問題的解，如果包含則繼續往下搜索，如果不包含則向祖先回溯。

通俗來說，就是利用一個樹結構來表示解空間,然後從樹的根開始深度優先遍歷該樹，到不滿足要求的葉子結點時向上回溯繼續遍歷。

幾個結點：
擴展結點：一個正在產生子結點的結點稱為擴展結點
活結點：一個自身已生成但未全部生成子結點的結點
死結點：一個所有子結點已全部生成的結點

1、分析問題，定義問題解空間。

2、根據解空間，確定解空間結構，得 搜索樹 。

3、從根節點開始深度優先搜索解空間（利用 剪枝 避免無效搜索）。

4、遞歸搜索，直到找到所要求的的解。

1、子集樹
當問題是：從n個元素的集合S中找出滿足某種性質的子集時，用子集樹。
子集樹必然是一個二叉樹。常見問題：0/1背包問題、裝載問題。

遍歷子集樹時間復雜度：O（2^n）

2、排列樹
當問題是：確定n個元素滿足某種排列時，用排列數。常見問題：TSP旅行商問題，N皇後問題。

遍歷排列樹時間復雜度：O（n!）

通俗地講，結合java集合的概念，選擇哪種樹其實就是看最後所得結果是放入一個List（有序）里，還是放入一個Set（無序）里。

剪枝函數能極大提高搜索效率，遍歷解空間樹時，對於不滿足條件的分支進行剪枝，因為這些分支一定不會在最後所求解中。

常見剪枝函數：

約束函數（對解加入約束條件）、限界函數（對解進行上界或下界的限定）

滿足約束函數的解才是可行解。

1、0/1背包問題

2、TSP旅行商問題

3、最優裝載問題

4、N-皇後問題

具體問題可網路詳細內容。

⑵ 求java中文分類實現過程代碼

這是一個強大的語義+語法+詞法分析器，很難很強大
做好了，你可以試試來網路工作

⑶ java 深度優先搜索（回溯法）求集合的冪集

import java.util.ArrayList;
import java.util.List;

public class BackTrack {
public static void main(String[] args) {
//初始化一個集合，放在list裡面
List<String> list=new ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("f");
List<String> li=new ArrayList<String>();
PowerSet(0,list,li);
}
//回溯法求冪集
public static void PowerSet(int i,List<String> list,List<String> li){

if(i>list.size()-1){System.out.println(li);}
else{
li.add(list.get(i));//左加
PowerSet(i+1,list,li); //遞歸方法
li.remove(list.get(i)); //右去
PowerSet(i+1, list, li);
}
}

}

註：該方法採用中序遍歷二叉樹（實際這棵樹是不存在的）。對於第一個元素，左節點加進去，右節點去掉。對於第i一個節點，左加，右去。直到i大於元素的總個數。

輸出結果：
[1, 2, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 2]
[1, 3, 4]
[1, 3]
[1, 4]
[1]
[2, 3, 4]
[2, 3]
[2, 4]
[2]
[3, 4]
[3]
[4]
[]

⑷ 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。

⑸ JAVA中八皇後問題演算法和流程圖。要求用回溯法，求大神解答，在線等如果有代碼就完美了

[cpp] view plainprint?
//--------------------------------------
//利用函數遞歸，解決八皇後問題
//
// zssure 2014-03-12
//--------------------------------------

#include <stdio.h>
#include <cmath>

int count=0;//全局計數變數

/*--------------------四個皇後----------------------*/
//#define QUEEN_NUM 4
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0 };

/*--------------------五個皇後----------------------*/
//#define QUEEN_NUM 5
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0 };

/*--------------------六個皇後----------------------*/
//#define QUEEN_NUM 6
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0
// };

/*--------------------七個皇後----------------------*/
//#define QUEEN_NUM 7
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0
// };

/*--------------------八個皇後----------------------*/
#define QUEEN_NUM 8
int label[QUEEN_NUM][QUEEN_NUM]={0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0};

void FillChessbox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n))//對角區域填充
{
if(label[i][j]==0)
label[i][j]=num;
}

int i=0,j=0;
while(i<QUEEN_NUM)//行填充
{
if(label[i][n]==0)
label[i][n]=num;
++i;
}
while(j<QUEEN_NUM)//列填充
{
if(label[m][j]==0)
label[m][j]=num;
++j;
}

}
void ClearChessBox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n) && label[i][j]==num)
label[i][j]=0;
int i=0,j=0;
while(i<QUEEN_NUM)
{
if(label[i][n]==num)
label[i][n]=0;
++i;
}
while(j<QUEEN_NUM)
{
if(label[m][j]==num)
label[m][j]=0;
++j;
}
}
void AllClear()
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
label[i][j]=0;

}
void PrintResult()
{
for(int i=0;i<QUEEN_NUM;++i)
{
for(int j=0;j<QUEEN_NUM;++j)
printf("%d ",label[i][j]);
printf("\n");

}
}
bool EightQueen(int n/*皇後個數*/,int c/*已經放置的皇後個數*/)
{
//static int count=0;
//小於3x3的棋盤是無解的
if(n<4)
return false;

for(int i=0;i<n;++i)
{
if(label[c-1][i]==0)//存在可以放置第c個皇後的位置
{
label[c-1][i]=c+1;
if(c==n)/*已經放置完畢所有的皇後*/
{
++count;
PrintResult();
printf("**************************\n");
ClearChessBox(c-1,i,c+1);
//AllClear();
return true;
}
FillChessbox(c-1,i,c+1);
EightQueen(n,c+1);
ClearChessBox(c-1,i,c+1);
/*-------------------------------------------------------------------------------------------------------------------------
// 現場恢復，無論下一個皇後是否順利放置，都應該恢復現場。原因是
//
// 如果下一個皇後放置失敗，那麼自然應該將本次放置的皇後去除，重新放置，所以需要進行現場恢復（即回溯）；
// 如果下一個皇後放置成功，意味著本次放置已經滿足條件，是一個解，此時需要恢復現場，進行下一次的重新放置，尋找下一個解。
//
//------------------------------------------------------------------------------------------------------------------------*/
//if(!EightQueen(n,c+1))
// ClearChessBox(c-1,i,c+1);

}
}
return false;
}

int main()
{
EightQueen(QUEEN_NUM,1);
printf("%d\n",count);
return 0;
}