首页 > Web开发 > JavaScript教程 > 正文

Java实现搜索回溯经典题目

互联网 2019-08-12 11:32:57 0

 前言

搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。


如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步步向前试探前进,如果碰到死胡同,说明前进方向已无路可走,这时,首先看其它方向是否还有路可走,如果有路可走,则沿该方向再向前试探;如果已无路可走,则返回一步,再看其它方向是否还有路可走;如果有路可走,则沿该方向再向前试探。按此原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口处无解为止。


搜索框架

搜索伪代码/公式

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


void Search(int k)

{

 for (i=1;i<=算符种数;i++)

  if (满足条件)

     {

    保存结果

    if (到目的地) 输出解;

     else Search(k+1);

    恢复:保存结果之前的状态{回溯一步}

     }

}



经典问题

【问题1】八皇后问题


题目

八皇后问题:要在国际象棋棋盘中放八个皇后,使任意两个皇后都不能互相吃。(提示:皇后能吃同一行、同一列、同一对角线的任意棋子。)


分析

放置第i个(行)皇后的算法为:

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);

    }

}




  • 相关标签:Java
  • 版权归原作者所有,如果有侵犯到您的权益,请联系本站删除!
  • 相关文章


    专题推荐

    今日头条
  • 手机哪款好?8月值得买的手机就这四款 手机哪款好?8月值得买的手机就这四款
  • 七夕保命技能书送上 女朋友还有30秒到达战场 七夕保命技能书送上 女朋友还有30秒到达战场
  • 七夕保命技能书送上 女朋友还有30秒到达战场 七夕保命技能书送上 女朋友还有30秒到达战场
  • 七夕搞笑句子大全2019 七夕微信说说笑死人那种 七夕搞笑句子大全2019 七夕微信说说笑死人那种
  • 热门标签