Bài toán dđồ thị xe buýt trong c++ năm 2024

Question

Thuật toán tìm đường có nhiều loại lắm, bạn nói cụ thể hơn trường hợp bạn muốn đi, mà nói chung thì đây là một thuật toán khá khó và không dể hình dung khi xem code, nếu tìm hiểu lý thuyết thì sẽ dể dàng hơn. Thuật toán tìm điển hình có thể nói đến Dijkstra, A*

Tìm đường đi ngắn nhất từ một nút tới tất cả các node còn lại. - Thuật toán Dijkstra :

Gán tập giá trị set = trống,
Kiểm tra khoảng cách từ nut s tới các nut còn lại (khoảng cách(s, s) = 0, khoảng cách (s, t) = x)
Lặp lại cho đến khi tất cả các nút được đưa vào tập set
Tìm ra một nút d với khoảng cách tới s là ngắn nhất
Đưa d vào tập set
Cập nhật khoảng cách từ s tới tất cả các nút khác sử dụng:
Nếu distance(s, m) > distance(s, d) + dist(d, m) 8/ thì distance(s, m) = distance(s, d) + dist (d, m)

Thuật toán trên thể hiện trên java

Mã:

//
//   This file contains the Java code from Program 16.15 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in Java"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus5/programs/pgm16_15.txt
//
public class Algorithms
{
    public static Digraph DijkstrasAlgorithm (Digraph g, int s)
    {
    int n = g.getNumberOfVertices ();
    Entry[] table = new Entry [n];
    for (int v = 0; v < n; ++v)
        table [v] = new Entry ();
    table [s].distance = 0;
    PriorityQueue queue =
        new BinaryHeap (g.getNumberOfEdges());
    queue.enqueue (
        new Association (new Int (0), g.getVertex (s)));
    while (!queue.isEmpty ())
    {
        Association assoc = (Association) queue.dequeueMin();
        Vertex v0 = (Vertex) assoc.getValue ();
        int n0 = v0.getNumber ();
        if (!table [n0].known)
        {
        table [n0].known = true;
        Enumeration p = v0.getEmanatingEdges ();
        while (p.hasMoreElements ())
        {
            Edge edge = (Edge) p.nextElement ();
            Vertex v1 = edge.getMate (v0);
            int n1 = v1.getNumber ();
            Int wt = (Int) edge.getWeight ();
            int d = table [n0].distance + wt.intValue ();
            if (table [n1].distance > d)
            {   table [n1].distance = d;
            table [n1].predecessor = n0;
            queue.enqueue (
                new Association (new Int (d), v1));
            }
        }
        }
    }
    Digraph result = new DigraphAsLists (n);
    for (int v = 0; v < n; ++v)
        result.addVertex (v, new Int (table [v].distance));
    for (int v = 0; v < n; ++v)
        if (v != s)
        result.addEdge (v, table [v].predecessor);
    return result;
    }
}

Đây là 1 bài về tìm đường bên gamedev.vn bạn có thể tham khảo: A* là chiến lược tìm kiếm được dùng rất nhiều ở các Game, kiến thức thức về A* có thể nói là một kiến thức thuộc loại MUST HAVE với bất kì ai lập trình AI cho Game. Sách vở viết về A* bạn có thể tìm dễ dàng ở nhà sách. Đồng thời nếu bạn muốn tìm hiểu thì có thể đọc cái này

CÁC GIẢI THUẬT TÌM KIẾM HEURISTIC Không gian tìm kiếm là một đồ thị trạng thái Tìm hành trình ngắn nhất: xác định bởi việc cực tiểu hóa giá thành bằng giải thuật AT Tìm kiếm với tri thức bổ sung: hướng tìm kiếm được xác định bằng tri thức bổ sung sau mỗi bước đi bằng giải thuật AKT

Giải thuật AT (Algorthm of Tree)

Trong không gian tìm kiếm, mỗi đỉnh n tương ứng với môt số g(n) giá thành đi từ đỉnh ban đầu đến đỉnh n. Đỉnh đóng là những đỉnh đã được xét Đỉnh mở là những đỉnh sẽ được xét Gọi OPEN là tập chứa những đỉnh mở Đỉnh đầu tiên x0 có g(0) = 0, đưa x0 vào OPEN Lặp lại cho đến khi tới đích hoặc tập OPEN=NULL Chọn đỉnh đến là đỉnh có g nhỏ nhất, gọi nó là đỉnh xmax ta có OPEN = OPEN - xmax Nếu xmax là đỉnh đích thì kết thúc Ngược lại, với mọi xi kề xmax Tính g(xi) = g(xmax) + cost(xmax,xi) Chọn xi là đỉnh đến có g(xi) nhỏ nhất Thêm xi vào OPEN

Giải thuật AKT (Algorthm of Knowledgeable Tree)

