小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

常用算法四（回溯算法）

 第一閱覽室 2014-04-19

1、概念

      回溯算法實(shí)際上一個(gè)類(lèi)似枚舉的搜索嘗試過(guò)程，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。

   回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為“回溯點(diǎn)”。

     許多復(fù)雜的，規(guī)模較大的問(wèn)題都可以使用回溯法，有“通用解題方法”的美稱(chēng)。

2、基本思想

   在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問(wèn)題的解，則逐層向其祖先結(jié)點(diǎn)回溯。（其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法）。

       若用回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹(shù)都要已被搜索遍才結(jié)束。

       而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。

3、用回溯法解題的一般步驟：

    （1）針對(duì)所給問(wèn)題，確定問(wèn)題的解空間：

            首先應(yīng)明確定義問(wèn)題的解空間，問(wèn)題的解空間應(yīng)至少包含問(wèn)題的一個(gè)（最優(yōu)）解。

    （2）確定結(jié)點(diǎn)的擴(kuò)展搜索規(guī)則

    （3）以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。

4、算法應(yīng)用示例：

八皇后問(wèn)題的遞歸實(shí)現(xiàn)

  1. public class Empress {    
  2.         
  3.     private int n ; //皇后個(gè)數(shù)    
  4.     private int[] x ; //當(dāng)前解    
  5.     private long sum ; //當(dāng)前已找到的可行方案數(shù)    
  6.     private static int h ;      //記錄遍歷方案序數(shù)    
  7.     
  8.     public Empress(){    
  9.         this.sum = 0 ;  //初始化方案數(shù)為1，當(dāng)回溯到最佳方案的時(shí)候，就自增1    
  10.         this.n = 8 ;    //求n皇后問(wèn)題，由自己定義    
  11.         this.x = new int[n+1];  //x[i]表示皇后i放在棋盤(pán)的第i行的第x[i]列    
  12.         h = 1 ; //這個(gè)是我額外定義的變量，用于遍歷方案的個(gè)數(shù)，請(qǐng)看backTrace()中h變量的作用，這里將它定義為static靜態(tài)變量    
  13.     }    
  14.     
  15.     public boolean place (int k){    
  16.         for (int j = 1 ; j < k ; j++){    
  17.             //這個(gè)主要是刷選符合皇后條件的解，因?yàn)榛屎罂梢怨襞c之同一行同一列的或同一斜線上的棋子    
  18.             if ( (Math.abs(k - j)) == (Math.abs(x[j]-x[k])) || (x[j] == x[k]) ){    
  19.                 return false ;  //如果是與之同一行同一列的或同一斜線上的棋子，返回false;    
  20.             }    
  21.         }    
  22.         return true ;//如果不是與之同一行同一列的或同一斜線上的棋子，返回true;    
  23.     }    
  24.         
  25.     public void backTrace (int t){    
  26.         if (t > n){  //當(dāng)t>n時(shí),算法搜索到葉節(jié)點(diǎn)，得到一個(gè)新的n皇后互不攻擊放置方案，方案數(shù)加1    
  27.             sum ++ ;    //方案數(shù)自增1    
  28.             System.out.println ("方案" + (h++) + "");    
  29.             print(x);    
  30.             System.out.print ("\n----------------\n");//華麗的分割線    
  31.         }else { //當(dāng)t<=n時(shí)，當(dāng)前擴(kuò)展的結(jié)點(diǎn)Z是解空間中的內(nèi)部結(jié)點(diǎn)，該節(jié)點(diǎn)有x[i]=1,2，…,n共n個(gè)子結(jié)點(diǎn)，    
  32.                 //對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子結(jié)點(diǎn)，由place()方法檢測(cè)其可行性，    
  33.                 //并以深度優(yōu)先的方式遞歸地對(duì)可行子樹(shù)搜索，或剪去不可行子數(shù)    
  34.             for (int i = 1 ; i <= n ; i++){    
  35.                 x[t] = i ;      
  36.                 if (place (t)){     //檢查結(jié)點(diǎn)是否符合條件    
  37.                     backTrace (t+1);    //遞歸調(diào)用                  
  38.                 }    
  39.             }    
  40.         }    
  41.     }    
  42.         
  43.     public void print (int[] a){    //打印數(shù)組，沒(méi)啥的    
  44.         for (int i = 1 ; i < a.length ; i++){    
  45.             System.out.print ("皇后" + i + "在" + i + "行" +a[i] + "列、");    
  46.         }    
  47.     }    
  48.         
  49.     public static void main (String[] args){    
  50.         Empress em = new Empress();    
  51.         em.backTrace(1);    //從1開(kāi)始回溯    
  52.         System.out.println ("\n詳細(xì)方案如上所示，"+"可行個(gè)數(shù)為:" + em.sum);    
  53.     }    
  54. }/*output:八皇后問(wèn)題只有92種方案，這里只給出其中的三個(gè)方案  
  55. 方案1  
  56. 皇后1在1行1列、皇后2在2行5列、皇后3在3行8列、皇后4在4行6列、皇后5在5行3列、皇后6在6行7列、皇后7在7行2列、皇后8在8行4列、  
  57. ----------------  
  58. 方案2  
  59. 皇后1在1行1列、皇后2在2行6列、皇后3在3行8列、皇后4在4行3列、皇后5在5行7列、皇后6在6行4列、皇后7在7行2列、皇后8在8行5列、  
  60. ----------------  
  61.         .  
  62.         .  
  63.         .  
  64. 方案92  
  65. 皇后1在1行8列、皇后2在2行4列、皇后3在3行1列、皇后4在4行3列、皇后5在5行6列、皇后6在6行2列、皇后7在7行7列、皇后8在8行5列、  
  66. ----------------  
  67. *///~    



分書(shū)問(wèn)題：
    有編號(hào)為 A、B、C、D、E 的 5 本書(shū)，以及 5 個(gè)人，每本書(shū)可以分給每一個(gè)對(duì)該書(shū)有興趣的人閱讀，且每個(gè)人都只能分到一本自己
感興趣的書(shū)。問(wèn)當(dāng)給定 5 個(gè)人對(duì) 5 本書(shū)的感興趣情況時(shí)，怎樣分配這 5 本書(shū)才能讓每個(gè)人都開(kāi)始閱讀。

思路：每次都嘗試給第 p 個(gè)人從 5 本書(shū)中分出他感興趣的一本，若不能構(gòu)成最終解，則撤銷(xiāo)回溯到上一個(gè)人（即第 p – 1 個(gè)人）的分配。
我們?nèi)缦麓_定：
int bookCounts 表示書(shū)的總數(shù)量，與總?cè)藬?shù)相等
int like [p] [b] = 1 表示第 p 個(gè)人喜歡讀第 b 本書(shū)，即具體的問(wèn)題初始條件；
int given [b] = p 表示第 b 本書(shū)分給了第 p 個(gè)人，即保存解的標(biāo)識(shí)數(shù)組；
注：在這里 p ，b （即下標(biāo)）都從 0 開(kāi)始，算法實(shí)現(xiàn)如下：

