Bài toán người đưa thư sử dụng giải thuật Heuristic

1. Phát biểu bài toán:

Bài toán: Để tiết kiệm thời gian đi đưa thư trong một địa phương. Người đưa thư phải đi qua tất cả các điểm cần phát thư rồi trở về vị trí ban đầu với đường đi ngắn nhất.

Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu.

2. Hạn chế khi sử dụng thuật toán tối ưu:

Đồ thị có n đỉnh, khi đó thuật toán tối ưu cho bài toán này sẽ là thuật toán tìm đường đi ngắn nhất cho chu trình Haminton. Do đó thuật toán tối ưu sẽ có độ phức tạp là O(n!).

ĐI TÌM một thuật giải Heuristic cho bài toán này.

3. Sử dụng thuật toán Heuristic cho bài toán người đưa thư:

- Theo kinh nghiệm của con người trong thực tế thì khi ta đi trên những đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất à sử dụng nguyên lý tham lam.

- Thuật giải bài toán sử dụng nguyên lý tham lam:

- Ví dụ về thuật giải trên:

Với một đồ thị trọng số dương như hình bên. Nếu ta xuất phát từ đỉnh sổ 1, thì đỉnh tiếp theo phải đến là 2 (vì cạnh 1-2 có trọng số nhỏ nhất so với các đỉnh chưa đến của 1), như vậy tiếp theo ta sẽ đến các đỉnh theo thứ tự là 5, 3, 4, và trở về 1.

Như vậy đường đi ngắn nhất theo giải thuật trình bày trên tìm được là: 1 + 3 + 2 + 1+ 7 = 14

4. Cài đặt thuật toán.

(ma trận trọng số, kích thước 5x5)

- Ta có dạng ma trận hóa của đồ thị trong ví dụ ở mục 3, như hình bên:

- Input: một ma trận vuông bằng file “graph.txt “ có dạng như hình bên (tài về tại đây), hay nhập ma trận bằng tay.

- Output: đường đi theo thuật giải Heuristic, và chi phí của đường đi đó.

- Tổ chức dữ liệu chương trình: (hình dưới)

Trong đó:

+ n: là biến cho biết số đỉnh của đồ thị.

+ G: dùng để trỏ tới các giá trị của ma trận.

+ v[Gr.n + 1]: dùng để lưu trữ đường đi theo thuật giải Heuristic.

+ Gr.G[ i][j ]: đồ thị dưới dạng ma trận.

+ x: là đỉnh đầu tiên xuất phát.

+ initGraph(Graph &Gr): Hàm dùng để khởi tạo một đồ thị mới từ cấu trúc đã tổ chức.

+ ReadGraph(Graph &Gr): dùng để đọc đồ thị từ file .txt

+ inputHandle( Graph &Gr): dùng để nhập đồ thị bằng tay.

+ outputGraph(Graph Gr): dùng để xuất đồ thị đã được nhập ra màn hình.

+ testGraph(int a, int* v, Graph Gr): Kiểm tra điểm đang duyệt có trùng với điểm đã duyệt trên ma trận không. Được gọi trong hàm topNear(…).

+ topNear(int a, Graph Gr, int* v) : Hàm tìm đỉnh kế tiếp theo thuật giải Heuristic. Được gọi lại trong hàm FindWay(…) .

+ FindWay(int x, Graph Gr, int* v): Hàm tìm đường đi theo giải thuật Heuristic. Dựa theo cách tìm đường đi có trọng số nhỏ nhất để đi bước tiếp theo.

- Giao diện chương trình: console Aplication.

Khi thực thi, chương trình sẽ yêu cầu chọn nhập ma trận đồ thị bằng tay hay bằng file “graph.txt”. Ví dụ như hình trên chọn nhập ma trận bằng file txt. Ta nhập tiếp đỉnh bắt đầu (ở đây nhập 1), thì chương trình sẽ cho ra đáp án cho ví dụ trên:

=> Đường đi là: 1 – 2 – 5 – 3 – 4 – 1

=> Chi phí cho đường đi này theo giải thuật Heuristic là: 14.

Nếu như chọn cách nhập ma trận bằng tay thì ta phải nhập từng giá trị của ma trận vào.

- Nhấn ESC để thoát khỏi chương trình, Phím bất kỳ để tiếp tục chương trình với cách duyệt từ đỉnh khác.[Tài toàn bộ code chương trình - Turbo C++ tại đây]

5. Đánh giá thuật giải Heuristic của bài toán:

* Ưu điểm: Thuật giải Heuristic cho bài toán người đưa thư có độ phức tạp O(n2 ) tốt hơn rất nhiều so với thuật toán tối ưu (có độ phức tạp O( n!) ).

* Nhược điểm: thuật giải có những hạn chế, chưa cho ra lời giải chính xác.

>> Kết luận: Thuật giải Heuristic cho bài toán người đưa thư tuy chưa đưa ra được lời giải chính xác cho bài toán, nhưng nó cho ra một lời giải có thể chấp nhận được với độ phức tạp thấp hơn nhiều so với thuật toán tối ưu.