Gọi là thuật toán tìm kiếm với tri thức bổ sung. Tri thức bổ sung là gì ? Giả sử bạn cần đến Hà Nội, mà bạn có 2 con đường cùng có thể đi đến đó. Một là đến Hải Phòng, sau đó sẽ tới Hà Nội. Hai là đến Vinh, sau đó sẽ ra Hà Nội. Vấn đề là bạn chọn đường nào ? Bạn có một tri thức bổ sung là đường từ Hải Phòng ra Hà Nội sẽ ngắn hơn đường từ Vinh ra Hà Nội, nên bạn chọn đường ra Hải Phòng. Ở ví dụ trên đây, rõ ràng tri thức “đường từ Hải Phòng ra Hà Nội sẽ ngắn hơn đường từ Vinh ra Hà Nội” là một tri thức phỏng đoán rút tỉa từ kinh nghiệm (nếu bạn là người nước ngoài chưa đến Việt Nam bao giờ chẳng hạn bạn sẽ không có tri thức này) Thuật toán AKT cũng vậy. Dựa vào các tri thức kinh nghiệm bổ sung, xây dựng cá hàm ước lượng, để cùng giá thành quyết định đường đi cho chính xác Trong không gian tìm kiếm, mỗi đỉnh n tương ứng với môt số g(n) giá thành đi từ đỉnh ban đầu đến đỉnh n và một giá trị h(n) biểu hiện sự ước lượng của chúng ta giá thành để đi từ n đến đích. Như vậy tổng chi phí của một đỉnh sẽ là f(n) = g(n) + h(n) Chọn đỉnh đến là đỉnh có f nhỏ nhất, gọi nó là đỉnh xmax ta có OPEN = OPEN - xmax Nếu xmax là đỉnh đích thì kết thúc Ngược lại, với mọi xi kề xmax Tính g(xi) = g(xmax) + cost(xmax,xi) Tính h(xi) và tính f(xi) = g(xi) + h(xi) Chọn xi là đỉnh đến có f(xi) nhỏ nhất Thêm xi vào OPEN

Giải thuật A*

Đây là giải thuật cải tiến giải thuật AKT Đỉnh đóng là những đỉnh đã được xét A* sử dụng thêm tập CLOSE để lưu những đỉnh đã được xét Khi xét đến một nút nào đó, ngoài f, g, h thì A* còn quan tâm đến Danh sách các nút dẫn đến nút xi gọi là Cha(xi) Danh sách các nút kế tiếp nút xi Ví dụ 1 đồ thị như sau (gửi kèm bên dưới) Khoảng cách tính theo đường chim bay từ 1 đỉnh bất kì đến đỉnh B như sau:

A 366 B 0 C 160 D 242 E 161 F 178 G 77 H 151 I 226 L 244 M 241 N 234 O 380 P 98 R 193 S 253 T 329 U 80 V 199 Z 374

Bây giờ ta thử tìm đường đi ngắn nhất từ A đến B

B1:

OPEN = {A} CLOSE = {} A(g=0,h=0,f=0) B2: OPEN = {} CLOSE = {A} A(g=0,h=366,f=366) Từ A ta có 3 điểm có thể đi được là S,T,Z. Ta đi tính g,h,f của 3 điểm này h(S) = 253 g(S) = g(A) + cost(A,S) = 0 + 140 = 140 f(S) = g(S) + h(S) = 140 + 253 = 393 Cha(S) = A h(T) = 329 g(T) = g(A) + cost(A,T) = 0 + 118 = 118 f(T) = g(T) + h(T) = 118 + 329 = 447 Cha(T) = A h(Z) = 374 g(Z) = g(A) + cost(A,Z) = 0 + 75 = 75 f(Z) = g(Z) + h(Z) = 374 + 75 = 449 Cha(Z) = A OPEN = {S,T,Z} CLOSE = {A} Chọn xmax = S, loại xmax khỏi OPEN OPEN = {T,Z} CLOSE = {A,S} B3: Từ S ta có 4 điểm có thể đi được là A,F,O,R. Ta đi tính g,h,f của 4 điểm này A(h=366,g=280,f=646,cha=S) g(A) mới = 280 > g(A) cũ = 0 nên không cần cập nhật lại giá trị của g và f của A trong CLOSE (Nếu g(A) mới < g(A) cũ thì cần cập nhật lại giá trị của g và f của A trong CLOSE) F(h=178,g=239,f=417,cha=S) O(h=380,g=291,f=671,cha=S) R(193,220,413,cha=S) OPEN = {T,Z,F,O,R} CLOSE = {A(0,0,0),S} Tương tự như vậy ta được đường đi ngắn nhất A→S→R→P→B Dựa vào thông tin cha(xi) đã lưu trữ cho xi ta lần ngược để tìm đường đi tối ưu và luôn nhớ cập nhật lại g,f nếu giá trị mới nhỏ hơn giá trị cũ.

Vậy thì để bắt đầu chúng ta cần phải tổng hợp dữ liệu từ các file của BNTT. Vậy ai có thể bắt tay vào tham gia nào ? Vbavn

mẹo hay