用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。

题目

用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。

相似考题

1.回溯法解旅行售货员问题时的解空间树是子集树。()此题为判断题(对，错)。

2.以下的算法设计方法中，( )以获取问题最优解为目标。A．回溯方法B．分治法C．动态规划D．递推

3.若原问题无可行解，对偶问题有可行解，根据敏感性分析准则应该()。A、现有解仍为最优解B、用单纯形法求新的最优解C、用对偶单纯形法求新的最优解D、引入人工变量用单纯形法求新的最优解

4.用表上作业法求解运输问题时,当某个非基变量检验数为0,则该问题有( )。A.多重解B. 无解C. 退化解D. 无穷多最优解

更多“用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。”相关问题

  • 第1题：

    用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的()

    A、原解

    B、上界

    C、下界

    D、最优解


    参考答案：C

  • 第2题：

    在求解某问题时，经过分析发现该问题具有最优子结构性质，若定义问题的解空间，以深度优先的方式搜索解空间，则采用（ ）算法设计策略。

    A.动态规划
    B.贪心
    C.回溯
    D.分支限界

    答案：C
    解析：
    分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。
    动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
    贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。
    回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
    题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

  • 第3题：

    回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。


    正确答案:子集树；排列树

  • 第4题：

    比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？


    正确答案: 1）回溯法是在约束下带跳跃的深度优先搜索。
    2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。
    3）分枝限界法更适合找最优解。

  • 第5题：

    在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）

    • A、回溯法
    • B、分支限界法
    • C、回溯法和分支限界法
    • D、回溯法求解子集树问题

    正确答案:B

  • 第6题：

    在求解规模较大的问题时，可以把它分解成若干个规模较小的子问题，求出各个子问题的解之后，再把这些解合成原问题的解，这种方法是（）。

    • A、穷举法
    • B、回溯法
    • C、分治法
    • D、递归法

    正确答案:C

  • 第7题：

    用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。


    正确答案:一个（最优）解

  • 第8题：

    单选题
    关于回溯搜索法的介绍，下面（）是不正确描述。
    A

    回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解

    B

    回溯法是一种既带系统性又带有跳跃性的搜索算法

    C

    回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯

    D

    回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径


    正确答案： C
    解析： 暂无解析

  • 第9题：

    单选题
    回溯法解旅行售货员问题时的解空间树是（）。
    A

    子集树

    B

    排列树

    C

    深度优先生成树

    D

    广度优先生成树


    正确答案： B
    解析： 暂无解析

  • 第10题：

    填空题
    用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。

    正确答案： 一个（最优）解
    解析： 暂无解析

  • 第11题：

    单选题
    用表上作业法求解运输问题时，当某个非基变量检验数为0，则该问题有（）。
    A

    多重解

    B

    无解

    C

    退化解

    D

    无穷多最优解


    正确答案： B
    解析： 暂无解析

  • 第12题：

    单选题
    在求解规模较大的问题时，可以把它分解成若干个规模较小的子问题，求出各个子问题的解之后，再把这些解合成原问题的解，这种方法是（）。
    A

    穷举法

    B

    回溯法

    C

    分治法

    D

    递归法


    正确答案： A
    解析： 暂无解析

  • 第13题：

    回溯法也称为试探法。以下关于回溯法的结论中正确的是(50)。

    A．即使问题的解存在，回溯法不一定能找到问题的解

    B．回溯法找到的问题的解不一定是最优解

    C．回溯法不能找到问题的全部解

    D．回溯法无法避免求出的问题解的重复


    正确答案：B
    解析：回溯法又称为试探法，是找到问题解的一种搜索策略，就是在用某种方法找出的解的过程中，若中间项结果满足所解问题的条件，则一直沿这个方向搜索下去，直到无路可走或无结果，则开始回溯，改变其前一项的方向(或值)继续搜索。若其上一项的方向(或值)都已经测试过，还无路可走或无结果，则再继续回溯到更前一项，改变其方向(或值)继续搜索。若找到了一个符合条件的解，则停止或输出这个结果继续搜索，这个解不一定是最优解；否则继续回溯下去，直到回溯到问题的开始处(不能再回溯)，仍没有找到符合条件的解，则表示此问题无解或已经找到了全部的解。

  • 第14题：

    用单纯形法求解目标函数为极大值的线性规划问题，当所有非基变量的检验数均小于零时，表明该问题（）

    • A、有无穷多最优解
    • B、无可行解
    • C、有且仅有一个最优解
    • D、有无界解

    正确答案:C

  • 第15题：

    用表上作业法求解运输问题时，当某个非基变量检验数为0，则该问题有（）。

    • A、多重解
    • B、无解
    • C、退化解
    • D、无穷多最优解

    正确答案:D

  • 第16题：

    回溯法解旅行售货员问题时的解空间树是（）。

    • A、子集树
    • B、排列树
    • C、深度优先生成树
    • D、广度优先生成树

    正确答案:B

  • 第17题：

    关于回溯搜索法的介绍，下面（）是不正确描述。

    • A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
    • B、回溯法是一种既带系统性又带有跳跃性的搜索算法
    • C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
    • D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

    正确答案:D

  • 第18题：

    用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。


    正确答案:子集树

  • 第19题：

    填空题
    用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。

    正确答案： 子集树
    解析： 暂无解析

  • 第20题：

    填空题
    回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。

    正确答案： 子集树,排列树
    解析： 暂无解析

  • 第21题：

    单选题
    在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）
    A

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    回溯法求解子集树问题


    正确答案： C
    解析： 暂无解析

  • 第22题：

    填空题
    用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。

    正确答案： 排列树
    解析： 暂无解析

  • 第23题：

    问答题
    比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？

    正确答案： 1）回溯法是在约束下带跳跃的深度优先搜索。
    2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。
    3）分枝限界法更适合找最优解。
    解析： 暂无解析

相关内容