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:
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.
Đồ 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:
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)
- Chương trình được viết trên môi trường Turbo C++ 3.0.
- 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(…).
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.
>>> Tải code chương trình tại đây.
Lưu ý:
- Sau 5s, click BỎ QUA QUẢNG CÁO (SKIP AD)
- File grapt.txt đặt tại cùng thư mục với code chương trình.
Nguồn: thanhcuong