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


Dương Thu Hoài
8 tháng trước
Hữu ích 3 Chia sẻ Viết bình luận 0
Đã xem 10524

Chào mừng trở lại! Nếu bạn bỏ lỡ Phần 1 trên Thuật toán Dijkstra, bạn có thể kiểm tra nó ở đây .

A * Thuật toán

Có thể có một cách mà bằng cách sử dụng một số manh mối, chúng ta có thể đi thẳng đến đích và không truy cập các nút không cần thiết khác? Vâng, nếu chúng ta có một số ước tính, thì có, có. Nếu mọi nút đều biết điểm đến của con đường ngắn nhất là bao xa, chúng ta có thể sử dụng thông tin bổ sung này, ước tính này, để tìm đường Road của chúng tôi nhanh hơn. Chúng tôi gọi đây là một heuristic.

Sử dụng heuristic chúng ta có thể xây dựng một hàm,  f (n) , đưa ra ước tính tổng chi phí đường dẫn từ nút bắt đầu đến đích, nếu nút hiện tại, n, nằm trên đường dẫn. Chúng tôi định nghĩa nó như thế này:

f (n) = g (n) + h (n)

Ở đâu:

  • f (n)  = tổng chi phí đường dẫn ước tính thông qua nút  n
  • g (n) = tổng chi phí đường dẫn từ đầu đến  n
  • h (n) = chi phí ước tính từ  n  đến mục tiêu. Các heuristic.

Chúng ta đã có thể tính  g (n) , tổng chi phí từ đầu đến  n , bằng   thuật toán Dijkstra , vì vậy, nếu chúng ta biết  h (n) , chúng ta có thể nhận được  f (n) , chi phí ước tính của đường dẫn qua nút  n . Trong trường hợp đó, chúng ta có thể thay đổi   thuật toán Dijkstra để sử dụng hàm mới này khi nhận được nút tiếp theo để truy cập từ biên giới. Đây là  A * .

A * thực sự là một biến thể được thông báo của  Dijkstra , trong đó chúng tôi sử dụng chi phí ước tính của đường dẫn qua nút n, hàm  f (n)  , để chọn nút tiếp theo để truy cập. Có một heuristic tốt có thể giúp chúng ta tránh truy cập các nút không cần thiết. Giống như có một gợi ý mà ai đó nói với chúng tôi, sử dụng cách này, nhanh hơn. Vì vậy, trước tiên chúng tôi đi theo cách đó và nếu gợi ý đó tốt, chúng tôi sẽ đạt được mục tiêu nhanh hơn.

Hãy thay đổi cách thực hiện trước đây của chúng tôi. Chúng tôi muốn sử dụng hàm heuristic khi chọn nút tiếp theo để truy cập từ biên giới, do đó chuyển đổi nó trong  A *. Các  cạnh  đối tượng sẽ giống nhau. Nó sẽ có một nút mục tiêu và một chi phí liên quan đến nó. Không có gì thay đổi ở đây. Trong  Node lớp, chúng tôi sẽ thêm hai trường mới:  h_cost và  f_cost.

static class Node{

  public final String name;

  // cost so far to reach destination
  public double g_cost = Integer.MAX_VALUE;
  // total estimated cost of path through current node
  public double f_cost = Integer.MAX_VALUE;
  // estimated cost from this node to destination
  public final double h_cost;

  public List<Edge> adjacency = new ArrayList<>();
  public Node parent;

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

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

  public String toString(){
    return name;
  }
}

Các  h_cost sẽ được khởi tạo bởi các nhà xây dựng. Đó là chi phí ước tính cho nút mục tiêu mà chúng tôi cần cung cấp. Các  f_cost sẽ được tính theo công  Một * thuật toán dựa trên  g_cost và  h_cost, và chúng tôi sẽ sử dụng nó để chọn nút bên cạnh đến thăm. Hãy xem cách làm:

public static void AStarSearch(Node source, Node destination) {
  source.g_cost = 0;
  // total estimated cost of path through current node will be in this case equal to h_cost
  source.f_cost = source.h_cost;

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

  frontier.add(source);

  int numberOfSteps = 0;
  while (!frontier.isEmpty()) {
    numberOfSteps++;
    // get the node with minimum distance
    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 new_g_cost = current.g_cost + cost;
      double new_f_cost = neigh.h_cost + new_g_cost;

      if (new_f_cost < neigh.f_cost) {
        neigh.parent = current;
        neigh.g_cost = new_g_cost;
        neigh.f_cost = new_f_cost;

        if (frontier.contains(neigh)) {
          frontier.remove(neigh);
        }

        frontier.add(neigh);
      }
    }
  }

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

Vì vậy, nếu nhìn kỹ chúng ta sẽ thấy ba điểm khác biệt so với thuật toán trước:

  • Các  PriorityQueue sẽ so sánh các nút dựa trên  f_cost.
  • Chúng ta phải tính toán một cái mới  f_cost dựa trên chi phí ước tính hiện tại và cái mới  g_cost.
  • Chúng tôi cập nhật đường dẫn tốt nhất cho đến nay, nếu cái mới  f_cost thấp hơn hiện tại  f_cost.

Đây là những khác biệt duy nhất. Tất cả những thứ khác vẫn giữ nguyên. Vì vậy, hãy xem cách nó hoạt động. Chúng tôi sẽ quay trở lại bản đồ Rumani của chúng tôi, nhưng lần này chúng tôi thêm một số thông tin heuristic vào mỗi nút để có được ước tính về thời gian cần thiết để đi từ mỗi thành phố đến Bucharest.