/**
  * 回溯法求解分書(shū)問(wèn)題 
  * @author haolloyin
  */

 public class AllacateBooks {
     // 書(shū)的總數(shù)量，與總?cè)藬?shù)相等
     private int bookCounts = 5;

     // like[p][b]=1 表示第 p 個(gè)人喜歡讀第 b 本書(shū)
      private int[][] like = new int[bookCounts][bookCounts];

    // given[b] = p 表示將第 b 本書(shū)分配給第 p 個(gè)人
      private int[] given = new int[bookCounts];

    // 初始化標(biāo)識(shí)數(shù)組 given[] 和傳入各人喜歡書(shū)的情況數(shù)組
      private void init(int like[][]) {
        for (int i = 0; i < bookCounts; i++) {
           given[i] = -1; // -1 表示第 i 本書(shū)還沒(méi)分配出去
        }
          this.like = like;
      }

    // 嘗試給每一個(gè)人分配一本書(shū)
      public void allocateBook(int person) {
        for (int bookNum = 0; bookNum < bookCounts; bookNum++) {
          if (like[person][bookNum] == 1 && given[bookNum] == -1) {
             given[bookNum] = person;
             if (person == bookCounts - 1) {
                // 打印結(jié)果
                for (int i = 0; i < bookCounts; i++) {
                 System.out.println("人 " + (given[i]+1) + " <---> 書(shū) " + ((char)(i + 'A')));
                }
                System.out.println();
             } else {
               // 為下一個(gè)人分配一本書(shū)
               allocateBook(person + 1);
             }
            // 失敗，回溯重新尋找解
             given[bookNum] = -1;
         }
       }
      }

 // 測(cè)試
   public static void main(String[] args) {
    // 構(gòu)造一個(gè)問(wèn)題規(guī)模
      int[][] like = new int[][]{
           { 0, 0, 1, 1, 0 },
           { 1, 1, 0, 0, 1 },
           { 0, 1, 1, 0, 1 },
           { 0, 0, 0, 1, 0 },
           { 0, 1, 0, 0, 1 }};
    AllacateBooks allocateBooks = new AllacateBooks();
    allocateBooks.init(like);
    allocateBooks.allocateBook(0);
   }
 } 
 對(duì)應(yīng)于所給的問(wèn)題規(guī)模，所得的解如下：

人 2 <---> 書(shū) A
人 3 <---> 書(shū) B
人 1 <---> 書(shū) C
人 4 <---> 書(shū) D
人 5 <---> 書(shū) E

人 2 <---> 書(shū) A
人 5 <---> 書(shū) B
人 1 <---> 書(shū) C
人 4 <---> 書(shū) D
人 3 <---> 書(shū) E

[實(shí)驗(yàn)?zāi)康腯

綜合運(yùn)用數(shù)組、遞歸等數(shù)據(jù)結(jié)構(gòu)知識(shí)，掌握、提高分析、設(shè)計(jì)、實(shí)現(xiàn)及測(cè)試程序的綜合能力。

[實(shí)驗(yàn)內(nèi)容及要求]

以一個(gè)M×N的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。

（1）   根據(jù)二維數(shù)組，輸出迷宮的圖形。

（2）   探索迷宮的四個(gè)方向：RIGHT為向右，DOWN向下，LEFT向左，UP向上，輸出從入口到出口的行走路徑。

[測(cè)試數(shù)據(jù)]

左上角（1，1）為入口，右下角（8，9）為出口。

0

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

1

1

0

1

0

1

1

1

0

0

1

0

0

0

0

1

0

0

0

0

0

1

0

0

0

1

0

1

0

1

1

1

1

0

0

1

1

1

0

0

0

1

0

1

1

1

0

0

0

0

0

0

[實(shí)現(xiàn)提示]

