algorithm - 严重停留在图形任务上

Question

You have a graph with K ports and N cities, there are M ships in each port which carry X load units each (all of them are fully loaded at the beginning and can't reload at any time and all of them carry the same quantity of cargo). Every city needs some amount of cargo (may need the same amount, may not - depends on the input) and a ship can only unload its cargo in a city if it fulfills the city's whole needs (i.e. if a city needs 10 units of cargo, you can't unload 7 from one ship and 3 from the other - either one supplies all 10 units or it has no business of stopping there).

Every port is connected to every other port and every other city (cities are also connected with each other - basically everything is connected with everything) and you know the distance from each point to any other. What is the minimal cost (sum of the distances) all the ships must traverse and what are their respective routes if all the cities have to have their needs fulfilled and each ship has to end its journey in the same port that it started from?

这是我正在努力的一项任务，旨在提高我解决问题的能力。我想到了一种贪婪的方法，即选择最近的城市，然后先去最近的城市，但这在像这样的简单情况下是不够的(假设每个港口都有一艘船):

C1 <--11km--> P1 <--10km--> C2 <--10km--> P2 
where P are ports and C are cities 
(There should also be direct edges from C1 to C2 or P1 to P2 for example 
but I omitted them for clarity - let's just assume here all the verices
lie on the same line and so we could ignore them)

因为从 P1 出发的船会去 C2 从而使到 C1 的路线更长，而最佳解决方案是让它去更远的 C1，让 P2 的船去处理 C2。那么解决这个问题的正确方法是什么？或者它可能是 NP 完全的但没有？例如，我试着用 TSP 来考虑它，但它不太相似，因为你不在这里寻找哈密顿循环。

Answer 1

您的问题是 NP-hard 问题，如下所示。假设你有两个港口，其中一个港口有 2 艘船，另一个港口有任意数量的船只，从第一个港口到任何城市的旅行成本基本上为零，而从第二个港口到任何城市的旅行成本任何城市都很大。还可以想象从任何一个城市到另一个城市的旅行成本非常低。假设每艘船的载货量为 M，城市的总载货需求为 2*M。然后你想把城市分成两组，每组城市的总需求是 M，这样你就可以使用从第一个港口出发的两艘 M 容量的船，它们的旅行成本很低。否则，您也必须使用其他港口的其他船只，并产生非常大的旅行费用。但是，将一组数字拆分为两个具有相同总和的不相交集合是一个 NP 完全问题。因此，您的问题是 NP-hard。

因此，启发式或暴力破解可能是您最好的选择。