Từ Dijkstra đến A Star (A *), Phần 1: Thuật toán Dijkstra


Phan Xuân Thu
8 tháng trước
Hữu ích 2 Chia sẻ Viết bình luận 0
Đã xem 9070

Tìm một đường dẫn từ nút này đến nút khác là một vấn đề tìm kiếm đồ thị cổ điển mà chúng ta có thể giải quyết bằng nhiều thuật toán truyền tải như BFS hoặc DFS . Nhưng, nếu chúng ta muốn tìm con đường ngắn nhất từ ​​nút này sang nút khác, các giao dịch BFS hoặc DFS sẽ không giúp chúng ta quá nhiều, vì vậy chúng ta cần sử dụng các thuật toán khác như Bellman-Ford , Floyd-Warshall hoặc Dijkstra . Trong bài viết này, tôi muốn tập trung vào thuật toán Dijkstra và xem chúng ta có thể làm gì để cải thiện nó, để làm cho nó nhanh hơn, do đó, biến nó thành thuật toán A star (A *).

Tìm đường đi ngắn nhất trong đồ thị có trọng số dương

Trong biểu đồ có trọng số dương, chúng ta có thể tính toán đường dẫn với chi phí thấp nhất từ ​​điểm A đến điểm B , bằng thuật toán Dijkstra . Nếu có các đường dẫn có chi phí âm, Dijkstra sẽ không hoạt động, vì vậy chúng tôi sẽ phải tìm đến các phương pháp khác, như thuật toán Bellman-Ford hoặc Floyd-Warshall .

Ý tưởng chính của thuật toán này là bắt đầu từ một nút, nút tiếp theo để truy cập là nút có chi phí thấp nhất so với truyền tải từ nguồn tới nó. Vì vậy, nó trông gần giống như BFS , bằng cách có một hàng đợi với các nút và, ở mỗi lần lặp, chúng ta kéo một phần tử từ hàng đợi và truy cập nó. Sự khác biệt giữa DijkstraBFS là với BFS, chúng ta có một hàng đợi FIFO đơn giản và nút tiếp theo để truy cập là nút đầu tiên được thêm vào trong hàng đợi. Nhưng, bằng cách sử dụng Dijkstra, chúng ta cần phải kéo nút với chi phí thấp nhất cho đến nay.

Hãy xem một ví dụ đơn giản:

Chúng tôi muốn đi từ A đến E bằng BFS , vì vậy, chúng tôi sẽ sử dụng hàng đợi FIFO đơn giản. Bắt đầu từ nút A , chúng tôi nhận được các nút lân cận, BC và chúng tôi đặt chúng vào hàng đợi. Tiếp theo, chúng tôi kéo từ hàng đợi các yếu tố đầu tiên mà đã được thêm vào, nút B , và chúng tôi kiểm tra các nút láng giềng,  MộtD . A đã được truy cập, vì vậy chúng tôi bỏ qua nó và chúng tôi thêm nút D vào hàng đợi. Vì vậy, các hàng đợi bây giờ chứa các nút CD .

Chúng tôi di chuyển về phía trước và chúng tôi nhận được nút C từ hàng đợi, kiểm tra các nút lân cận, AE.  Chúng tôi bỏ qua A vì chúng tôi đã truy cập vào nó và chúng tôi thấy rằng chúng tôi đã đến E và chúng tôi dừng lại. Vì vậy, chúng tôi đã tìm thấy một đường dẫn, A -> C -> E , với tổng chi phí là 22. Đây có phải là đường dẫn có chi phí thấp nhất không? Ồ không. Hãy thay đổi thuật toán để tìm đường đi ngắn nhất, bằng cách thay đổi cách truy xuất các phần tử từ hàng đợi.

Như một quan sát nhỏ, thuật toán BFS cổ điển đi qua tất cả các biểu đồ và nó dừng lại khi hàng đợi trống. Đây là một thuật toán thay đổi một chút mà tham lam hơn, nơi chúng ta dừng lại khi tìm thấy đích đến của mình.

Vì vậy, hãy xem những gì chúng ta nhận được, nếu chúng ta kéo từ hàng đợi nút với chi phí thấp nhất cho đến nay. Bắt đầu từ A , chúng tôi kiểm tra các nút lân cận, BC và chúng tôi tính toán chi phí đường dẫn từ A đến từng nút  . Vì vậy, chúng tôi có một hàng đợi với:

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

