Bài tập thực hành môn Nhập môn Trí tuệ nhân tạo | Học viện Công Nghệ Bưu Chính Viễn Thông

lOMoAR cPSD| 58800262
H ỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔ NG
  ⚫   ⚫  
B ÀI TẬP THỰC HÀNH BUỔI 1 Mã môn học:
Giảng Viên: Đinh Chí Hiếu
Họ và Tên: Trịnh Phi Hùng
Mã Sinh Viên: B21DCTC048 lOMoAR cPSD| 58800262 Start node: S End node: G 1. Giải bằng tay
2. Tìm kiếm theo chiều rộng a. Chương trình Python
b. Chụp ảnh màn hình kết quả
3. Vẽ ồ thị trên bằng NetworkX Câu 1: lOMoAR cPSD| 58800262
Các bước giải bài toán theo phương pháp tìm kiếm theo chiều rộng:
Bước 1: Bắt ầu từ iểm S, thêm iểm S vào hàng ợi Hàng ợi: [S] Đã duyệt: []
Bước 2: Duyệt iểm S và ánh dấu iểm S, tìm các iểm liền với S và cho vào hàng ợi:
Các iểm liền với S: A,B Hàng ợi:[A,B] Đã duyệt: [S]
Bước 3: Duyệt iểm A và ánh dấu iểm A, tìm các iểm liền với A và cho vào hàng ợi:
Các iểm liền với A: C,D,G Hàng ợi: [B,C,D,G] Đã duyệt: [S,A]
Bước 4: Duyệt iểm B và ánh dấu iểm B, tìm các iểm liền với B và cho vào hàng ợi: Các iểm liền với B: C Hàng ợi: [C,D,G] Đã duyệt: [S,A,B]
Bước 5: Duyệt iểm C và ánh dấu iểm C, tìm các iểm liền với C và cho vào hàng ợi: Các iểm liền với C: G Hàng ợi: [D,G] Đã duyệt: [S,A,B,C]
Bước 6 Duyệt iểm D và ánh dấu iểm D, tìm các iểm liền với D và cho vào hàng ợi: Các iểm liền với D: G Hàng ợi: [G] Đã duyệt: [S,A,B,C,D]
Bước 7: Duyệt iểm G và ánh dấu iểm G, kết thúc giải thuật: lOMoAR cPSD| 58800262 Hàng ợi:[] Đã duyệt:[S,A,B,C,D,G,]
Đường ngắn nhất ể i từ S ến G là S->A->G, ường i này tìm ược khi G ược thêm vào hàng ợi ở bước 3. Câu 2:
Đoạn code tìm kiếm theo chiều rộng Tạo graph:
Tạo hàm tìm kiếm theo chiều rộng: lOMoAR cPSD| 58800262 In kết quả Kết quả lOMoAR cPSD| 58800262 Câu 3: Tạo Graph lOMoAR cPSD| 58800262 Vẽ biểu ồ: lOMoAR cPSD| 58800262 Kết quả