算法第五章作业

一、对回溯算法的理解

       我认为回溯算法其实是一种近似于“试探”的过程,它根据一个树形的结构,进行一层层的试探,最终得到想要的结果。在每一次的递归中,当出现符合条件的答案时,便保存当前的状态,进入下一层的计算;否则,返回上一层,进行下一步的计算。所以在回溯算法中必须给出限界函数,否则递归便不会终止。

二、“子集和”问题的解空间结构和约束函数:

  ”子集和“问题类似于0-1背包问题,"子集和“问题的解空间由长度为n的0-1向量组成,该解空间包含对所有变量的所有可能的0-1赋值。比如当n=5时,其解空间为{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}。其解空间树是一颗完全二叉树。

  其约束函数为 if (sum + a[t] < c)/ else ,如果加上当前结点的值小于问题所要求的子集和目标值,则向左子树走,否则走向右子树。

三、本章学习过程中遇到的问题和结对编程情况汇报:

  本章学习对我来说难点在于比较难以想到约束函数和限界函数,通常在编程过程中会发现自己做的不是回溯法,然后就要在停顿一会儿,去思考,比较费时间。结对编程上的话,最近一段时间也比较忙于各种小测和期末的大作业、复习等等,虽然有交流,但是交流的次数比之前少了,自己在回溯法上也要多下功夫。

原文地址:https://www.cnblogs.com/fengwanthousand/p/12056712.html