Bây giờ, sử dụng Dijkstra , chúng tôi chọn để truy cập các nút với mức thấp nhất cost_so_far, đó là B . Chúng tôi kiểm tra các nút lân cận, AD , chúng tôi thấy rằng nút D không có bất kỳ nút nào cost_so_farvà chúng tôi tính toán nó. Các  cost_so_far cho nút D là  cost_so_far cho B cộng với chi phí giữa BD , đó là 3. Vì vậy, chúng ta có một tổng chi phí 5. Chúng tôi đặt nó trong hàng đợi và hàng đợi sẽ trông như thế này:

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

Theo cùng một quy trình, chúng tôi kéo nút D khỏi hàng đợi, bởi vì nó có mức thấp nhất cost_so_far, mặc dù thực tế là C đã được thêm vào trước đó. Chúng tôi kiểm tra nó và chúng tôi thấy rằng chúng tôi đã đạt E với giá trị  cost_so_far bằng 10 + 4 = 14. Chúng tôi thêm nó vào hàng đợi và một lần nữa, chúng tôi chọn nút tiếp theo để truy cập từ hàng đợi. Hàng đợi sẽ như thế này:

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

Chúng tôi không dừng lại ở đây, nhưng tôi sẽ giải thích điều này một lát sau. Nhưng, bây giờ, hãy tiếp tục quá trình. Chúng tôi nhìn vào hàng đợi, và chúng tôi kéo nút với mức thấp nhất  cost_so_far C . C có hai hàng xóm, A đã được truy cập trước đó và E có giá trị  cost_so_far bằng 14. Bây giờ, nếu chúng ta tính chi phí đường dẫn đến E , thông qua C , chúng ta sẽ có giá trị  cost_so_far bằng 22, lớn hơn cost_so_far 14 hiện tại  , vì vậy chúng tôi không thay đổi nó.

Trong tương lai, chúng ta sẽ có một hàng đợi với một nút duy nhất, E . Chúng tôi lấy nó và chúng tôi thấy rằng chúng tôi đã đến đích, vì vậy chúng tôi dừng lại. Bây giờ chúng ta có đường dẫn với chi phí thấp nhất, từ A đến E , A -> B -> D -> E, với tổng chi phí là 14. Vì vậy, sử dụng BFS, chúng tôi đã tìm thấy một đường dẫn có tổng chi phí là 22, nhưng, sử dụng Dijkstra , chúng tôi đã thấy một con đường tốt hơn với chi phí thấp hơn là 14.

Vậy tại sao chúng ta không dừng lại sớm hơn khi lần đầu tiên đến nút  E ? Chà, hãy thay đổi chi phí cạnh giữa ED thành 20.


Trong trường hợp này, tất cả các bước từ  A đến D , sẽ giống nhau. Nhưng, sau khi chúng ta truy cập nút D, hàng đợi sẽ như thế này:

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

Chúng tôi có C , bởi vì nó có mức thấp nhất cost_so_far, và chúng tôi tính toán tiềm năng  cost_so_far cho E qua C , đó là 22, và chúng ta thấy rằng giá trị mới là thấp hơn so với hiện tại cost_so_far, 25. Vì vậy, chúng tôi cập nhật nó và E sẽ có một mới  cost_so_far bằng đến 22, qua C . Khi chúng ta kéo nút E từ hàng đợi, chúng ta thấy rằng chúng ta đã đến đích và chúng ta đã tìm thấy đường dẫn có chi phí thấp nhất từ A đến E , đó là A -> C -> E với tổng chi phí là 22.

Vì vậy, ngay cả khi chúng tôi đang truy cập vào một nút, chúng tôi sẽ thấy điểm đến của chúng tôi và chúng tôi tính toán  cost_so_far cho điểm đó, chúng tôi không dừng lại ở đó, bởi vì có thể có một con đường khác với chi phí thấp hơn. Vì vậy, mỗi khi chúng tôi truy cập một nút, chúng tôi tìm đến các nút lân cận và, ngay cả khi chúng tôi đã tính toán một  cost_so_far lần trước khi chúng tôi truy cập một nút khác, chúng tôi sẽ kiểm tra xem liệu chúng tôi có tìm thấy đường dẫn tốt hơn không, bằng cách cập nhật  cost_so_far nếu nó thấp hơn hiện tại một. Đó là lý do tại sao thuật toán Dijkstra có thể tìm thấy đường dẫn với chi phí thấp nhất.

 Đề xuất thực hiện Dijkstra

