Báo cáo Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo

danh sách có th ể  h ướ ng t ớ i ti ế p theo. Có  thể  s ử  d ụ ng thu ậ t toán tìm ki ế m theo chi ề u r ộ ng cho hai m ụ c đích: tìm ki ế m  đường đi t ừộỉố  m t đ nh g c cho tr ướớộỉ c t i m t đ nh đích, và tìm ki ếườ m đ ng đi t ừ   đỉốớấảỉnh g c t i t t c  các đ nh khác. Trong đ ồị th  không có tr ọốậ ng s , thu t toán tìm  kiế m theo chi ề u r ộ ng luôn tìm ra đ ường đi ng ắ n nh ấ t có th ể . Thu ậ t toán BFS  bắầừỉố t đ u t  đ nh g c và l ầượ n l t nhìn các đ ỉềớỉốnh k  v i đ nh g c. Sau đó, v ớỗ i m i  đỉnh trong s ố  đó, thu ậ t toán l ạầượ i l n l t nhìn tr ướ c các đ ỉềớnh k  v i nó mà ch ư a  được quan sát tr ướ c đó và l ặ p l ạ i. Xem thêm thu ậ t toán tìm ki ế m theo chi ề u sâu,  trong đó cũng sử  d ụ ng 2 thao tác trên nh ư ng có trình t ự  quan sát các đ ỉnh khác  vớ i thu ậ t toán tìm ki ế m theo chi ề u r ộ ng.  giảậ i thu t tìm ki ế m theo chi ềộệừớớớ u r ng duy t t  A t i B t i E t i F sau đó t ớ i C,  tớ i G và cu ố i cùng t ớ i D. Gi ả i thu ậ t này tuân theo qui t ắ c: Qui tắ c 1: Duyệếớỉềề t ti p t i đ nh li n k  mà ch ưượ a đ c duy ệ t. Đánh d ấ u  đỉnh mà đã đ ược duy ệ t. Hi ể n th ị  đ ỉnh đó và đ ẩy vào trong m ộ t hàng đ ợi (queue).. Qui tắ c 2: Nế u không tìm th ấ y đ ỉnh li ề n k ề , thì xóa đ ỉnh đ ầu tiên trong  hàng đợi. Qui tắ c 3: Lặ p l ạ i Qui t ắ c 1 và 2 cho t ớ i khi hàng đ ợi là tr ố ng. Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Ứng d ụ ng: Thuậ t toán tìm ki ế m theo chi ề u r ộ ng đ ược dùng đ ể gi ả i nhi ề u bài toán trong lý  thuyế t đ ồ th ị , ch ẳ ng h ạ n nh ư : Tìm tấ t c ả  các đ ỉnh trong m ộ t thành ph ầ n liên thông Tìm đường đi ng ắ n nh ấ t gi ữ a hai đ ỉnh u và v (v ớ i chi ề u dài đ ường đi tính  bằ ng s ố  cung) Kiể m tra xem m ộ t đ ồ th ị  có là đ ồ th ị  hai phía Tìm các thành phầ n liên thông Ưu đi ể m: Xét duyệ t t ấ t c ả  các đ ỉnh đ ể tr ả  v ề  k ế t qu ả . Nế u s ố  đ ỉnh là h ữ u h ạ n, thu ậ t toán ch ắ c ch ắ n tìm ra k ế t qu ả . Nhượ c đi ể m: Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Mang tính chấ t vét c ạ n, không nên áp d ụ ng n ế u duy ệ t s ố  đ ỉnh quá  lớ n. Mang tính chấ t mù quáng, duy ệ t t ấ t c ả  đ ỉnh, không chú ý đ ến thông  tin trong các đỉnh đ ể duy ệ t hi ệ u qu ả , d ẫ n đ ến duy ệ t qua các đ ỉnh  không cầ n thi ế t. 2. Tìm kiế m theo chi ề u sâu. Giả i thu ậ t tìm ki ế m theo chi ề u sâu (Depth First Search – vi ế t t ắ t là DFS), còn  đượọảậc g i là gi i thu t tìm ki ếư m  u tiên chi ề u sâu, là gi ảậệặ i thu t duy t ho c tìm  kiế m trên m ộ t cây ho ặộồịửụ c m t đ  th  và s  d ng stack (ngăn x ếể p) đ  ghi nh ớỉ  đ nh  liềềểắầệ n k  đ  b t đ u vi c tìm ki ế m khi không g ặượỉềề p đ c đ nh li n k  trong b ấỳ t k   vòng lặ p nào. Gi ảậếụ i thu t ti p t c cho t ớ i khi g ặượỉầ p đ c đ nh c n tìm ho ặớ c t i  mộ t nút không có con. Khi đó gi ả i thu ậ t quay lui v ề  đ ỉnh v ừ a m ớ i tìm ki ế m  ở   bướ c tr ướ c. Trong hình minh họ a trên, gi ả i thu ậ t tìm ki ế m theo chi ề u sâu đ ầu tiên duy ệ t t ừ  các đỉnh A tớ i B tớ i C tớ i D sau đó tớ i E, sau đó tớ i F và cuố i cùng t ớ i G. Giả i  thuậ t này tuân theo qui t ắ c sau: Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Qui tắ c 1: Duyệếớỉềề t ti p t i đ nh li n k  mà ch ưượ a đ c duy ệ t. Đánh d ấ u  đỉnh mà đã đ ược duy ệ t. Hi ể n th ị  đ ỉnh đó và đ ẩy vào trong m ộ t ngăn x ế p (stack). Qui tắ c 2: Nế u không tìm th ấ y đ ỉnh li ề n k ề , thì l ấ y m ộ t đ ỉnh t ừ  trong  ngăn xế p (thao tác pop up). (Gi ả i thu ậ t s ẽ  l ấ y t ấ t c ả  các đ ỉnh t ừ  trong ngăn x ế p  mà không có các đỉnh li ề n k ề  nào) Qui tắ c 3: Lặ p l ạ i các qui t ắ c 1 và qui t ắ c 2 cho t ớ i khi ngăn x ế p là tr ố ng. Ưu đi ể m: Xét duyệ t t ấ t c ả  các đ ỉnhđ ể tr ả  v ề  k ế t qu ả . Nế u s ố  đ ỉnh là h ữ u h ạ n, thu ậ t toán ch ắ c ch ắ n tìm ra k ế t qu ả . Nhượ c đi ể m: Mang tính chấ t vét c ạ n, không nên áp d ụ ng n ế u duy ệ t s ố  đ ỉnh quá l ớ n. Mang tính chấ t mù quáng, duy ệ t t ấ t c ả  đ ỉnh, không chú ý đ ến thông tin  trong các đỉnh đ ể duy ệ t hi ệ u qu ả , d ẫ n đ ến duy ệ t qua các đ ỉnh không c ầ n  thiế t. 3. Tìm kiế m theo chi ề u sâu có gi ớ i h ạ n. Trong trí tuệ  nhân t ạ o hay các lý thuy ế t đ ồ th ị , thu ậ t toán tìm ki ế m có gi ớ i h ạ n  độ sâu (DLS)  hay depth­limited search algorithm là mộ t thu ậ t toán phát tri ể n các  nút chư a xét các theo chi ề u sâu nh ư ng có gi ớ i h ạ n m ứ c đ ể tránh đi vào nh ữ ng  con đường không mang l ạ i k ế t qu ả  t ố t nh ư  trong thu ậ t toán tìm ki ế m sâu d ầ n. Ưu đi ể m:  Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Nó là bộ  nh ớ  hi ệ u qu ả , s ử  d ụ ng không gian tuy ế n tính O (bxL) Nhượ c đi ể m: Chư a hoàn thành n ế u gi ả i pháp n ằ m d ướ i gi ớ i h ạ n L(d <l), vì nó  không thể  tìm th ấ y Solution. Nó có thể  không tìm th ấ y t ố i  ư u n ế u có nhi ề u h ơ n Solution. Nó không hiệ u qu ả  v ề  th ờ i gian vì ph ả i m ấ t O (b ^ L). Nó có thể  gây ra các vòng l ặ p n ế u tìm ki ế m cây đ ược s ử  d ụ ng trên  biể u đ ồ. 4. Tìm kiế m theo giá thành th ố ng nh ấ t. Hàng đợưi  u tiên PQ là c ấ u trúc d ữệưữ  li u l u tr  các ph ầử n t  cùng v ớộư i đ   u tiên  củ a nó và khi l ấầửỏ y ph n t  ra kh i hàng đ ợẽứộưi s  căn c  vào đ   u tiên nh ỏấ  nh t. Cho mộ t tr ạ ng thái n, ký hi ệ u g(n) là t ổ ng chi phí đ ường đi ng ắ n nh ấ t (hi ệ n có)  từ  tr ạ ng thái ban đ ầu S đ ến tr ạ ng thái n. Thu ậ t toán UCS s ử  d ụ ng m ộ t hàng đ ợi  ưu tiên (Priority Queue – PQ) đ ể l ư u tr ữ  và duy ệ t các tr ạ ng thái trên đ ường đi.  Thuậ t toán dùng thêm m ộ t danh sách CLOSE đ ể l ư u tr ữ  các tr ạ ng thái đã đ ược  xét. Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Ưu đi ể m: Tìm kiế m theo giá thành th ố ng nh ấ t là t ố i  ư u vì con đ ường có chi phí  thấ p nh ấ t đ ược ch ọ n. Nhượ c đi ể m: Không cầ n quan tâm đ ến s ố  l ượ ng các b ướ c liên quan đ ến tìm ki ế m  và chỉ  quan tâm đ ến chi phí đ ường d ẫ n. Do đó gi ả  thu ậ t này có th ể   bị  m ắ t k ẹ t trong m ộ t vòng l ặ p vô h ạ n. 5. Tìm kiế m sâu d ầ n. Trong trí tuệ  nhân t ạ o hay lý thuy ế t đ ồ th ị , thu ậ t toán tìm ki ế m ki ế m sâu d ầ n là  1 thuậ t toán duy ệ t ho ặ c tìm ki ế m trên cây ho ặ c đ ồ th ị . Thuậ t toán đ ượưểắụểc đ a ra đ  kh c ph c đi m yêu c ủậ a thu t toán tìm ki ếớ m gi i  hạ n đ ộ sâu    DLS   . Đó là khi mà tấ t c ả  các l ờ i gi ả i n ằ m  ở  đ ộ sâu l ớ n h ơ n gi ớ i  hạ n đ ộ sâu l thì gi ả i thu ậ t DLS sẽ  th ấ t b ạ i. Giả i thu ậ t tìm ki ế m sâu d ầ n  sẽ  : áp dụ ng gi ả i thu ậ t    DLS   đối v ớ i đ ường đi có đ ộ dài <= 1 Nếấạếụ u th t b i, ti p t c áp d ụ ng gi ảậ i thu t dfs đ ốớười v i đ ng đi có đ ộ dài  <= 2 ..cứưậế  nh  v y đ n khi tìm đ ượờảặc l i gi i ho c khi toàn b ộ  cây đã đ ược  xét mà không tìm được l ờ i gi ả i. Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi ­         Luôn tìm ra nghiệ m (n ế u bài toán có nghi ệ m), mi ễ n là ch ọ n max đ ủ l ớ n  (giố ng nh ư  tìm ki ế m theo chi ề u r ộ ng)  ­         Có độ ph ứ c t ạ p th ờ i gian là O(kd) (gi ố ng tìm ki ế m r ộ ng)  ­         Có độ ph ứ c t ạ p không gian là O(k*d) (gi ố ng tìm ki ế m sâu)  ­         Giả i thu ậ t tìm ki ế m sâu d ầ n th ươ ng áp d ụ ng cho các bài toán có không  gian trạ ng thái l ớ n và đ ộ sâu c ủ a nghi ệ m không bi ế t tr ướ c. Ưu đi ể m: Nó tổ  ch ứ c các l ợ i ích c ủ a thu ậ t toán tìm ki ế m BFS và DFS v ề  m ặ t hi ệ u  quả  tìm ki ế m và b ộ  nh ớ  nhanh. Nhượ c đi ể m: Hạế n ch  chính c ủ a IDS là nó l ặạấả p l i t t c  các công vi ệủ c c a giai đo ạướ n tr c. 6. Tìm kiế m leo đ ồi. Tìm kiế m leo đ ồi là tìm ki ế m theo đ ộ sâu đ ược h ướ ng d ẫ n b ở i hàm đánh giá.  Song khác vớ i tìm ki ế m theo đ ộ sâu, khi phát tri ể n m ộ t đ ỉnh u thì b ướ c ti ế p theo  ta chọ n trong s ốỉ  các đ nh con c ủỉ a u, đ nh có h ứẹềấể a h n nhi u nh t đ  phát tri ể n,  đỉnh này đ ược xác đ ịnh b ở i hàm đánh giá. Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Ưu đi ể m: Phươ ng pháp tìm ki ế m leo đ ồi chú tr ọ ng tìm h ướ ng đi d ễẫếạ  d n đ n tr ng  thái đích nhấ t. Cách đó đ ược đ ưa ra nh ằ m làm gi ả m công s ứ c tìm ki ế m.  Thuậ t toán tìm ki ế m leo đ ồi th ự c ch ấ t là thu ậ t toán tìm ki ế m theo chi ề u  sâu, song tạỗướ i m i b c ta s ẽư   u tiên ch ọộạ n m t tr ng thái có h ứẹ a h n  nhanh tớ i đich nh ấ t đ ể phát tri ể n tr ướ c. V ấ n đ ề quan tr ọ ng là bi ế t khai  thác kheo léo thông tin phả n h ồ i đ ể xác đ ịnh h ướ ng đi ti ế p và đ ẩy nhanh  quá trình tìm kiế m. Thông th ườ ng ta gán m ỗ i tr ạ ng thái c ủ a bài toán v ớ i  mộ t s ố  đo (hàm đánh giá) nào đó nh ằ m đánh giá m ứ c đ ộ g ầ n đích c ủ a nó.  Điề u đó có nghĩa là n ế u tr ạ ng thái hi ệ n th ờ i là u thì tr ạ ng thái v s ẽ  đ ược  phát triể n ti ế p theo n ế u v k ề  v ớ i u và hàm đanh giá c ủ a v đ ạt giá tr ị  max  (hoặ c min). Nhượ c đi ể m: Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Cự c tr ị  đ ịa ph ươ ng: nút đang xét t ố t h ơ n các nút lân c ậ n, nh ư ng đó không  phả i là ph ươ ng án t ố t nh ấ t trong toàn th ể , ví v ậ y có th ể  ph ả i quay lui v ề   nút trướ c đ ể đi theo h ướ ng khác. Gi ả i pháp này đòi h ỏ i ghi nh ớ  l ạ i nhi ề u  đường đi.          Cao nguyên: Các giá trị  c ủ a các ph ươ ng án nh ư  nhau, không xác đ ịnh  được ngay h ướ ng nào là t ố t h ơ n trong vùng lân c ậ n. 7. Simulated annealing search. Dự a trên quá trình tôi  ủ  (annealing process): Kim lo ạ i ngu ộ i đi và l ạ nh c ứ ng l ạ i  thành cấ u trúc k ế t tinh  Phươ ng pháp tìm ki ế m Simulated Annealing có th ể  tránh đ ược các đi ể m t ố i  ư u  cụ c b ộ  (local optima)  Phươ ng pháp tìm ki ế m Simulated Annealing s ử  d ụ ng chi ế n l ượ c tìm ki ế m ng ẫ u  nhiên, trong đó chấ p nh ậ n các thay đ ổi làm tăng giá tr ị  hàm m ụ c tiêu (c ầ n c ự c  đại hóa) và cũng ch ấ p nh ậ n (có h ạ n ch ế ) các thay đ ổi làm gi ả m  Phươ ng pháp tìm ki ế m Simulated Annealing s ử  d ụ ng m ộ t tham s ố  đi ề u khi ể n T  (như  trong các h ệ  th ố ng nhi ệ t đ ộ) ❑ Bắ t đ ầu thì T nh ậ n giá tr ị  cao, và gi ả m d ầ n v ề  0 Ý tưở ng: Thoát kh ỏượ i (v t qua) các đi ểốưụộằ m t i  u c c b  b ng cách cho phép c ả   các dị ch chuy ểồừạ n “t i” t  tr ng thái hi ệờưảầầấủ n th i, nh ng gi m d n t n xu t c a các  di chuyể n t ồ i này (Có thểứ  ch ng minh đ ượếc) N u giá tr ịủ  c a tham s ố  T (xác đ ịứộảầnh m c đ  gi m t n  xuấ t đ ối v ớ i các di chuy ể n t ồ i) gi ả m ch ậ m, thì ph ươ ng pháp tìm ki ế m Simulated  Annealing sẽ  tìm đ ượờảốưc l i gi i t i  u toàn c ụớ c v i xác su ấấỉ t x p x  1  Phươ ng pháp tìm ki ế m Simulated Annealing Search r ấ t hay đ ược s ử  d ụ ng trong  các lĩnh vự c: thi ế t k ế  s ơ  đ ồ b ả ng m ạ ch VLSI, l ậ p l ị ch bay,  Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD: Th.S Ngô Hồ Anh Khôi Ưu đi ể m: Simulated annealing search có thể  đ ối phó v ớ i các mô hình phi tuy ế n tính  cao, dữ  li ệ u h ỗ n lo ạ n và  ồ n ào và nhi ề u ràng bu ộ c. Đó là m ộ t k ỹ  thu ậ t  mạ nh m ẽ  và chung chung. Ưu đi ể m chính c ủ a nó so v ớ i các ph ươ ng pháp tìm ki ế m đ ịa ph ươ ng khác  là tính linh hoạ t và kh ả  năng ti ế p c ậ n toàn c ầ u s ự  t ố i  ư u. Thuậ t toán này khá linh ho ạ t vì nó không d ự a trên b ấ t k ỳ  thu ộ c tính h ạ n  chế  nào c ủ a mô hình.