问答题简述分支限界法及其算法思想。

题目

问答题

简述分支限界法及其算法思想。

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

常见的两种分支限界法为队列式(FIFO)分支限界法与堆栈式分支限界法。()

此题为判断题(对，错)。

正确答案:×

第2题：

分支限界法是一种只带有系统性搜索算法。()

此题为判断题(对，错)。

正确答案:√

第3题：

分支限界法主要有队列式(FIFO)分支限界法和优先队列式分支限界法。()

此题为判断题(对，错)。

正确答案:√

第4题：

用分支限界法设计算法的步骤是什么？

正确答案: （1）针对所给问题，定义问题的解空间（对解进行编码）；
（2）确定易于搜索的解空间结构（按树或图组织解）；
（3）以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

第5题：

从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（）之外都是最常见的方式。

A、队列式分支限界法
B、优先队列式分支限界法
C、栈式分支限界法
D、FIFO分支限界法

正确答案:C

第6题：

常见的分支限界法的算法框架有3种。()

此题为判断题(对，错)。

正确答案:×

第7题：

简述ID3算法的基本思想及其主算法和建树算法的基本步骤。

正确答案: 首先找出最有判别力的因素，然后把数据分成多个子集，每个子集又选择最有判别力的因素进一步划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树，可以用它来对新的样例进行分类。
主算法包括如下几步：
①从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；
②用“建树算法”对当前窗口形成一棵决策树；
③对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；
④若存在错判的例子，把它们插入窗口，重复步骤②，否则结束。
建树算法的具体步骤如下：
①对当前例子集合，计算各特征的互信息；
②选择互信息最大的特征A_k；
③把在A_k处取值相同的例子归于同一子集，A_k取几个值就得几个子集；
④对既含正例又含反例的子集，递归调用建树算法；
⑤若子集仅含正例或反例，对应分枝标上P或N，返回调用处。

第8题：

以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。()

此题为判断题(对，错)。

正确答案:√

第9题：

试比较回溯法与分支限界算法，分别谈谈这两个算法比较适合的问题？

正确答案: 不同点：求解目标，搜索方式，空间消耗。
回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
搜索方式：回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。
回溯法：以深度优先方式系统搜索问题解的算法为回溯法，适合解组合数较大的问题。
分支限界法适合解决大量离散最优化的问题。

第10题：

简述分支限界法与回溯法的异同。

正确答案: 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：
（1）求解目标不同；
（2）搜索方式不同；
（3）对扩展结点的扩展方式不同；
（4）存储空间的要求不同。

简述分支限界法及其算法思想。

题目

相似问题和答案

更多相关问题

相关内容