求助大佬：这道题除了穷举和遍历还有其他算法吗。

ikkkki

在理想情况下（无障碍物，不考虑碰撞），4辆小车（a, b, c, d）同时出发，要分别到达4个指定的位置的车库（A, B, C, D）（一个车库只能停一辆车），假设全部小车进库的时间是T（即最后一辆小车入库的时间），编程求出T的最小值。小车入库的时间如下表所示。
表1 小车入库时间表（单位：分钟）
        A        B        C        D
a        4        8        7        15
b        7        9        17        14
c        6        9        12        8
d        6        7        14        6
答案：T=8

isdkz

这是一个典型的旅行商问题（TSP），可以使用启发式算法来解决。其中最常用的是遗传算法（Genetic Algorithm）和模拟退火算法（Simulated Annealing）。这些算法可以帮助找到较优解，避免了穷举和遍历的低效率。在这个问题中，可以将每辆车看作一个旅行商，每个车库看作一个城市，然后使用启发式算法来找到最短路径，即最小的T值。

Mike_python小

小车最短时间问题

这个问题可以通过贪心算法来解决。我们可以对每个车库的时间进行排序，然后让每辆车按顺序选择最早可用的车库。

下面是C++代码的一个例子：

2. #include <iostream>
3. #include <vector>
4. #include <algorithm>
6. int main()
7. {
8.     std::vector<std::vector<int>> times = {
9.         {4, 8, 7, 15},
10.         {7, 9, 17, 14},
11.         {6, 9, 12, 8},
12.         {6, 7, 14, 6}
13.     };
15.     for (auto& t : times) {
16.         std::sort(t.begin(), t.end());
17.     }
19.     std::vector<int> cars = {0, 1, 2, 3}; // 车辆编号
21.     int min_time = 0;
22.     do {
23.         int current_time = 0;
24.         for (int i = 0; i < 4; ++i) {
25.             current_time += times[i][cars[i]];
26.         }
27.         min_time = std::min(min_time, current_time);
28.     } while (std::next_permutation(cars.begin(), cars.end()));
30.     std::cout << "最小时间为：" << min_time << std::endl;
32.     return 0;
33. }

复制代码

在这个程序中，我们首先对每个小车的到达时间进行排序。然后使用了std::next_permutation对所有可能的车辆到达顺序进行遍历，计算每种到达顺序下的总时间，并找出最小值。

球一个最佳答案谢谢啦！这对我非常重要！

ikkkki

Mike_python小 发表于 2023-11-7 19:23
小车最短时间问题

这个问题可以通过贪心算法来解决。我们可以对每个车库的时间进行排序，然后让每辆车按顺 ...

这个代码跑出来怎么是0，这个代码好像求的是总时间最小，题目的T是最后一辆小车入库的时间，

ikkkki

isdkz 发表于 2023-11-7 19:22
这是一个典型的旅行商问题（TSP），可以使用启发式算法来解决。其中最常用的是遗传算法（Genetic Algorithm ...

用最短路径来做求出来的是总时间最小，但这道题求的是T是最后一辆小车入库的时间，车辆都是同时出发

ikkkki

没人吗