查找從一個節點到另一個節點的路徑是一個經典的圖形搜索問題, 我們可以使用多個遍歷算法 (如bfsdfs)來解決此問題。但是, 如果我們想要找到從一個節點到另一個節點的最短路徑, bfsdfs遍歷不會對我們有太大幫助, 因此我們需要使用其他算法, 如bellman-ford、 floyd-warshall 或 dijkstra。在本文中, 我想重點介紹 dijkstra 算法, 并了解我們可以做些什么來改進它, 使它更快, 從而將它轉換為 a 星 (a *) 算法。

在正加權圖中尋找最短路徑

在正加權圖中, 我們可以使用dijkstra算法計算從a點到b 點成本最低的路徑。如果有負成本的路徑, dijkstra 就行不通了, 所以我們必須尋找其他方法, 比如bellman-ford活期-warshall算法。

該算法的主要思想是, 從一個節點開始, 下一個要訪問的節點是從源到它的遍歷成本最低的節點。因此, 這看起來幾乎像bfs, 通過有一個帶有節點的隊列, 并且在每次迭代中, 我們都會從隊列中提取一個元素并訪問它。dijkstrabfs之間的區別在于, 使用bfs , 我們有一個簡單的fifo隊列, 下一個要訪問的節點是在隊列中添加的第一個節點。但是, 使用dijkstra,我們需要以迄今為止最低的成本拉節點。

讓我們看一個簡單的例子:

Image title

我們希望使用bfsae , 因此, 我們將使用一個簡單的 fifo 隊列。從節點a開始, 我們得到相鄰的節點bc, 并將它們放在隊列中。接下來, 我們從隊列中提取已添加的第一個元素節點 b, 并檢查相鄰節點 a 和d. a被訪問, 所以我們忽略了它, 我們將節點d添加到隊列中。因此, 隊列現在包含節點cd

我們向前移動, 并從隊列中獲取節點c , 檢查相鄰節點, ae.我們忽略了 a , 因為我們已經訪問過它, 我們看到我們到達了 e , 我們停了下來。因此, 我們找到了一條路徑, a > c > e,總成本為22。這就是成本最低的道路嗎?好吧, 不。讓我們通過更改從隊列中檢索元素的方式來更改算法以查找最短路徑。

作為一個小觀察, 經典的 bfs算法遍歷所有圖形, 當隊列為空時, 它就會停止。這是一個稍有變化的算法, 更貪婪, 當我們找到目的地時, 我們就會停下來。

因此, 讓我們看看我們得到了什么, 如果我們從隊列中提取到目前為止成本最低的節點。從a 開始, 我們檢查相鄰節點 b 和 c, 并計算從a 到每個節點的路徑成本。因此, 我們有一個隊列與:

Queue: {
  B, cost_so_far: 2
  C, cost_so_far: 10 
}

現在, 使用dijkstra,我們選擇訪問具有最低的節點 cost_so_far , 即bcost_so_far節點 d 是 b 加上 b 和 d 之間的成本, 即 3. cost_so_far 所以我們的總成本是5。我們把它放在隊列中, 隊列將如下所示:

Queue {
  C, cost_so_far: 10,
  D, cost_so_far: 5
}

在相同的過程之后, 我們從隊列中提取節點d , 因為它的節點 cost_so_far 最少, 盡管以前添加了c 。我們檢查它, 我們看到我們達到e cost_so_far 等于 10 + 4 = 14。我們將其添加到隊列中, 再次從隊列中選擇要訪問的下一個節點。隊列將如下所示:

Queue {
  E, cost_so_far: 14
  C, cost_so far: 10
}

我們不會停在這里, 但我稍后會解釋。但是, 就目前而言, 讓我們繼續這一進程。我們看隊列, 我們拉的節點是最低 cost_so_far 的, 即cc有兩個鄰居, a以前訪問過, e cost_so_far 等于14。現在, 如果我們計算到e的路徑成本, 通過c, 我們將有一個 cost_so_far 等于 22, 這大于當前 cost_so_far 的 14, 所以我們不會改變它。

向前移動, 我們將有一個具有單個節點 e 的隊列。我們拿著它, 看到我們到達了目的地, 所以我們停下來了。我們現在的路徑成本最低, 從ae, a-> b-> > e,總成本為14。因此, 使用bfs我們找到了一條總成本為22的路徑, 但是, 使用dijkstra, 我們看到了一條成本更低的路徑, 成本更低, 為14。

那么, 為什么我們第一次到達節點e時沒有早點停下來呢?好吧, 讓我們把ed之間的邊緣成本更改為20。

Image title

在這種情況下, 從ad的所有步驟都是相同的。但是, 在我們訪問節點 d 后, 隊列將如下所示:

Queue {
  E, cost_so_far: 25
  C, cost_so far: 10
}

我們采用c, 因為它有最低 cost_so_far 的, 我們計算 cost_so_far ec的潛力, 這是 22, 我們看到新的值低于當前 cost_so_far , 25。所以我們更新它, e將有一個 cost_so_far 新的等于 22, 通過c。當我們從隊列中提取節點e時, 我們看到我們到達了目的地, 我們找到了從ae成本最低的路徑, 即a-> c-> e,總成本為22。

因此, 即使我們訪問一個節點時, 我們 “看到” 我們的目標, 我們計算 cost_so_far 它, 我們不會停在那里, 因為可能有另一條路徑具有更低的成本。所以, 每次訪問一個節點, 我們都會看它的鄰居, 即使 cost_so_far 我們在以前訪問另一個節點時已經計算出了 a, 我們也會通過更新 cost_so_far 是否比當前節點低來檢查是否找到了更好的路徑

