文章目錄

• • 前言
  • 搜索框架
  • 經典問題

前言

• 搜索與回溯是計算機解題中常用的算法，很多問題無法根據某種確定的計算法則來求解，可以利用搜索與回溯的技術求解?；厮菔撬阉魉惴ㄖ械囊环N控制策略。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發現原來的選擇是錯誤的，就退回一步重新選擇，繼續向前探索，如此反復進行，直至得到解或證明無解。
• 如迷宮問題：進入迷宮后，先隨意選擇一個前進方向，一步步向前試探前進,如果碰到死胡同，說明前進方向已無路可走，這時，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走，則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無解為止。

搜索框架

搜索偽代碼/公式
基本上所有的搜索與回溯都是這個公式的變種

void Search(int k) {for (i=1;i<=算符種數;i++)if (滿足條件){保存結果if (到目的地) 輸出解;else Search(k+1);恢復：保存結果之前的狀態{回溯一步}} }

經典問題

【問題1】八皇后問題

• 題目

八皇后問題：要在國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一對角線的任意棋子。）

• 分析

放置第ｉ個(行)皇后的算法為：
int search(i)；
{
　　 int j;
　　　for (第i個皇后的位置j=1;j<=8;j++ ) //在本行的8列中去試
　　　if (本行本列允許放置皇后)
　　　　{
　　　　　放置第i個皇后；
對放置皇后的位置進行標記；
　　　　　if (i==8) 輸出 //已經放完個皇后
　　　　　　 else search(i+1)； //放置第i+1個皇后
　　　　　對放置皇后的位置釋放標記，嘗試下一個位置是否可行；
　　　　}
}

• 參考代碼

public class EightQueue {/*** 存放每一行，皇后的位置，a[1]=6，代表第一行的皇后放在位置6* */int[] a = new int[9];/*** 每一列，是否被放置了皇后* */int[] b = new int[9];/*** 左對角線是否放置了皇后* */int[] c = new int[17];/*** 右對角線是否放置了皇后* */int[] d = new int[17];/*** 解法的個數* */int num = 0;public void search(int n) {// 算符種類for (int i=1; i<=8; i++) {// 判斷是否可以放棋子if(b[i]==0 && c[n+i]==0 && d[n-i+8]==0) {// 保存條件a[n] = i;b[i] = 1;c[n+i] = 1;d[n-i+8] = 1;// 目的地if (n == 8) {print(a);num ++;} else {search(n + 1);}// 回溯b[i] = 0;c[n+i] = 0;d[n-i+8] = 0;}}}public void print(int[] a) {for (int i=1; i<a.length; i++) {System.out.print(a[i] + " ");}System.out.println("");}public static void main(String[] args) {EightQueue e = new EightQueue();e.search(1);System.out.println("解法個數 " + e.num);//92個解} }

【問題2】自然數分解

任何一個大于1的自然數n，總可以拆分成若干個小于n的自然數之和

當n=7共14種拆分方法：
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14

【代碼實現】

public class SplitData {int[] a;int goal;/*** 任何一個大于1的自然數n，總可以拆分成若干個小于n的自然數之和* 算符種類：要分割的自然數n* 結果數組：a[n],存儲這分割的結果* */void search(int n, int t) {// 算符種類，從1開始，一直到nfor (int i=a[t-1]; i<=n; i++) {// 滿足條件,把分解的數字存入數組并在n基礎上減去// 當前數i要大于等于前1位數，且不過nif(i < goal) {a[t] = i;n -= i;if (n == 0) {print(t);} else {search(n, t+1);}n += i;}}}public void print(int t) {System.out.println("結果為：");for (int i=1; i <= t; i++) {System.out.print(a[i] + " ");}System.out.println("");}public static void main(String[] args) {SplitData s = new SplitData();// 想要分解的自然數int n = 7;s.a = new int[n+1];for (int i=0; i<s.a.length; i++) {s.a[i] = 1;}s.goal = n;s.search(n,1);} }

總結

以上是生活随笔為你收集整理的Java实现搜索回溯经典题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。