一个NPC问题，首先是NP问题，另外所有的其他NP问题都能在多项式时间复杂性规约为该问题

有这样一种算法，运行一次一定能找到问题的解，有时不知其是否正确，可以确定的是该解高概率（大于50%）是正确的。这种算法是？

素数测试问题的蒙特卡洛算法，n是一个待判定正整数。当 n是素数时， 有时会被判定为非素数。该说法正确吗?

‍

（1）求解目标不同，分支限界法可求最优解或满足条件的一个解，而回溯法可求最优解或满足条件的所有解

‌

（2）搜索方式不同， 回溯法是以深度优先状态生成树法搜索解空间树，分支限界法则以广度优先或最小耗费（最大效益）优先的状态生成树法搜索解空间树。

‌

（3） 同一个问题在使用回溯法或分支限界法时，该问题的解空间树的结构不同

‌

（4）  回溯法与分支限界法，构造最优解的方式不同。

‌

从上述选项中找出答案。

在队列式分支限界法中， 叶子结点不加入队列。而在优先队列式分支限界法中，叶子结点通常要加入到优先队列中。有下列2个解释：

‍

（1）      队列式分支限界法，活结点在队列中的顺序是按照搜索解空间树时扩展出该结点的先后顺序存放，每次从队首取出一个活结点成为新的扩展结点。扩展结点扩展出的儿子结点是叶子结点时，会将该叶子结点的值同当前最优值比较，检查更新最优值，叶子结点并不进入队列，等队列为空时，搜索结束，记录的当前最优值就是问题最优值。

‍

（2）      优先队列式分支限界法中， 当优先级的定义是限界函数时，扩展出的叶子结点进入队列， 这种做法主要是为了让搜索过程提前结束。也就是当从优先队列中取出一个活结点是叶子结点时，意味着现在优先队列中剩余的所有活结点其优先级都不大于该叶子结点的优先级，叶子结点的优先级等于最优值，算法结束，无论优先队列是否为空。

‍

根据其正确与否，给出答案

阅读该单元测试中关于0-1背包问题的优先队列分支限界算法代码，

‏

‎问左分支的剪枝条件是什么？右分支的剪枝条件是什么？从代码中找到命令行，使用原代码回答问题。

回溯法与分支限界法的空间复杂度是相同的，都是O(h(n)),  h(n)是解空间树的深度。