首页 > 试题广场 >

下面算法的功能是

[单选题]

下面算法的功能是:()

Method(C) {
    S = {};
    while (not solution(S)) {
        x = select(C);
        if feasible (S, x)
            S = S + {x};
        C = C - {x};
    }
    return S;
}

分支限界法求解问题的一般过程

动态规划求解最优解的一般过程

贪心算法求解最优解的一般过程

```
回溯算法求解的一般过程
```

查看答案及解析

IreanLau

分支限界法是对回溯法做出优化。 feasible(S,x)是剪枝函数。

S=S+{x}; C=C-{x};是回溯（分支）过程。

发表于 2015-09-19 14:17:27 回复(6)

seaway

本题的正确答案是“贪心算法求解最优解的一般过程 ”

分析如下所示：（复制粘贴来自： http://blog.csdn.net/winbobob/article/details/38314821 ）

1.贪心法的设计思想

贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。

该算法存在问题：

1). 不能保证求得的最后解是最佳的；

2). 不能用来求最大或最小解问题；

3). 只能求满足某些约束条件的可行解的范围。

Dijkstra算法、Prim算法和Kruskal算法都属于典型的贪心算法

引例 [找零钱]

一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目

引例分析

为使找回的零钱的硬币数最小，不考虑找零钱的所有各种方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，只当不足大面值币种的金额才会去考虑下一种较小面值的币种。这就是在采用贪婪法。这种方法在这里之所以总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。

贪心法的求解过程

用贪心法求解问题应该考虑如下几个方面：

（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。

（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。

（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。

（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。

（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

贪心法的一般流程

[cpp] view plain copy

Greedy(C) //C是问题的输入集合即候选集合

{

S={ }; //初始解集合为空集

while (not solution(S)) //集合S没有构成问题的一个解

{

x=select(C); //在候选集合C中做贪心选择

if feasible(S, x) //判断集合S中加入x后的解是否可行

S=S+{x};

C=C-{x};

}

return S;

2.贪心法的基本要素

对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。

但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。

子问题：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，对于任何一个整数k，1 < k < n，以Dk作为问题的初始状态，来进行以后的决策，这样的问题就成为是原问题的一个子问题。

1) 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。

贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2) 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

3.贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。大多数时候，能用贪心算法求解的问题，都可以用动态规划算法求解。但是能用动态规划求解的，不一定能用贪心算法进行求解。（因为贪心选择性质比动态规划的两个属性约束更强）

编辑于 2016-02-28 17:09:14 回复(4)

helloworld__

Greedy(C) //C是问题的输入集合即候选集合

{

S={ }; //初始解集合为空集

while (not solution(S)) //集合S没有构成问题的一个解

{

x=select(C); //在候选集合C中做贪心选择

if feasible(S, x) //判断集合S中加入x后的解是否可行

S=S+{x};

C=C-{x};

}

return S;

}

这是从网上找来的有注释的伪代码，看看就好。烂题一道，不用纠结了。

发表于 2016-11-09 13:55:40 回复(0)

露西恩缇努维尔

题目中给的是两个集合，每回从第一个集合中选元素，如果这个元素和第二个集合满足一定的条件，则加入第二个集合并将其从第一个集合中删去。

求最小生成树的Prim算法和Kruskal算法都是题目中这个套路，贪心无疑。

分支限界法利用队列queue，基于BFS的思想，不对。

动态规划要查表，有明显的状态递推，不对。

回溯算法要么用深搜，需要递归。要么用栈stack，也不符合。

编辑于 2020-05-27 18:10:56 回复(0)

yayamma

分治法 要求各个子问题是独立的(即不包含公共的子问题 )，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子问题。
动态规划 与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题) ，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效的一个原因。

发表于 2015-09-19 14:54:52 回复(0)