Chúng ta hãy xem làm thế nào chúng ta có thể thực hiện điều này. Chúng ta sẽ bắt đầu với một nút có tên và danh sách kề cho các hàng xóm của nó. Bên cạnh các trường đó, chúng ta cũng có thể thêm một  cost_so_far trường, hãy gọi nó g_costvà cha mẹ. Thuật toán tìm kiếm sẽ đặt hai trường này và chúng tôi sẽ sử dụng chúng để tìm đường dẫn có chi phí thấp nhất từ ​​nút này sang nút khác. Chúng ta có thể khởi tạo các trường này bằng cách đặt giá trị  g_cost là vô hạn và cha mẹ là null. Điều này có thể trông như thế này:

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;
  }
}

Một cạnh có một chi phí và một nút mục tiêu.

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

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

Và bây giờ là thuật toán. Giống như tôi đã nói trước đây, ý tưởng chính của thuật toán này là khi bắt đầu từ một nút, nút tiếp theo được truy cập là nút có chi phí thấp nhất từ ​​nguồn đến nó. Đối với điều này, chúng ta có thể sử dụng Hàng đợi ưu tiên , hãy gọi nó là một biên giới, với các nút được sắp xếp theo g_cost. Khi chúng ta truy cập một nút, nếu chúng ta tìm thấy một cách tốt hơn cho các hàng xóm của nó, chúng ta chỉ cần thêm chúng vào biên giới và cập nhật  g_cost, và, vì biên giới là một hàng đợi ưu tiên, nó sẽ duy trì các nút được sắp xếp theo  g_cost  giá trị. Khi chúng tôi truy cập điểm đến, điều đó có nghĩa là chúng tôi đã tìm thấy con đường tốt nhất từ ​​nguồn đến đích và chúng tôi dừng lại.

Đây là việc thực hiện thuật toán:

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);
}

Một lần nữa, như tôi đã nói trước đây về việc triển khai BFS , đây là phiên bản sửa đổi một chút của thuật toán Dijkstra , được gọi là Tìm kiếm chi phí thống nhất , nơi chúng tôi dừng lại khi tìm thấy đích. Thuật toán Dijkstra cổ điển tiếp tục truy cập tất cả các nút cho đến khi hàng đợi trống, tìm chi phí đường dẫn tối thiểu từ nút bắt đầu đến mọi nút khác.

Chúng ta hãy xem cách nó hoạt động trên một bản đồ thực sự. Dưới đây là bản đồ của Romania. Hãy nói rằng chúng tôi muốn lái xe từ Arad đến Bucharest trên con đường ngắn nhất.

Chúng ta có thể thấy rằng có nhiều tuyến đường mà chúng ta có thể đi. Chúng ta có thể đi từ Arad đến Timisoara, rồi Lugoj, v.v., hoặc chúng ta có thể chọn Sibiu sau đó là Fagara và đi thẳng tới Bucharest. Nhưng chúng tôi không biết con đường nào có chi phí thấp nhất. Vì vậy, đây là một ứng cử viên tốt cho thuật toán Dijkstra . Chạy triển khai của chúng tôi trên bản đồ Rumani sẽ nhận được điều này:

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

Đó là con đường có chi phí thấp nhất (tin tôi đi, tôi thực sự đến từ Romania và tôi có thể đảm bảo với bạn rằng đây là con đường ngắn nhất). Vì vậy, bằng cách sử dụng thuật toán Dijkstra, chúng tôi có thể tìm thấy đường dẫn với chi phí thấp nhất, nhưng hãy xem có bao nhiêu bước cần thiết để tìm thấy điều này bằng cách in các nút khi truy cập chúng:

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

Vì vậy, chúng ta cần truy cập 13 nút để tìm đường dẫn tốt nhất. Như bạn có thể thấy, từ Arad, chúng tôi đã không đi thẳng đến Sibiu, chúng tôi đã đến đó qua Zerind, rồi Timisoara và sau đó là Sibiu. Và, ngay cả sau đó, chúng tôi đã không đến Rimnicu Valcea, mà đến Oradea, vì đó là nút có chi phí thấp nhất cho đến nay. Đó là cách thuật toán này hoạt động. Mười ba nút truy cập để tìm đường dẫn của chúng tôi và nhiều nút trong số đó không nằm trên đường dẫn với chi phí thấp nhất. Nhưng chúng tôi không biết điều đó và chúng tôi phải đến thăm họ để tìm hiểu.

Đó là tất cả cho Phần 1! Hãy đến abck vào thứ Hai khi chúng tôi đề cập đến cách giải quyết vấn đề này bằng thuật toán A Star [A (*)]

Hữu ích 2 Chia sẻ Viết bình luận 0
Đã xem 9070