下面可以用分支限界法解决的问题有（多选)：（） A. 旅行商问题 B. 八数码问题 C. 汉密尔顿回路 D.单源最短路径

题目

下面可以用分支限界法解决的问题有（多选)：（） A. 旅行商问题 B. 八数码问题 C. 汉密尔顿回路 D.单源最短路径

相似考题

1.单源最短路径问题能使用贪心法解决。()此题为判断题(对，错)。

2.解决0／1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划,需要排序的是回溯法,分支限界法。()此题为判断题(对，错)。

3.OSPF解决路由环问题的方法有()。A.矢量算法B.路由保持法C.最短路径树算法D.定义路由权的最大值

4.分支限界法能解决0／1背包问题的是。()此题为判断题(对，错)。

更多“下面可以用分支限界法解决的问题有（多选)：（） A. 旅行商问题 B. 八数码问题 C. 汉密尔顿回路 D.单源最短路径”相关问题

  • 第1题：

    判断有向图是否存在回路，利用()方法最佳。

    A.求关键路径

    B.求最短路径

    C.拓扑排序

    D.广度优先遍历


    正确答案：C

  • 第2题：

    不能保证求得0-1背包问题的最优解。

    A．分支限界法

    B．贪心算法

    C．回溯法

    D．动态规划策略


    正确答案：B
    解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。

  • 第3题：

    下面哪些使用的不是贪心算法()

    A.单源最短路径中的Dijkstra算法

    B.最小生成树的Prim算法

    C.最小生成树的Kruskal算法

    D.计算每对顶点最短路径的Floyd-Warshall算法


    正确答案：D

  • 第4题：

    关键路径是事件结点网络中()。

    A.从源点到汇点的最长路径

    B.从源点到汇点的最短路径

    C.最长回路

    D.最短回路


    正确答案：A

  • 第5题：

    关键路径是指AOE(Activity On Edge)网中______。

    A．最长的回路

    B．最短的回路

    C．从源点到汇点(结束顶点)的最长路径

    D．从源点到汇点(结束顶点)的最短路径


    正确答案：C

  • 第6题：

    社会服务方案的策划需要首先进行问题认识和分析，问题主要是要认识需要解决的社会问题，认识问题的方法有（ ）

    A.问题关注工作表
    B.问题认识工作表
    C.归纳法
    D.分支法
    E.演绎法

    答案：B,D
    解析：
    认识问题的方法有两种，一是“问题认识工作表”，二是“分支法”。 本题考查的是认识问题的方法。了解这两个方法的含义与内容。

  • 第7题：

    当各边上的权值满足()的条件时，BFS算法可用来解决单源最短路径问题。

    A.均相等
    B.均互不相等
    C.不一定相等
    D.其他

    答案：A
    解析：
    单源最短路径问题是指：从已知图G=(V，E)中找出某给定的源结点S∈V到V中的每个结点的最短路径。当各边上的权值均相等时，BFS算法可用来解决单源最短路径问题。

  • 第8题：

    解决单起点多回路最短路线问题常用的方法是（）。

    • A、回路法
    • B、图上作业法
    • C、表上作业法
    • D、节约里程法

    正确答案:D

  • 第9题：

    针对指派问题和旅行商问题，可用（）来解决

    • A、图解法
    • B、表上作业法
    • C、匈牙利算法
    • D、效率比法

    正确答案:C

  • 第10题：

    针对指派问题和旅行商问题，可用（）解决。

    • A、图解法
    • B、表上作业法
    • C、匈牙利算法
    • D、效率比法

    正确答案:C

  • 第11题：

    单选题
    下面问题（）不能使用贪心法解决。
    A

    单源最短路径问题

    B

    N皇后问题

    C

    最小花费生成树问题

    D

    背包问题


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

  • 第12题：

    单选题
    针对指派问题和旅行商问题，可用（）来解决
    A

    图解法

    B

    表上作业法

    C

    匈牙利算法

    D

    效率比法


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

  • 第13题：

    ● 迪杰斯特拉（Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了 （63） 算法策略

    （63）

    A. 贪心

    B. 分而治之

    C. 动态规划

    D. 试探＋回溯


    正确答案：A

  • 第14题：

    关键路径是事件结点网络中的(39)。

    A．从源点到汇点的最长路径

    B．从源点到汇点的最短路径

    C．最长的回路

    D．最短的回路


    正确答案：A
    解析：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径成为关键路径。在AOE网中，可以有不止一条的关键路径。

  • 第15题：

    在AOE图中，关键路径是(39)。

    A．从源点到汇点的最长路径

    B．从源点到汇点的最短路径

    C．最长的回路

    D．最短的回路


    正确答案：A
    解析：在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网，简称AOE图。用AOE图表示一项工程计划时，对于一项工程来说，一般有一个开始状态和一个结束状态，所以在AOE网中至少有一个入度为0的开始顶点，称其为源点；另外，应有一个出度为。的结束顶点，称其为汇点。AOE中不应存在有向回路，否则整个工程无法完成。从源点到汇点的路径中，长度最长的路径称为关键路径，所以应选A。

  • 第16题：

    关键路径是指AOE(Activity On Edge)网中(38)。

    A．最长的回路

    B．最短的回路

    C．从源点到汇点(结束顶点)的最长路径

    D．从源点到汇点(结束顶点)的最短路径


    正确答案：C
    解析：在AOE网中，用顶点表示活动，用有向边vi，vi＞表示活动vi必须先于活动vi进行。如果在有向环的带权有向图中用有向边表示一个工程中的各项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这种有向图叫做用边表示活动的网络，简称AOE网络。关键路径是指在AOE网络中从源点到汇点的最长路径。拓扑排序、最短路径和计算关键路径都是有向图的重要运算。根据关键路径的定义，正确答案为C。

  • 第17题：

    ● （65） 不能保证求得0-1 背包问题的最优解。

    （65）

    A. 分支限界法

    B. 贪心算法

    C. 回溯法

    D. 动态规划策略


    正确答案：B

  • 第18题：

    判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用()。

    A.广度优先遍历算法
    B.深度优先遍历算法
    C.求关键路径的方法
    D.求最短路径的方法

    答案：B
    解析：
    当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。

  • 第19题：

    关键路径是AOE网中()。

    A.最长的回路
    B.最短的回路
    C.从源点到终点的最长路径
    D.从源点到终点的最短路径

    答案：C
    解析：
    关键路径是指从开始顶点到结束顶点的最短路径，路径的长度也是工程完成的最少时间。关键活动是指关键路径上的所有活动，关键活动的最大特征是该活动的最早开始时间等于该活动所允许的最迟开始时间。

  • 第20题：

    BP网解决了旅行商问题。


    正确答案:错误

  • 第21题：

    下面问题（）不能使用贪心法解决。

    • A、单源最短路径问题
    • B、N皇后问题
    • C、最小花费生成树问题
    • D、背包问题

    正确答案:B

  • 第22题：

    单选题
    针对指派问题和旅行商问题，可用（）解决。
    A

    图解法

    B

    表上作业法

    C

    匈牙利算法

    D

    效率比法


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

  • 第23题：

    单选题
    当各边上的权值（  ）时，BFS算法可用来解决单源最短路径问题。
    A

    均相等

    B

    均互不相等

    C

    不一定相等

    D

    无法判断


    正确答案： B
    解析：

  • 第24题：

    单选题
    解决单起点多回路最短路线问题常用的方法是（）。
    A

    回路法

    B

    图上作业法

    C

    表上作业法

    D

    节约里程法


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

相关内容