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

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++代码的一个例子：

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

在这个程序中，我们首先对每个小车的到达时间进行排序。然后使用了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

没人吗