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

动态最短路径

shortest-path graph algorithm

The Winter Soldier · 技术社区 · 8 年前

你的朋友正计划远征加拿大北部的一个小镇下个寒假。他们研究了所有的旅行选择,并制定了一个有针对性的计划图的节点表示中间目的地,边表示中间目的地之间的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 回复 | 直到 8 年前

Luai Ghunim 8 年前

关键是 函数单调递增 . 有一种算法利用了这个特性,叫做 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 代码在这里。