严重停留在图形任务上
Heavily stuck on a graph task
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 完全的并且有 none？例如，我试着用 TSP 来考虑它，但它不太相似，因为你不在这里寻找哈密顿循环。
好的，所以我认为您可以使用 A* 状态 space 搜索算法来做到这一点。它类似于 Dykstra 的最短路径，但在节点上使用启发式函数。
我认为您可以将一次轮船旅程建模为图表上的一条边，每个节点将包含您的信息，包括每艘轮船的位置、载有多少货物以及已运送到每个城市的货物量。
State node:
List of ships
List of cities
Ship:
Cargo Capacity
Current Location
City:
Cargo Delivered
以上只是为每个州存储的数据。其他数据，如船舶所在城市，或一个城市需要多少货物，不能通过行动改变，因此它不是状态的一部分，它只是有用的背景信息。
如果是城市，图中的一条边就是移动船只和运送货物的动作。边缘权重就是城市之间的距离。
您还必须创建启发式函数，为每个状态提供某种适合度值。我们希望低适应度值是好的，高是坏的。启发式想到的一个想法是查看所有城市加在一起仍需要的货物量，再加上每艘不在其母港的船可能加 1。我不相信这种启发式是不一致或不可接受的。这是一种健身功能。
另一种启发式选择是计算未完全供应的城市，并添加不在其母港的船只数量。这种启发式方法是可以接受的（永远不会估计高于实际成本），但我不确定它是否会更好。有很多方法可以继续启发式。
那么您需要的另一个主要内容是 Expand(Node n) 函数，它根据您可以采取的所有可能操作为您提供所有可能的后继状态。
无论您使用什么启发式方法，如果您处于目标状态，都应该将其设为 return 零。因此，如果所有城市都有货物，并且所有船只都在其母港，那么它将 return 为零。
那么您只需 运行 通过标准的 A* 搜索即可！这是维基百科页面，如果你不熟悉的话。我相信还有很多其他好的资源可以用来学习它。如果您想对问题的 A* 算法部分进行更多解释，请告诉我。
http://en.wikipedia.org/wiki/A*_search_algorithm
一旦你涵盖了我提到的内容，你就拥有了所有的构建块：状态的表示、你的启发式函数可以访问的背景信息、一个也检查目标状态的启发式函数，以及一个获得后继的扩展函数基于可能的动作的状态，使用背景数据计算边缘权重。现在您只需在 A* 搜索算法的实现中使用那几个构建块，然后 bam，您就有了一个很好的解决方案。请记住，它可能无法证明是最佳解决方案，并且可能无法保证找到解决方案。我相信你的启发式函数的性质（是否可以接受and/or一致？）将决定是否保证解决方案或最佳解决方案。
您的问题是 NP-hard 问题，如下所示。假设你有两个港口，其中一个港口有 2 艘船，另一个港口有任意数量的船只，从第一个港口到任何城市的旅行成本基本上为零，而从第二个港口到任何城市的旅行成本任何城市都很大。还可以想象从任何一个城市到另一个城市的旅行成本非常低。假设每艘船的载货量为 M，城市的总载货需求为 2*M。然后你想把城市分成两组，每组城市的总需求是 M，这样你就可以使用从第一个港口出发的两艘 M 容量的船，它们的旅行成本很低。否则，您也必须使用其他港口的其他船只，并产生非常大的旅行费用。但是，将一组数字拆分为两个具有相同总和的不相交集合是一个 NP 完全问题。因此你的问题是 NP-hard.
因此，启发式或暴力破解可能是您最好的选择。
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 完全的并且有 none？例如，我试着用 TSP 来考虑它，但它不太相似，因为你不在这里寻找哈密顿循环。
好的，所以我认为您可以使用 A* 状态 space 搜索算法来做到这一点。它类似于 Dykstra 的最短路径，但在节点上使用启发式函数。
我认为您可以将一次轮船旅程建模为图表上的一条边，每个节点将包含您的信息，包括每艘轮船的位置、载有多少货物以及已运送到每个城市的货物量。
State node:
List of ships
List of cities
Ship:
Cargo Capacity
Current Location
City:
Cargo Delivered
以上只是为每个州存储的数据。其他数据，如船舶所在城市，或一个城市需要多少货物，不能通过行动改变，因此它不是状态的一部分，它只是有用的背景信息。
如果是城市，图中的一条边就是移动船只和运送货物的动作。边缘权重就是城市之间的距离。
您还必须创建启发式函数，为每个状态提供某种适合度值。我们希望低适应度值是好的，高是坏的。启发式想到的一个想法是查看所有城市加在一起仍需要的货物量，再加上每艘不在其母港的船可能加 1。我不相信这种启发式是不一致或不可接受的。这是一种健身功能。
另一种启发式选择是计算未完全供应的城市，并添加不在其母港的船只数量。这种启发式方法是可以接受的（永远不会估计高于实际成本），但我不确定它是否会更好。有很多方法可以继续启发式。
那么您需要的另一个主要内容是 Expand(Node n) 函数，它根据您可以采取的所有可能操作为您提供所有可能的后继状态。
无论您使用什么启发式方法，如果您处于目标状态，都应该将其设为 return 零。因此，如果所有城市都有货物，并且所有船只都在其母港，那么它将 return 为零。
那么您只需 运行 通过标准的 A* 搜索即可！这是维基百科页面，如果你不熟悉的话。我相信还有很多其他好的资源可以用来学习它。如果您想对问题的 A* 算法部分进行更多解释，请告诉我。 http://en.wikipedia.org/wiki/A*_search_algorithm
一旦你涵盖了我提到的内容，你就拥有了所有的构建块：状态的表示、你的启发式函数可以访问的背景信息、一个也检查目标状态的启发式函数，以及一个获得后继的扩展函数基于可能的动作的状态，使用背景数据计算边缘权重。现在您只需在 A* 搜索算法的实现中使用那几个构建块，然后 bam，您就有了一个很好的解决方案。请记住，它可能无法证明是最佳解决方案，并且可能无法保证找到解决方案。我相信你的启发式函数的性质（是否可以接受and/or一致？）将决定是否保证解决方案或最佳解决方案。
您的问题是 NP-hard 问题，如下所示。假设你有两个港口，其中一个港口有 2 艘船，另一个港口有任意数量的船只，从第一个港口到任何城市的旅行成本基本上为零，而从第二个港口到任何城市的旅行成本任何城市都很大。还可以想象从任何一个城市到另一个城市的旅行成本非常低。假设每艘船的载货量为 M，城市的总载货需求为 2*M。然后你想把城市分成两组，每组城市的总需求是 M，这样你就可以使用从第一个港口出发的两艘 M 容量的船，它们的旅行成本很低。否则，您也必须使用其他港口的其他船只，并产生非常大的旅行费用。但是，将一组数字拆分为两个具有相同总和的不相交集合是一个 NP 完全问题。因此你的问题是 NP-hard.
因此，启发式或暴力破解可能是您最好的选择。