c - 如何编写此图相关算法

Question

因此，假设您有一列火车和 10.000 (0...9999) 个车站。火车在0号站。

每个站点都有一些货物要运送到任何其他站点之一。并且发往其他站的货物数量是随机的：每站1~100吨。

您的火车一次最多只能运载 50 吨。一旦火车在任何车站提货，它必须先卸货，然后才能提货（即如果当前列车载重1吨，即使剩余49吨空间也不能提货）。

因此，开发火车将在最短的时间内运送所有货物的算法。

Answer 1

这是我第一次快速思考这个问题，如果我想到更好的答案，我会回来编辑我的答案。其他人也许能够接受我提供的东西并为您提供更多帮助。这是“蛮力”方法，可能有更好的方法来解决这个问题。

1. 枚举所有起点/终点对（看起来是一个输入）。-10,000 次操作。对于需要比火车提供更多容量的车站，将它们分成额外的起点/终点对。
2. 枚举起源/目的地对的所有排列 - 10,000！操作（n*n 复杂度） - 在循环内，不保存每一个。
3. 对于每个排列，计算火车行驶的总距离。对于每一对，这将是之前的行驶距离加上到起点的火车 + 到目的地的火车。对排列中的所有对执行此操作。将此单个值与您之前的单个值进行比较。如果它更小，请保留这个和一串排列。如果你保留一个新的排列，就扔掉你以前的排列串。这应该是 10,000 * c (1?) 次操作。只保存这些排列中的一种，如果保存所有排列，那么如果你保存它们，你将耗尽内存。我认为。

我认为它的复杂性大约是 n+n*n+n = 2n+n^2。这对于 10,000 个站点应该是可行的。小心内存，当我最初开始写这篇文章时，我想保存所有可能需要 20,000 的排列！在记忆中。

抱歉，我使用的是美国方式 , 而不是 . 用于千位分隔符。

希望这会有所帮助！