算法 - 请帮助。 [英] Algorithm - Help please.
问题描述
我想要一个能够在给定一组节点的情况下提供最佳路径的算法。但是，虽然我已经尝试了一段时间，但我无法提出解决方案。我想知道是否可以做到这一点。这是我的需求。
1.我有一组节点，通常大约有20个节点。
2.每个节点都相互连接，我知道所有初始权重。
3.我必须在路径中访问每个节点一次。但是，在路径中可以访问任意次数的特殊节点。
4.两个节点之间的旅行成本是动态的。假设重量S-> A是10而A-> B是25.现在，如果我采用路径S-> A-> B，那么我不会花费10 + 25 = 35，但是，10 +（10 + 25）= 45.也就是说，你随身携带最后一个砝码。因此，一旦你行进S-> A，连接到A的边缘的权重增加10（S-> A的成本。）
这是原因对我来说很头疼。如果不是这样的话，应用Dijkstra的算法就能解决问题。但由于这个原因，我不能仅仅通过查看到目前为止的成本来消除任何路径。
5.一旦路径到达特殊节点，比如G，所有重量都重置为原始重量。
那么，谁能告诉我这个算法呢？我会非常感激的。谢谢。
Hi,
I want an algorithm that will provide the best path given a set of nodes. However, I have been unable to come up with a solution though I have tried for some time now. I want to know whether this can even be done. Here are my needs.
1. I have a set of nodes, usually about, 20 nodes.
2. Every node is connected to each other and I know all the initial weights.
3. I have to visit every node exactly once in the path. However, there is a special node that can be visited any number of times in the path.
4. The cost of travelling between two nodes are dynamic. Say the weigths S->A is 10 and A->B is 25. Now, if I were to take the path S->A->B, it would cost me not 10 + 25 = 35, but, 10 + (10 + 25) = 45. That is, you carry the last weights with you. So, as soon as you travel S->A, the weights of the edges connected to A are incremented by 10 (the cost of S->A.)
This is the cause of the headache for me. if this wasn''t the case, applying Dijkstra''s algorithm would have solved the problem. But because of this reason, I can''t eliminate any path just by looking at the cost so far.
5. As soon as the path reachs the special node, say G, all the weights are reset to their original weights.
So, can anyone tell me an algorithm for this? I would be very greatful. Thank you.
推荐答案
4.两个节点之间的旅行费用是动态的。假设重量S-> A是10而A-> B是25.现在，如果我采用路径S-> A-> B，那么我不会花费10 + 25 = 35，但是，10 +（10 + 25）= 45.也就是说，你随身携带最后一个砝码。因此，一旦您行进S-> A，连接到A的边的权重增加10（S-> A的成本。）
4. The cost of travelling between two nodes are dynamic. Say the weigths S->A is 10 and A->B is 25. Now, if I were to take the path S->A->B, it would cost me not 10 + 25 = 35, but, 10 + (10 + 25) = 45. That is, you carry the last weights with you. So, as soon as you travel S->A, the weights of the edges connected to A are incremented by 10 (the cost of S->A.)
你能详细说明这个''规则'吗？如果路径有三个顶点怎么办？
说S - > A - > B个人边缘成本等于10,25和15.路径成本是多少？
第二：起始顶点是固定的吗？
亲切的问候，
Jos
Can you elaborate on this ''rule'' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?
Second: is the starting vertex fixed?
kind regards,
Jos
你能详细说明这个规则吗？如果路径有三个顶点怎么办？
说S - > A - > B个人边缘成本等于10,25和15.路径成本是多少？
第二：起始顶点是固定的吗？
亲切的问候，
Jos
Can you elaborate on this ''rule'' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?
Second: is the starting vertex fixed?
kind regards,
Jos
是的，起始节点是固定。
好吧，我们说我们有四条边。 S，A，B，C
一开始，这就是权重的方式：
S-> A 10
A-> B 25
B-> C 15
我们现在不关心其他边缘，所以我们这个例子不需要它们的权重。
现在，如果我们采用路径S-> A-> B-> C，总成本将是是，
S-> A A-> B B-> C
10 +（10）+ 25 +（ （10）+ 25）+ 15
所以，总费用= 10 +（10 + 25）+（（10）+25）+ 15 = 95.
希望清理完毕。这就像我们访问节点时权重累积一样。所以，我们必须承担所有那些过去的罪恶。和我们一样。
Yes, the starting node is fixed.
Ok, lets say that we have four edges. S, A, B, C
At the beginning, this is how the weights stand:
S->A 10
A->B 25
B->C 15
We are not concerned about the other edges at the moment, so we do not need their weights for this example.
Now, if we were to take the path S->A->B->C, the total cost will be,
S->A A->B B->C
10 + (10) + 25 + ((10) + 25) + 15
so, total cost = 10 + (10 + 25) + ((10) + 25) + 15 = 95.
Hope that cleared up. It''s like the weights accumulate when we visit a node. So, we have to carry all those past "sins" with us as well.
你能详细说明这个''规则'吗？如果路径有三个顶点怎么办？
说S - > A - > B个人边缘成本等于10,25和15.路径成本是多少？
第二：起始顶点是固定的吗？
亲切的问候，
Jos
Can you elaborate on this ''rule'' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?
Second: is the starting vertex fixed?
kind regards,
Jos
是的，起始节点是固定。
好吧，我们说我们有四条边。 S，A，B，C
一开始，这就是权重的方式：
S-> A 10
A-> B 25
B-> C 15
我们现在不关心其他边缘，所以我们这个例子不需要它们的权重。
现在，如果我们采用路径S-> A-> B-> C，总成本将是是，
S-> A A-> B B-> C
10 +（10）+ 25 +（ （10）+ 25）+ 15
所以，总费用= 10 +（10 + 25）+（（10）+25）+ 15 = 95.
希望清理完毕。这就像我们访问节点时权重累积一样。所以，我们必须承担所有那些过去的罪恶。和我们一起。
啊，终端节点也是固定的。它是特殊节点G。
Yes, the starting node is fixed.
Ok, lets say that we have four edges. S, A, B, C
At the beginning, this is how the weights stand:
S->A 10
A->B 25
B->C 15
We are not concerned about the other edges at the moment, so we do not need their weights for this example.
Now, if we were to take the path S->A->B->C, the total cost will be,
S->A A->B B->C
10 + (10) + 25 + ((10) + 25) + 15
so, total cost = 10 + (10 + 25) + ((10) + 25) + 15 = 95.
Hope that cleared up. It''s like the weights accumulate when we visit a node. So, we have to carry all those past "sins" with us as well.
Ah, the end node is fixed as well. it is the special node G.
这篇关于算法 - 请帮助。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
