加入收藏 | 设为首页 | 会员中心 | 我要投稿 PHP编程网 - 黄冈站长网 (http://www.0713zz.com/)- 数据应用、建站、人体识别、智能机器人、语音技术!
当前位置: 首页 > 综合聚焦 > 编程要点 > 语言 > 正文

回看算法详解

发布时间:2022-07-09 07:30:55 所属栏目:语言 来源:互联网
导读:回溯算法,又称为试探法。解决问题时,每进行一步,都是抱着试试看的态度,如果发现当前选择并不是最好的,或者这么走下去肯定达不到目标,立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯算法。 例如,在解决列举集合 {1,2,3} 中所有子集的
  回溯算法,又称为“试探法”。解决问题时,每进行一步,都是抱着试试看的态度,如果发现当前选择并不是最好的,或者这么走下去肯定达不到目标,立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯算法。
 
  例如,在解决列举集合 {1,2,3} 中所有子集的问题中,就可以使用回溯算法。从集合的开头元素开始,对每个元素都有两种选择:取还是舍。当确定了一个元素的取舍之后,再进行下一个元素,直到集合最后一个元素。其中的每个操作都可以看作是一次尝试,每次尝试都可以得出一个结果。将得到的结果综合起来,就是集合的所有子集。
 
  实现代码为:
  #include <stdio.h>
  //设置一个数组,数组的下标表示集合中的元素,所以数组只用下标为1,2,3的空间
  int set[5];
  //i代表数组下标,n表示集合中最大的元素值
  void PowerSet(int i,int n){
      //当i>n时,说明集合中所有的元素都做了选择,开始判断
      if (i>n) {
          for (int j=1; j<=n; j++) {
              //如果树组中存放的是 1,说明在当初尝试时,选择取该元素,即对应的数组下标,所以,可以输出
              if (set[j]==1) {
                  printf("%d ",j);
              }
          }
          printf("n");
      }else{
          //如果选择要该元素,对应的数组单元中赋值为1;反之,赋值为0。然后继续向下探索
          set[i]=1;PowerSet(i+1, n);
          set[i]=0;PowerSet(i+1, n);
      }
  }
  int main() {
      int n=3;
      for (int i=0; i<5; i++) {
          set[i]=0;
      }
      PowerSet(1, n);
      return 0;
  }
  运行结果:
  1 2 3
  1 2
  1 3
  1
  2 3
  2
  3
 
  回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点,都有可能是问题的答案。图 1 中的状态树是满二叉树,得到的叶子结点全部都是问题的解。
 
  在某些情况下,回溯算法解决问题的过程中创建的状态树并不都是满二叉树,因为在试探的过程中,有时会发现此种情况下,再往下进行没有意义,所以会放弃这条死路,回溯到上一步。在树中的体现,就是在树的最后一层不是满的,即不是满二叉树,需要自己判断哪些叶子结点代表的是正确的结果。

(编辑:PHP编程网 - 黄冈站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读