可使用回溯方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路。

  1. import java.util.*;  
  2.    
  3. class Position{  
  4.     public Position(){  
  5.    
  6.     }  
  7.    
  8.     public Position(int row, int col){  
  9.         this.col = col;  
  10.         this.row = row;  
  11.     }  
  12.    
  13.     public String toString(){  
  14.         return "(" + row + " ," + col + ")";  
  15.     }  
  16.    
  17.     int row;  
  18.     int col;  
  19. }  
  20.    
  21. class Maze{  
  22.     public Maze(){  
  23.         maze = new int[15][15];  
  24.         stack = new Stack<Position>();  
  25.         p = new boolean[15][15];  
  26.     }  
  27.    
  28.     /* 
  29.      * 構(gòu)造迷宮 
  30.      */  
  31.     public void init(){  
  32.         Scanner scanner = new Scanner(System.in);  
  33.         System.out.println("請(qǐng)輸入迷宮的行數(shù)");  
  34.         row = scanner.nextInt();  
  35.         System.out.println("請(qǐng)輸入迷宮的列數(shù)");  
  36.         col = scanner.nextInt();  
  37.         System.out.println("請(qǐng)輸入" + row + "行" + col + "列的迷宮");  
  38.         int temp = 0;  
  39.         for(int i = 0; i < row; ++i) {  
  40.             for(int j = 0; j < col; ++j) {  
  41.                 temp = scanner.nextInt();  
  42.                 maze[i][j] = temp;  
  43.                 p[i][j] = false;  
  44.             }  
  45.         }  
  46.     }  
  47.    
  48.     /* 
  49.      * 回溯迷宮，查看是否有出路 
  50.      */  
  51.     public void findPath(){  
  52.         // 給原始迷宮的周?chē)乙蝗鷫?nbsp; 
  53.         int temp[][] = new int[row + 2][col + 2];  
  54.         for(int i = 0; i < row + 2; ++i) {  
  55.             for(int j = 0; j < col + 2; ++j) {  
  56.                 temp[0][j] = 1;  
  57.                 temp[row + 1][j] = 1;  
  58.                 temp[i][0] = temp[i][col + 1] = 1;  
  59.             }  
  60.         }  
  61.         // 將原始迷宮復(fù)制到新的迷宮中  
  62.         for(int i = 0; i < row; ++i) {  
  63.             for(int j = 0; j < col; ++j) {  
  64.                 temp[i + 1][j + 1] = maze[i][j];  
  65.             }  
  66.         }  
  67.         // 從左上角開(kāi)始按照順時(shí)針開(kāi)始查詢  
  68.    
  69.         int i = 1;  
  70.         int j = 1;  
  71.         p[i][j] = true;  
  72.         stack.push(new Position(i, j));  
  73.         while (!stack.empty() && (!(i == (row) && (j == col)))) {  
  74.    
  75.             if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) {  
  76.                 p[i][j + 1] = true;  
  77.                 stack.push(new Position(i, j + 1));  
  78.                 j++;  
  79.             } else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) {  
  80.                 p[i + 1][j] = true;  
  81.                 stack.push(new Position(i + 1, j));  
  82.                 i++;  
  83.             } else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) {  
  84.                 p[i][j - 1] = true;  
  85.                 stack.push(new Position(i, j - 1));  
  86.                 j--;  
  87.             } else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) {  
  88.                 p[i - 1][j] = true;  
  89.                 stack.push(new Position(i - 1, j));  
  90.                 i--;  
  91.             } else {  
  92.                 stack.pop();  
  93.                 if(stack.empty()){  
  94.                     break;  
  95.                 }  
  96.                 i = stack.peek().row;  
  97.                 j = stack.peek().col;  
  98.             }  
  99.    
  100.         }  
  101.    
  102.         Stack<Position> newPos = new Stack<Position>();  
  103.         if (stack.empty()) {  
  104.             System.out.println("沒(méi)有路徑");  
  105.         } else {  
  106.             System.out.println("有路徑");  
  107.             System.out.println("路徑如下：");  
  108.             while (!stack.empty()) {  
  109.                 Position pos = new Position();  
  110.                 pos = stack.pop();  
  111.                 newPos.push(pos);  
  112.             }  
  113.         }  
  114.            
  115.         /* 
  116.          * 圖形化輸出路徑 
  117.          * */  
  118.            
  119.         String resault[][]=new String[row+1][col+1];  
  120.         for(int k=0;k<row;++k){  
  121.             for(int t=0;t<col;++t){  
  122.                 resault[k][t]=(maze[k][t])+"";  
  123.             }  
  124.         }  
  125.         while (!newPos.empty()) {  
  126.             Position p1=newPos.pop();  
  127.             resault[p1.row-1][p1.col-1]="#";  
  128.            
  129.         }  
  130.            
  131.         for(int k=0;k<row;++k){  
  132.             for(int t=0;t<col;++t){  
  133.                 System.out.print(resault[k][t]+"\t");  
  134.             }  
  135.             System.out.println();  
  136.         }  
  137.        
  138.    
  139.     }  
  140.    
  141.     int maze[][];  
  142.     private int row = 9;  
  143.     private int col = 8;  
  144.     Stack<Position> stack;  
  145.     boolean p[][] = null;  
  146. }  
  147.    
  148. class hello{  
  149.     public static void main(String[] args){  
  150.         Maze demo = new Maze();  
  151.         demo.init();  
  152.         demo.findPath();  
  153.     }  
  154. }  

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類(lèi)似文章 更多