intTypePromotion=1

Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:90

0
29
lượt xem
3
download

Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dưới đây là bài giảng Phân tích thiết kế giải thuật: Chương 4 của Trịnh Huy Hoàng. Mời các bạn tham khảo bài giảng để hiểu rõ hơn về phương pháp thiết kế thuật giải như thiết kế thuật toán, phân loại các phương pháp thiết kế thuật toán, các thuật toán chính xác, các thuật toán gần đúng, các bước để thiết kế một thuật giải cho một vấn đề cho trước.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng

  1. Các phương pháp thiết kế thuật giải Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM 1
  2. Nội dung  Thiếtkế thuật toán  Phân loại các phương pháp thiết kế thuật toán  Các thuật toán chính xác  Các thuật toán gần đúng  Các bước để thiết kế một thuật giải cho một vấn đề cho trước 2
  3. Mô hình từ bài toán đến chương trình Thiết kế Lập trình #includ Bài toán  e … thực tế Giải thuật Chương  trình Kỹ  thuật  thiết  kế  giải  thuật: Chia  để  trị,  quy  hoạch  động, … 3
  4. Các bước để giải 1 bài toán trên máy tính  Bước 1: Xác định vấn đề - bài toán  Bước 2: Lựa chọn phương pháp giải  Bước 3: Xây dựng thuật toán hoặc thuật giải  Bước 4: Cài đặt chương trình  Bước 5: Hiệu chỉnh chương trình  Bước 6: Thực hiện chương trình 4
  5. Thiết kế một thuật toán  Cho một vấn đề cần giải quyết  Xác định các bước và trình tự các bước để giải quyết vấn đề đó  Phân tích  thuật toán tốt đến mức nào 5
  6. Phân loại các phương pháp thiết kế thuật toán  Phương pháp chính xác – Bảo đảm nếu thuật toán được thi hành hoàn toàn thi lời giải là chính xác cho vấn đề cần giải quyết – Tuy nhiên  Ràng buộc về thời gian  Ràng buộc về không gian  Ràng buộc về thực tế vấn đề cần giải quyết: chi phí đầu tư, mức độ chấp nhận được của giải pháp  Phương pháp gần đúng – Không bảo đảm thuật toán sẽ chính xác cho tất cả các trường hợp – Sẽ tốt cho một số các trường hợp nào đó – Nhanh, dễ thiết kế 6
  7. Một số các phương pháp thiết kế thuật toán  Tuần tự (vét cạn)  Quay lui (thử và sai)  Chia để trị  Quy hoạch động  Tham lam  Heuristics 7
  8. Phương pháp tuần tự  Tuần tự xét tất cả các khả năng có thể có (vét cạn) cho đến khi gặp giải pháp cho vấn đề cần giải quyết  Ví dụ: giải bài toán cổ sau bài toán cổ – Trăm trâu trăm cỏ – Trâu đứng ăn năm – Trâu nằm ăn ba – Lụ khụ trâu già – Ba con một bó 8
  9. Thuật toán 1  Gọi x là số trâu đứng,y là số trâu nằm, z là số trâu già  x, y, z
  10. Thuật toán 1 for x  0 to 100 do for y  0 to 100 do for z  0 to 300 do if ((5*x+3*y+z/3 = 100) && (x+y+z=100)) then (x, y, z) là giải pháp của bài toán  Nhận xét: ??? 10
  11. Thuật toán 2  Giớihạn lại phạm vi của x, y, z hợp lý hơn  Thuật toán: for x  0 to 100/5 do for y  0 to 100/3 do for z  0 to 300 do if ((5*x+3*y+z/3 = 100) && (x+y+z=100)) then (x, y, z) là giải pháp của bài toán  Nhận xét: ??? 11
  12. Thuật toán 3  Giới hạn tiếp phạm i của x, y, z: – ??? 12
  13. Thiết kế thuật toán theo kiểu tuần tự vét cạn  Dễ thiết kế  Chậm  Tăng tốc thuật toán bằng cách giới hạn miền vét cạn 13
  14. Thiết kế thuật toán theo kiểu quay lui  Thật sự cũng là một phương pháp tuần tự xét hết tất cả các khả năng có thể có  Kết hợp với cơ chế stack và kỹ thuật đệ qui nhằm giúp thuật toán gọn, dễ hiểu 14
  15. Phương pháp quay lui  Ý tưởng: – Giả sử lời giải của bài toán là một bộ – Tại bước thứ i: tìm giải pháp tạm thời cho S i  Tìm khả năng có thể cho thành phần S i.  Nếu có thể chọn một khả năng nào đó làm giải pháp cho Si tạm thời. – Chuyển sang tìm giải pháp cho Si+1.  Nếu không tồn tại một giải pháp tạm thời cho S i thì quay lại bước thứ i-1, loại bỏ giải pháp tạm thời của S i-1, tìm giải pháp khác cho Si-1.  Nếu i=n+1, bộ các giải pháp tạm thời 15 chính là giải pháp của bài toán  Nếu i=0, đã xét tất cả khả năng có thể xảy ra
  16. Phương pháp quay lui – Input: thành phần thứ k cần tìm giải pháp tạm thời – Output: giải pháp tạm thời cho thành phần thứ k Try(i) if (i = n + 1) đã tìm thấy giải pháp else Xét mọi khả năng T có thể của Si Thiết lập T là giải pháp tạm thời cho Si Try(i+1) Khôi phục các trạng thái trước khi chọn T là giải pháp tạm thời Loại bỏ T ra khỏi tập có thể thành giải pháp của Si 16
  17. Phương pháp quay lui  Ví dụ: – Xét tình huống có một ông già mù qua suối. – Bài toán xếp hậu  Chobàn cờ vua (8x8), hai con hậu được gọi là khống chế nhau nếu chúng – cùng nằm trên một dòng, hoặc – cùng nằm trên một cột, hoặc – cùng nằm trên một đường chéo song song đường chéo chính – cùng nằm trên một đường chéo song song đường chéo phụ  Hãy tìm cách xếp tám con hậu lên bàn cờ sao cho không tồn tại hai con hậu bất kỳ nào khống chế nhau. 17
  18. Bài toán 8 hậu – Input: bàn cờ, trạng thái cột, chéo chính, chéo phụ, kích thước và dòng đang xét hiện tại (từ 1) – Output: giải pháp tạm thời cho thành phần thứ k Try(B, C, CC, CP, n, i) if (i = n + 1) đã tìm thấy giải pháp else Xét mọi cột T có khả năng đặt được ở dòng i Thiết lập vị trí của hậu ở dòng i là cột T Try(i+1) Hủy bỏ Thiết lập vị trí của hậu ở dòng i là cột T 18
  19. Cài đặt thuật toán  void QuayLuiHau(MANG2 banco, MANG1 cot, MANGCHEO cheochinh, MANGCHEO cheophu, int kichthuoc, int dongdat)  {  if (dongdat >= kichthuoc)  {  XuatBanCo(banco, kichthuoc);  }  else  {  for (int c = 0; c < kichthuoc; c++)  {  if (DatDuoc(banco, cot, cheochinh, cheophu, kichthuoc, dongdat, c))  {  cot[c] = KHONG_TRONG; cheochinh[dongdat+c] = KHONG_TRONG; cheophu[dongdat-c+kichthuoc] = KHONG_TRONG;  banco[dongdat][c] = 1;  QuayLuiHau(banco, cot, cheochinh, cheophu, kichthuoc, dongdat+1);  cot[c] = CON_TRONG; cheochinh[dongdat+c] = CON_TRONG; cheophu[dongdat-c+kichthuoc] = CON_TRONG;  banco[dongdat][c] = 0;  }  } 19   } }
  20. Phương pháp Chia Và Trị  Một mô hình thiết kế thuật toán có 3 bước: – Chia:  Nếu kích thước dữ liệu đầu vào nhỏ hơn một ngưỡng nào đó thì giải trực tiếp.  Ngược lại chia nhỏ dữ liệu đầu vào thành hai hoặc nhiều tập dữ liệu rời nhau. – Đệ qui:  Giải một cách đệ qui các bài toán con để lấy các lời giải – Trị:  Kết hợp các lời giải của các bài toán con thành lời giải của bài toán ban đầu. 20

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản