Thuật toán và giải thuật - Hoàng Kiếm Part 5

Nếu chi phí từ trạng thái khác luôn là hằng số thì thuật giải A* trở thành thuật giải tìm kiếm theo chiều rộng . Lý do là vì tât cả nhũng trạng thái cách trạng thái khởi đầu n bước đều có cùng giá trị g và vì thế có cùng f và giá trị này sẽ nhỏ hơn tất cả
Nội dung trích xuất từ tài liệu:
Thuật toán và giải thuật - Hoàng Kiếm Part 5 f’(Fagaras)  g(Fagaras)+ h’(Fagaras)  239+178 417 h’(Oradea)  380 g(Oradea)  g(Sibiu)+cost(Sibiu, Oradea)  140+151  291 f’(Oradea)  g(Oradea)+ h’(Oradea)  291+380  671 h’(R.Vilcea)  193 g(R.Vilcea)  g(Sibiu)+cost(Sibiu, R.Vilcea)  140+80  220 f’(R.Vilcea)  g(R.Vilcea)+ h’(R.Vilcea)  220+193  413Nút Arad ã có trong CLOSE. Tuy nhiên, do g(Arad) m i ư c t o ra (có giá tr 280)l n hơn g(Arad) lưu trong CLOSE (có giá tr 0) nên ta s không c p nh t l i giá tr gvà f’ c a Arad lưu trong CLOSE. 3 nút còn l i : Fagaras, Oradea, Rimnicu u khôngcó trong c OPEN và CLOSE nên ta s ưa 3 nút này vào OPEN, t cha c a chúng làSibiu. Như v y, n bư c này OPEN ã ch a t ng c ng 5 thành ph . OPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad) (Fagaras,g 239,h’ 178,f’ 417,Cha Sibiu) 29 Sưu t m b i: www.daihoc.com.vn (Oradea,g 291,h’ 380,f’ 617,Cha Sibiu) (R.Vilcea,g 220,h’ 193,f’ 413,Cha Sibiu)} CLOSE  {(Arad,g 0,h’ 0,f’ 0) (Sibiu,g 140,h’ 253,f’ 393,Cha Arad)}Trong t p OPEN, nút R.Vilcea là nút có giá tr f’ nh nh t. Ta ch n Tmax  R.Vilcea.Chuy n R.Vilcea t OPEN sang CLOSE. T R.Vilcea có th i n ư c 3 thành ph làCraiova, Pitesti và Sibiu. Ta l n lư t tính giá tr f’, g và h’ c a 3 thành ph này. h’(Sibiu)  253 g(Sibiu)  g(R.Vilcea)+ cost(R.Vilcea,Sibiu)  220+80 300 f’(Sibiu)  g(Sibiu)+h’(Sibiu)  300+253  553 h’(Craiova)  160 g(Craiova)  g(R.Vilcea)+ cost(R.Vilcea, Craiova)  220+146 366 f’(Craiova)  g(Fagaras)+h’(Fagaras)  366+160 526 h’(Pitesti)  98 g(Pitesti)  g(R.Vilcea)+ cost(R.Vilcea, Pitesti)  220+97  317 f’(Pitesti)  g(Oradea)+h’(Oradea)  317+98  415Sibiu ã có trong t p CLOSE. Tuy nhiên, do g’(Sibiu) m i (có giá tr là 553) l n hơng’(Sibiu) (có giá tr là 393) nên ta s không c p nh t l i các giá tr c a Sibiu ư c lưutrong CLOSE. Còn l i 2 thành ph là Pitesti và Craiova u không có trong c OPENvà CLOSE nên ta s ưa nó vào OPEN và t cha c a chúng là R.Vilcea. 30 Sưu t m b i: www.daihoc.com.vnOPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad) (Fagaras,g 239,h’ 178,f’ 417,Cha Sibiu) (Oradea,g 291,h’ 380,f’ 617,Cha Sibiu) (Craiova,g 366,h’ 160,f’ 526,Cha R.Vilcea) (Pitesti,g 317,h’ 98,f’ 415,Cha R.Vilcea) }CLOSE  {(Arad,g 0,h’ 0,f’ 0) (Sibiu,g 140,h’ 253,f’ 393,Cha Arad) (R.Vilcea,g 220,h’ 193,f’ 413,Cha Sibiu) } n ây, trong t p OPEN, nút t t nh t là Pitesti, t Pitesti ta có th i n ư c R.Vilcea, Bucharest và Craiova. L y Pitesti ra kh i OPEN và t nó vàoCLOSE. Th c hi n ti p theo tương t như trên, ta s không c p nh t giá tr f’,g c a R.Vilcea và Craiova lưu trong CLOSE. Sau khi tính toán f’, g c aBucharest, ta s ưa Bucharest vào t p OPEN, t Cha(Bucharest)  Pitesti.h’(Bucharest)  0g(Bucharest)  g(Pitesti)+cost(Pitesti, Bucharest)  317+100 418f’(Bucharest)  g(Fagaras)+h’(Fagaras)  417+0 417 31 Sưu t m b i: www.daihoc.com.vn bư c k ti p, ta s ch n ư c Tmax  Bucharest. Và như v y thu t toán k t thúc(th c ra thì t i bư c này, có hai ng c viên là Bucharest và Fagaras vì u cùng cóf’ 417 , nhưng vì Bucharest là ích nên ta s ưu tiên ch n hơn). xây d ng l i con ư ng i t Arad n Bucharest ta l n theo giá tr Cha ư c lưutr kèm v i f’, g và h’ cho n lúc n Arad. Cha(Bucharest)  Pitesti Cha(R.Vilcea)  Sibiu Cha(Sibiu)  AradV y con ư ng i ng n nh t t Arad n Bucharest là Arad, Sibiu, R.Vilcea, Pitesti,Bucharest.Trong ví d minh h a này, hàm h’ có ch t lư ng khá t t và c u trúc th khá ơngi n nên ta g n như i th ng n ích mà ít ph i kh o sát các con ư ng khác. âylà m t trư ng h p ơn gi n, trong trư ng h p này, thu t gi i có dáng d p c a tìmki m chi u sâu. n ây, minh h a m t trư ng h p ph c t p hơn c a thu t gi i. Ta th s a il ic u trúc th và quan sát ho t ng c a thu t gi i. Gi s ta c ...