[ C\C++ ] Bài toán người đưa thư sử dụng giải thuật Heuristic [ Giải thuật - Trí tuệ nhân tạo ]

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:

- 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(…).


  + 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.

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

Quảng cáo

Загрузка...

Categories

8051 (1) AI (1) AI programming (1) amazon (1) Android (27) ASP (1) Assembly (17) Bài giảng (2) Bài giảng lập trình C và Cpp (16) bài giảng quản lý dự án CNTT (1) bài tập java (1) bài tập lập trình (1) Bài viết hay (62) Bản đồ tư duy (1) Bidvertiser (1) Biểu diễn thuật toán (1) bitcoin (1) blockchain (1) Blockchain là gì (1) Bubble-Sort (1) C (77) C Plus Plus (103) C sharp (11) C++ (3) cấu trúc dữ liệu giải thuật (1) Cây (tree) (2) Cây quyết định (3) CDSL phân tán (1) Chữa bài tập Java (1) code assembly (1) Công nghệ điện toán đám mây (1) Công nghệ lập trình (1) Cơ sở dữ liệu (10) CSS (2) Cuộc cách mạng công nghiệp 4.0 (1) Danh ngôn lập trình (1) Danh sách liên kết (list) (1) Datamining (4) Đại số gia tử và ứng dụng (1) đăng ký Amazon (1) Đăng ký hosting (2) đặt hàng trên Amazon (1) Đệ quy (2) Đồ họa (4) Độ phức tạp của thuật toán (1) ebook-csdl (1) ebook-giaithuat (1) ebook-laptrinh (1) ebook-phancung-mang (1) ebook-tinhocungdung (1) ebook-web (1) Exceptions (1) Genetic Algorithm (1) Giải hệ phương trình tuyến tính (5) giải thuật (3) giải thuật Đệ quy (1) Giáo trình (2) Góc học tập (34) Góc suy ngẫm (1) Google App Engine (2) Heap-Sort (1) Hệ quản trị CSDL (1) Học lập trình (125) Học lập trình C và CPP qua ví dụ (15) học lập trình Java (7) HostGator (1) hợp ngữ (1) HPH (25) HTML (1) Hướng Dẫn Đăng Ký Tên Miền và Host Trên Hostgator (1) hướng dẫn mua host (1) hướng dẫn nhận tiền (1) hướng dẫn payoneer (1) Hướng dẫn sử dụng Emu8086 (1) hướng dẫn viết báo (1) hướng đăng ký tên miền (1) Insert-sort (2) iOS (1) Java (50) Java Căn bản (5) java core (3) Java GUI (1) JavaScript (3) Kiếm tiền online (10) Kỹ thuật đồ họa máy tính (9) Kỹ thuật lập trình (16) kỹ thuật SEO (1) Lập trình 8051 với C/C++ (1) Lập trình căn bản (7) Lập trình Cơ sở dữ liệu (2) Lập trình điều khiển thiết bị (1) Lập trình hợp ngữ (1) Lập trình hướng đối tượng (38) Lập trình hướng đối tượng với Java (6) Lập trình mạng (6) Lập trình mobile (3) Lập trình nhúng (1) Lập trình trí tuệ nhân tạo (1) lập trình vi xử lý (1) lập trình viên (1) Lập trình viên độc lập (1) Luyện thi IC3 (4) Lý thuyết Cơ sở dữ liệu (2) Lý thuyết đồ thị (11) Mạng máy tính (1) Mẹo tìm kiếm trên Google (1) Merge-Sort (1) MS Access (1) Mua hàng trên Amazon (1) Nghiên cứu khoa học (1) ngon-ngu-khac (1) Ngôn ngữ lập trình (1) Nhúng code Assembly trong C\C++ (2) Những lỗi thường gặp khi lập trình (1) Oracle (1) Pascal (3) payoneer (1) people-group (1) phần cứng máy tính (1) PHP (1) Quản lý dự án CNTT (1) Queue (hàng đợi) (1) Quick-Sort (1) Seclection-sort (2) SEO (1) SQL (5) Stack (ngăn xếp) (1) Swift (8) tài liệu CNTT miễn phí (2) Tài liệu tham khảo (2) thanh toán quốc tế (1) Thiết kế Web (2) Thủ thuật máy tính (5) thuattoan-khac (1) Thuật toán (41) Thuật toán di truyền (2) Thuật toán Đệ quy (4) Thuật toán K-Mean (1) Thuật toán khác (9) Thuật toán leo đồi (1) Thuật toán ma trận (7) Thuật toán Sắp Xếp -Sort (9) Thuật toán Tìm kiếm - Search (5) Thương mại điện tử (4) Tiện ích máy tính (3) Tìm hiểu Blockchain (1) Tìm kiếm nhị phân (2) Tìm kiếm tuần tự (Line search) (2) Tin học văn phòng (5) Tin tức công nghệ (7) Tính định thức của ma trận (1) Toán rời rạc (12) Trí tuệ nhân tạo (8) Tự học lập trình Android (14) Tự học lập trình C và CPP (14) tự học lập trình iOS (8) Tự học lập trình java qua các ví dụ (7) Ứng dụng cơ sở dữ liệu (1) VB (2) vẽ ngôi nhà (1) ví dụ Assembly (1) xcode (8) XML (1) Xử lý ma trận (mảng 2 chiều) (7) Xử lý mảng 1 chiều (1) Xử lý ngoại lệ (1)