信管网试题内容

试题内容

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用C_ij。为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2，…，每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。该算法采用了（1）算法设计策略，其时间复杂度为（2）。
（1） A．分治
B．动态规划
C．贪心
D．回溯
（2）A.Θ（n²）
B.Θ（n）
C.Θ（nlgn）
D.Θ（1）