Ước tính không cần phải hoàn hảo, xét cho cùng, chỉ là ước tính. Tất nhiên, điều quan trọng là càng gần với giá trị thực càng tốt, nhưng khía cạnh quan trọng ở đây là không đánh giá quá cao và tôi sẽ giải thích cho bạn tại sao muộn hơn một chút. Ví dụ, nhìn vào nút Pitesti. Chi phí thực tế từ Pitesti đến Bucharest là 101, nhưng giá trị ước tính là 100. Điều này sẽ hoạt động. Hãy chạy chương trình của chúng tôi trên bản đồ này và xem những gì chúng tôi nhận được.

Current node: Arad
Current node: Sibiu
Current node: Rimnicu Vilcea
Current node: Fagaras
Current node: Pitesti
Current node: Bucharest
Number of steps: 6
Path: [Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest]

Hiệu quả rõ ràng. Chúng tôi có đường dẫn chỉ với 6 bước, thay vì 13 bước cần thiết cho thuật toán Dijkstra. Nhanh hơn hai lần. Đó là một cải tiến lớn. (Trên thực tế, điều này không có nghĩa là A * nhanh hơn Dijkstra hai lần. Việc tối ưu hóa phụ thuộc vào độ chính xác của ước tính).

Vậy tại sao điều này làm việc tốt hơn? Làm thế nào chúng ta đã đi gần như thẳng đến Bucharest từ Arad, chỉ với một ngoại lệ, Fagara, và tại sao chúng ta không kiểm tra các nút khác? Chúng ta không thể bỏ lỡ một con đường khác và / hoặc tốt hơn nếu chúng ta không truy cập nó? Vâng, điều này là do chúng tôi chọn nút tiếp theo sẽ được truy cập dựa trên  f_cost, đó là:

f_cost = h_cost + g_cost

Và, như tôi đã nói trước đây, giá trị heuristic không nên được đánh giá quá cao, điều đó có nghĩa là chức năng heuristic nên được chấp nhận. Các  h_cost nên luôn luôn nhỏ hơn hoặc bằng với khoảng cách thực sự. Tại sao? Vâng, thuật toán của chúng tôi chọn nút tiếp theo để truy cập dựa trên giá trị ước tính và nó sẽ chọn nút có giá trị thấp nhất  f_cost.

Chúng ta hãy xem một ví dụ đơn giản trong đó  h_cost chi phí lớn hơn chi phí thực và xem điều gì sẽ xảy ra nếu heuristic không được chấp nhận.

Trong biểu đồ này, chúng ta thấy rằng chi phí ước tính từ  C  đến  D  là 150 và chi phí thực là 100. Nếu chúng ta chạy thuật toán của mình trên biểu đồ này, chúng ta sẽ thấy rằng nó tính toán con đường ngắn nhất này, A -> B -> D, với tổng chi phí là 220. Nhưng như bạn thấy, đường dẫn có chi phí thấp nhất là A -> C -> D, với tổng chi phí là 200.

Vậy tại sao  A * không  tìm thấy con đường đúng? Bởi vì nó dựa vào thực tế là ước tính luôn nhỏ hơn hoặc bằng giá trị thực. Vì vậy, nếu khi chọn một nút để truy cập, thuật toán sẽ thấy rằng ước tính cao hơn giá trị ước tính của nút khác, tại sao nó phải chọn nút đầu tiên? Nó sẽ đi với nút thứ hai, bởi vì, theo điều kiện có thể chấp nhận, giá trị thực không thể thấp hơn giá trị ước tính, vì vậy nó sẽ không kiểm tra nút đó. Do đó, nếu các ước tính không tôn trọng điều kiện được chấp nhận, thuật toán này sẽ không hoạt động đúng.

Nhưng, nếu các heuristic được chấp nhận, thuật toán sẽ hoạt động nhanh hơn  thuật toán Dijkstra cổ điển  , bởi vì, nó sẽ chỉ kiểm tra các nút có mức thấp nhất  f_costvà thực tế là  f_cost  không thể cao hơn chi phí đường dẫn thực, chúng tôi có thể chắc chắn rằng chúng ta sẽ không bỏ lỡ một con đường tốt hơn. Đó là lý do tại sao chúng ta thấy rằng, khi đi qua bản đồ Rumani, nó sẽ đi từ Arad đến Sibiu, Rm Valcea, mà không kiểm tra Oradea hoặc Timisoara.

Như bạn thấy, thuật toán cũng sẽ kiểm tra Fagara, không phải là con đường ngắn nhất, nhưng thuật toán chưa biết điều đó. Đó là bởi vì, sau khi nó truy cập nút Rm Valcea, nút Fagara có giá trị  f_cost tương đương với 415 ( g_cost = 239,  h_cost = 176) và Pitesti có giá trị  f_cost tương đương với 417 ( g_cost = 317 +  h_cost = 100). Vì vậy, nó sẽ chọn đến thăm Fagara có chi phí ước tính thấp hơn. Sau khi nó truy cập nó, nó sẽ thấy rằng tổng chi phí từ Arad đến Bucharest thông qua Fagara là 450, trong khi Pitesti có giá trị  f_cost tương đương với 415, vì vậy nó sẽ đi đến Pitesti, và nó sẽ tiếp tục đến Bucarawa, tìm ra con đường ngắn nhất.

Phần kết luận

Vì vậy, trong loạt bài viết này, chúng ta đã thấy  thuật toán Dijkstra hoạt động như thế nào  để giúp chúng ta tìm ra con đường ngắn nhất từ ​​nút này sang nút khác. Tuy nhiên, thuật toán này còn một số chỗ cần cải thiện, vì vậy nếu chúng ta có một số chi phí ước tính từ mỗi nút đến đích, chúng ta có thể tìm thấy con đường ngắn nhất nhanh hơn nhiều. Và đây là cách chúng tôi chuyển đổi   thuật toán Dijkstra thành thuật toán A star  (A *).

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