你的朋友正计划远征加拿大北部的一个小镇
下个寒假。他们研究了所有的旅行选择，并制定了一个
节点表示中间目的地，边表示中间目的地之间的reoad的图
他们。
在此过程中，他们还了解到，极端天气会导致
世界在冬季变得相当缓慢，并可能导致大的旅行延误他们已经
找到了一个优秀的旅游网站，可以准确地预测他们能以多快的速度
沿着公路旅行；然而，旅行的速度取决于一年中的时间。更多
准确地说，该网站回答了以下形式的查询：给定一个edge e=（u，v）
连接两个站点u和v，并给出从位置u开始的建议起始时间t
网站将返回一个值fe（t），预测到达v的时间。网站保证
一
fe（t）>t对于每一条边e和每一次t（你不能在时间上向后移动），并且
fe（t）是t的单调递增函数（也就是说，你不能通过开始
稍后）除此之外，函数fe可以是任意的例如，在
旅行时间不随季节而变化，我们将得到fe（t）=t+e, wheree是
从边缘e的开始到结束所需的时间。
您的朋友想使用网站来确定最快的旅行方式
有向图从它们的起点到它们的预定目的地。（你应该假设
它们从时间0开始，网站所做的所有预测都是完全正确的
正确。）为此提供一个多项式时间算法，其中我们将单个查询处理为
网站（基于特定的边缘e和时间t）作为一个计算步骤。
def updatepath(node):
randomvalue = random.randint(0,3)
print(node,"to other node:",randomvalue)
for i in range(0,n):
distance[node][i] = distance[node][i] + randomvalue
def minDistance(dist,flag_array,n):
min_value = math.inf
for i in range(0,n):
if dist[i] < min_value and flag_array[i] == False:
min_value = dist[i]
min_index = i
return min_index
def shortest_path(graph, src,n):
dist = [math.inf] * n
flag_array = [False] * n
dist[src] = 0
for cout in range(n):
#find the node index that have min cost
u = minDistance(dist,flag_array,n)
flag_array[u] = True
updatepath(u)
for i in range(n):
if graph[u][i] > 0 and flag_array[i]==False and dist[i] > dist[u] + graph[u][i]:
dist[i] = dist[u] + graph[u][i]
path[i] = u
return dist
我应用了Dijkstra算法，但它不正确我将在我的算法中改变什么来工作它的动态变化的边缘。
最佳答案
关键是函数是单调递增的。有一个算法利用了这个属性，它被称为一个*。
累积成本：你的教授希望你使用两个距离，一个是累积成本（这很简单，就是从先前的成本加上移动到下一个节点所需的成本/时间）。
启发式成本：这是一些预测成本。
disjkstra方法不起作用，因为您使用的是启发式成本/预测和累积成本。
单调递增意味着h（a）<=h（a）+f（a..b），简单地说，如果从节点a移动到节点b，则成本不应小于前一个节点（在这种情况下为a），这是启发式+累积的。如果此属性保持不变，则a*选择的第一条路径始终是指向目标的路径，并且它不需要回溯。
注意：这个算法的能力完全取决于你如何预测值。
如果你低估了将用累积值修正的值，但如果你高估了该值，它将选择错误的路径。
算法：
Create a Min Priority queue.
insert initial city in q.
while(!pq.isEmpty() && !Goalfound) Node min = pq.delMin() //this should return you a cities to which your distance(heuristic+accumulated is minial). put all succesors of min in pq // all cities which you can reach, you can better make a list of visited cities s that queue will be efficient by not placing same element twice.Keep doing this and at the end you will either reach goal or your queue will be empty额外的
在这里，我使用*实现了一个8字谜解决方案，它可以让您了解如何定义成本以及如何工作。
`
private void solve(MinPQ<Node> pq, HashSet<Node> closedList) {
while(!(pq.min().getBoad().isGoal(pq.min().getBoad()))){
Node e = pq.delMin();
closedList.add(e);
for(Board boards: e.getBoad().neighbors()){
Node nextNode = new Node(boards,e,e.getMoves()+1);
if(!equalToPreviousNode(nextNode,e.getPreviousNode()))
pq.insert(nextNode);
}
}
Node collection = pq.delMin();
while(!(collection.getPreviousNode() == null)){
this.getB().add(collection.getBoad());
collection =collection.getPreviousNode();
}
this.getB().add(collection.getBoad());
System.out.println(pq.size());
}
这里有一个full代码的链接。