迪伊克斯特拉實施建議

讓我們看看如何實現這一點。我們將從一個節點開始, 該節點的鄰居有一個名稱和一個鄰接列表。除了這些字段, 我們還可以添加一個 cost_so_far 字段, 讓我們稱之為 g_cost 字段, 以及一個父字段。搜索算法將設置這兩個字段, 我們將使用它們來查找從一個節點到另一個節點的成本最低的路徑。我們可以通過將 “無限 g_cost ” 和 “父” 設置為 “無限 null ” 來初始化這些字段。這可能如下所示:

static class Node{
  public final String name;
  public List<Edge> adjacency = new ArrayList<>();
  public Node parent;
  public double g_cost = Integer.MAX_VALUE;

  public Node(String name){
    this.name = name;
  }

  public void addNeighbour(Node neighbour, int cost) {
    Edge edge = new Edge(neighbour, cost);
    adjacency.add(edge);
  }

  public String toString(){
    return name;
  }
}

邊具有成本和目標節點。

static class Edge{
  public final double cost;
  public final Node target;

  public Edge(Node target, double cost){
    this.target = target;
    this.cost = cost;
  }
}

現在的算法。正如我之前所說, 此算法的主要思想是, 從一個節點開始, 要訪問的下一個節點是一個從源到它的成本最低的節點。為此, 我們可以使用“優先級隊列“, 讓我們將其稱為 “邊框”, 節點按. g_cost當我們訪問一個節點時, 如果我們為它的鄰居找到更好的方法, 我們只需將它們添加到邊框 g_cost 中并更新, 而且, 由于邊界是優先級隊列, 它將維護按值排序的節點 g_cost 。當我們訪問目的地時, 這意味著我們找到了從源頭到目的地的最佳路徑, 我們就停下來了。

這是算法實現:

public static void dijkstraSearch(Node source, Node destination) {
  source.g_cost = 0;

  PriorityQueue<Node> frontier = new PriorityQueue<>(new Comparator<Node>() {
    @Override
    public int compare(Node o1, Node o2) {
      return Double.compare(o1.g_cost, o2.g_cost);
    }
  });


  frontier.add(source);

  int numberOfSteps = 0;
  while (!frontier.isEmpty()) {
    numberOfSteps++;
    // get the node with minimum g_cost
    Node current = frontier.poll();

    System.out.println("Current node: " + current.name);

    // we have found the destination
    if (current.name.equals(destination.name)) {
      break;
    }

    // check all the neighbours
    for (Edge edge: current.adjacency) {

      Node neigh = edge.target;
      double cost = edge.cost;

      double newCost = current.g_cost + cost;

      if (newCost < neigh.g_cost) {
        neigh.parent = current;
        neigh.g_cost = newCost;

        // reset frontier order
        if (frontier.contains(neigh)) {
          frontier.remove(neigh);
        }

        frontier.add(neigh);
      }
    }
  }

  System.out.println("Number of steps: " + numberOfSteps);
}

同樣, 正如我之前對bfs 實現所說的, 這是 dijkstra 算法的一個稍微修改的版本, 稱為統一成本搜索, 當我們找到目標時, 我們會在該算法中停止。經典的 dijkstra算法繼續訪問所有節點, 直到隊列為空, 找到從起始節點到所有其他節點的最小路徑成本。

讓我們看看這是如何在真正的地圖上工作的假設我們要在最短的路徑上從阿拉德開車到布加勒斯特。

Image title

我們可以看到, 我們可以走多條路線。我們可以從阿拉德到蒂米什瓦拉, 然后盧戈杰, 等等, 或者我們可以選擇錫比烏, 然后法加拉, 直接去布加勒斯特。但我們不知道哪條路的成本最低。所以, 這是一個很好的候選人的 dijkstra算法。在羅馬尼亞地圖上運行我們的實現將得到這樣的:

Total Cost: 418.0
Path: [Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest]

這就是成本最低的道路 (相信我, 我其實來自羅馬尼亞, 我可以向你保證, 這是最短的路)。因此, 使用 dijkstra 算法, 我們能夠找到成本最低的路徑, 但讓我們看看在訪問節點時打印節點所需的步驟是多少:

Current node: Arad
Current node: Zerind
Current node: Timisoara
Current node: Sibiu
Current node: Oradea
Current node: Rimnicu Vilcea
Current node: Lugoj
Current node: Fagaras
Current node: Mehadia
Current node: Pitesti
Current node: Craiova
Current node: Drobeta
Current node: Bucharest
Number of steps: 13

因此, 我們需要訪問13個節點, 以找到最佳路徑。正如你所看到的, 從阿拉德我們沒有直接去錫比烏, 我們是通過澤林到達的, 然后是蒂米什瓦拉, 然后是錫比烏。而且, 即使在那之后, 我們也沒有去里姆尼庫瓦爾塞亞, 而是去了奧拉迪亞, 因為那是迄今為止成本最低的節點。這就是這個算法的工作原理。13個節點訪問, 以找到我們的路徑, 其中許多節點沒有在路徑上的成本最低反正。但我們不知道這一點, 我們不得不去看望他們才能知道。

這都是第1部分!來 abc 周一, 當我們將涵蓋如何使用 a 星 [a (*)] 算法解決這個問題。

Comments are closed.