Java实现搜索回溯经典题目

我会带着你远行 2021-09-29 22:44 308阅读 0赞

### 前言 ###

*  搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
 *  如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

--------------------

### 搜索框架 ###

搜索伪代码/公式  
基本上所有的搜索与回溯都是这个公式的变种

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

**【代码实现】**

/** * @author 谢世杰 */
    public class SplitData { 
        int[] a;
        int goal;
    
        /** * 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和 * 算符种类：要分割的自然数n * 结果数组：a[n],存储这分割的结果 * */
        void search(int n, int t) { 
            // 算符种类，从1开始，一直到n
            for (int i=a[t-1]; i<=n; i++) { 
                // 满足条件,把分解的数字存入数组并在n基础上减去
                // 当前数i要大于等于前1位数，且不过n
                if(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);
        }
    }