代码之家  ›  专栏  ›  技术社区  ›  The Winter Soldier

动态最短路径

  •  0
  • The Winter Soldier  · 技术社区  · 7 年前

    你的朋友正计划远征加拿大北部的一个小镇 下个寒假。他们研究了所有的旅行选择,并制定了一个有针对性的计划 图的节点表示中间目的地,边表示中间目的地之间的REOAD 他们 在此过程中,他们还了解到极端天气会导致该地区出现道路 冬季,世界将变得相当缓慢,并可能导致严重的旅行延误。他们已经 找到了一个优秀的旅游网站,可以准确预测他们的旅行速度 沿道路行驶;然而,旅行的速度取决于一年中的时间。更多 准确地说,该网站回答以下形式的查询:给定边e=(u,v) 连接两个站点u和v,并给定从位置u开始的拟议开始时间t,则 网站将返回值fe(t),即预计到达v的时间。网站保证: 1. fe(t)>对于每一条边e和每一次t(你不能在时间上向后移动),并且 fe(t)是t的单调递增函数(也就是说,你不会因为开始而提前到达) 稍后)。除此之外,函数fe可以是任意的。例如,在 e, where e是 从边缘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算法,但它不正确?我会在我的算法中改变什么来处理动态变化的边缘。

    1 回复  |  直到 7 年前
        1
  •  1
  •   Luai Ghunim    7 年前

    关键是 函数单调递增 . 有一种算法利用了这个特性,叫做 A* .

    累计成本: 您的教授希望您使用两个距离,一个是累积成本(这很简单,是将上一个节点的成本加上移动到下一个节点所需的成本/时间)。

    启发式成本: 这是一些预测成本。

    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-puzzle-solve,它可以让您了解如何定义成本以及它的工作原理。

    `

    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 代码在这里。