Đề tài Nghiên cứu thuật toán A sao

LỜI MỞ ĐẦU Trí tuệ nhân tạo đang trở thành một một môn học phổ biến và được sử dụng trong hầu hết các ứng dụng hiện nay. Có thể kể đến một vài ứng dụng của trí tuệ nhân tạo trong lập trình ai cho game rồi các chương trình sử lý phân tích toán học phức tạp… Trong đó tìm kiếm là một mảng luôn luôn được nhắn tới nhiều nhất trong trí tuệ nhân tạo. Vì vậy chúng em chọn đề tài nghiên cứu về tìm kiếm tối ưu và một thể hiện đặc trưng của nó là thuật toán A* . Trong bài làm còn nhiều thiếu sót mong thầy và các bạn đóng góp ý kiến để đề tài được hoàn thiện hơn. Cuối cùng thay cho lời kết, chúng em xin chân thành cảm ơn thầy giáo Trần Hùng Cường đã tận tình giúp đỡ, hướng dẫn, sửa chữa trong quá trình thực hiện đề tài này Mục lục I Lý thuyết 1.Tìm kiếm ưu tiên tối ưu (best-first search) Ưu điểm của tìm kiếm theo chiều sâu là không phải quan tâm đến sự mở rộng của tất cả các nhánh. Ưu điểm của tìm kiếm chiều rộng là không bị sa vào các đường dẫn bế tắc (các nhánh cụt). Tìm kiếm ưu tiên tối ưu sẽ kết hợp 2 phương pháp trên cho phép ta đi theo một con đường duy nhất tại một thời điểm, nhưng đồng thời vẫn "quan sát" được những hướng khác. Nếu con đường đang đi "có vẻ" không triển vọng bằng những con đường ta đang "quan sát" ta sẽ chuyển sang đi theo một trong số các con đường này. Để tiện lợi ta sẽ dùng chữ viết tắt BFS thay cho tên gọi tìm kiếm ưu tiên tối ưu. Một cách cụ thể, tại mỗi bước của tìm kiếm BFS, ta chọn đi theo trạng thái có khả năng cao nhất trong số các trạng thái đã được xét cho đến thời điểm đó. (khác với leo đồi dốc đứng là chỉ chọn trạng thái có khả năng cao nhất trong số các trạng thái kế tiếp có thể đến được từ trạng thái hiện tại). Như vậy, với tiếp cận này, ta sẽ ưu tiên đi vào những nhánh tìm kiếm có khả năng nhất (giống tìm kiếm leo đồi dốc đứng), nhưng ta sẽ không bị lẩn quẩn trong các nhánh này vì nếu càng đi sâu vào một hướng mà ta phát hiện ra rằng hướng này càng đi thì càng tệ, đến mức nó xấu hơn cả những hướng mà ta chưa đi, thì ta sẽ không đi tiếp hướng hiện tại nữa mà chọn đi theo một hướng tốt nhất trong số những hướng chưa đi. Đó là tư tưởng chủ đạo của tìm kiếm BFS. Để hiểu được tư tưởng này. Bạn hãy xem ví dụ sau : Minh họa thuật giải Best-First Search Khởi đầu, chỉ có một nút (trạng thái) A nên nó sẽ được mở rộng tạo ra 3 nút mới B,C và D. Các con số dưới nút là giá trị cho biết độ tốt của nút. Con số càng nhỏ, nút càng tốt. Do D là nút có khả năng nhất nên nó sẽ được mở rộng tiếp sau nút A và sinh ra 2 nút kế tiếp là E và F. Đến đây, ta lại thấy nút B có vẻ có khả năng nhất (trong các nút B,C,E,F) nên ta sẽ chọn mở rộng nút B và tạo ra 2 nút G và H. Nhưng lại một lần nữa, hai nút G, H này được đánh giá ít khả năng hơn E, vì thế sự chú ý lại trở về E. E được mở rộng và các nút được sinh ra từ E là I và J. Ở bước kế tiếp, J sẽ được mở rộng vì nó có khả năng nhất. Quá trình này tiếp tục cho đến khi tìm thấy một lời giải. Lưu ý rằng tìm kiếm này rất giống với tìm kiếm leo đồi dốc đứng, với 2 ngoại lệ. Trong leo núi, một trạng thái được chọn và tất cả các trạng thái khác bị loại bỏ, không bao giờ chúng được xem xét lại. Cách xử lý dứt khoát này là một đặc trưng của leo đồi. Trong BFS, tại một bước, cũng có một di chuyển được chọn nhưng những cái khác vẫn được giữ lại, để ta có thể trở lại xét sau đó khi trạng thái hiện tại trở nên kém khả năng hơn những trạng thái đã được lưu trữ. Hơn nữa, ta chọn trạng thái tốt nhất mà không quan tâm đến nó có tốt hơn hay không các trạng thái trước đó. Điều này tương phản với leo đồi vì leo đồi sẽ dừng nếu không có trạng thái tiếp theo nào tốt hơn trạng thái hiện hành. . Để cài đặt các thuật giải theo kiểu tìm kiếm BFS, người ta thường cần dùng 2 tập hợp sau : OPEN : tập chứa các trạng thái đã được sinh ra nhưng chưa được xét đến (vì ta đã chọn một trạng thái khác). Thực ra, OPEN là một loại hàng đợi ưu tiên (priority queue) mà trong đó, phần tử có độ ưu tiên cao nhất là phần tử tốt nhất. Người ta thường cài đặt hàng đợi ưu tiên bằng Heap. CLOSE : tập chứa các trạng thái đã được xét đến. Chúng ta cần lưu trữ những trạng thái này trong bộ nhớ để đề phòng trường hợp khi một trạng thái mới được tạo ra lại trùng với một trạng thái mà ta đã xét đến trước đó. Trong trường hợp không gian tìm kiếm có dạng cây thì không cần dùng tập này. Thuật giải BEST-FIRST SEARCH 1. Đặt OPEN chứa trạng thái khởi đầu. 2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện : 2.a. Chọn trạng thái tốt nhất (Tmax) trong OPEN (và xóa Tmax khỏi OPEN) 2.b. Nếu Tmax là trạng thái kết thúc thì thoát. 2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện : Tính f(Tk); Thêm Tk vào OPEN BFS khá đơn giản. Tuy vậy, trên thực tế, cũng như tìm kiếm chiều sâu và chiều rộng, hiếm khi ta dùng BFS một cách trực tiếp. Thông thường, người ta thường dùng các phiên bản của BFS là AT, AKT và A* Thông tin về quá khứ và tương lai Thông thường, trong các phương án tìm kiếm theo kiểu BFS, độ tốt f của một trạng thái được tính dựa theo 2 hai giá trị mà ta gọi là là g và h’. h’ chúng ta đã biết, đó là một ước lượng về chi phí từ trạng thái hiện hành cho đến trạng thái đích (thông tin tương lai). Còn g là "chiều dài quãng đường" đã đi từ trạng thái ban đầu cho đến trạng thái hiện tại (thông tin quá khứ). Lưu ý rằng g là chi phí thực sự (không phải chi phí ước lượng). Để dễ hiểu, bạn hãy quan sát hình sau : Phân biệt khái niệm g và h’ Kết hợp g và h’ thành f’ (f’ = g + h’) sẽ thể hiện một ước lượng về "tổng chi phí" cho con đường từ trạng thái bắt đầu đến trạng thái kết thúc dọc theo con đường đi qua trạng thái hiện hành. Để thuận tiện cho thuật giải, ta quy ước là g và h’ đều không âm và càng nhỏ nghĩa là càng tốt. 2.Thuật giải A* A* là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật giải A* có sử dụng thêm tập hợp CLOSE để lưu trữ những trường hợp đã được xét đến. A* mở rộng AKT bằng cách bổ sung cách giải quyết trường hợp khi "mở" một nút mà nút này đã có sẵn trong OPEN hoặc CLOSE. Khi xét đến một trạng thái Ti bên cạnh việc lưu trữ 3 giá trị cơ bản g,h’, f’ để phản ánh độ tốt của trạng thái đó, A* còn lưu trữ thêm hai thông số sau : 1. Trạng thái cha của trạng thái Ti (ký hiệu là Cha(Ti) : cho biết trạng thái dẫn đến trạng thái Ti. Trong trường hợp có nhiều trạng thái dẫn đến Ti thì chọn Cha(Ti) sao cho chi phí đi từ trạng thái khởi đầu đến Ti là thấp nhất, nghĩa là : g(Ti) = g(Tcha) + cost(Tcha, Ti) là thấp nhất. 2. Danh sách các trạng thái kế tiếp của Ti : danh sách này lưu trữ các trạng thái kế tiếp Tk của Ti sao cho chi phí đến Tk thông qua Ti từ trạng thái ban đầu là thấp nhất. Thực chất thì danh sách này có thể được tính ra từ thuộc tính Cha của các trạng thái được lưu trữ. Tuy nhiên, việc tính toán này có thể mất nhiều thời gian (khi tập OPEN, CLOSE được mở rộng) nên người ta thường lưu trữ ra một danh sách riêng. Trong thuật toán sau đây, chúng ta sẽ không đề cập đến việc lưu trữ danh sách này. Sau khi hiểu rõ thuật toán, bạn đọc có thể dễ dàng điều chỉnh lại thuật toán để lưu trữ thêm thuộc tính này. 1. Đặt OPEN chỉ chứa T0. Đặt g(T0) = 0, h’(T0) = 0 và f’(T0) = 0. đặt CLOSE là tập hợp rỗng. 2. Lặp lại các bước sau cho đến khi gặp điều kiện dừng. 2.a. Nếu OPEN rỗng : bài toán vô nghiệm, thoát. 2.b. Ngược lại, chọn Tmax trong OPEN sao cho f’(Tmax) là nhỏ nhất 2.b.1. Lấy Tmax ra khỏi OPEN và đưa Tmax vào CLOSE. 2.b.2. Nếu Tmax chính là TG thì thoát và thông báo lời giải là Tmax. 2.b.3. Nếu Tmax không phải là TG. Tạo ra danh sách tất cả các trạng thái kế tiếp của Tmax. Gọi một trạng thái này là Tk. Với mỗi Tk, làm các bước sau : 2.b.3.1. Tính g(Tk) = g(Tmax) + cost(Tmax, Tk). 2.b.3.2. Nếu Tk chưa xuất hiện trong cả OPEN lẫn CLOSE thì : Thêm Tk vào OPEN 2.b.3.3. Nếu tồn tại Tk’ trong OPEN trùng với Tk. Nếu g(Tk) < g(Tk’) thì Đặt g(Tk’) = g(Tk) Tính lại f’(Tk’) Đặt Cha(Tk’) = Tmax Tính : f' (Tk) = g(Tk)+h’(Tk). Có một số điểm cần giải thích trong thuật giải này. Đầu tiên là việc sau khi đã tìm thấy trạng thái đích TG, làm sao để xây dựng lại được "con đường" từ T0 đến TG. Rất đơn giản, bạn chỉ cần lần ngược theo thuộc tính Cha của các trạng thái đã được lưu trữ trong CLOSE cho đến khi đạt đến T0. Đó chính là "con đường" tối ưu đi từ TG đến T0 (hay nói cách khác là từ T0 đến TG). Điểm thứ hai là thao tác cập nhật lại g(Tk’) , f’(Tk’) và Cha(Tk’) trong bước 2.b.3.3. Các thao tác này thể hiện tư tưởng : "luôn chọn con đường tối ưu nhất". Như chúng ta đã biết, giá trị g(Tk’) nhằm lưu trữ chi phí tối ưu thực sự tính từ T0 đến Tk’. Do đó, nếu chúng ta phát hiện thấy một "con đường" khác tốt hơn thông qua Tk (có chi phí nhỏ hơn) con đường hiện tại được lưu trữ thì ta phải chọn "con đường" mới tốt hơn này. Một lần nữa, xin nhắc lại rằng, bạn có thể cho rằng tập OPEN lưu trữ các trạng thái "sẽ được xem xét đến sau" còn tập CLOSE lưu trữ các trạng thái "đã được xét đến rồi". Có thể bạn sẽ cảm thấy khá lúng túng trước một thuật giải dài như thế. Vấn đề có lẽ sẻ trở nên sáng sủa hơn khi bạn quan sát các bước giải bài toán tìm đường đi ngắn nhất trên đồ thị bằng thuật giải A* sau đây. 3. Ví dụ minh họa hoạt động của thuật giải A* Chúng ta sẽ minh họa hoạt động của thuật giải A* trong việc tìm kiếm đường đi ngắn nhất từ thành phố Arad đến thành phố Bucharest của Romania. Bản đồ các thành phố của Romania được cho trong đồ thị sau. Trong đó mỗi đỉnh của đồ thị của là một thành phố, giữa hai đỉnh có cung nối nghĩa là có đường đi giữa hai thành phố tương ứng. Trọng số của cung chính là chiều dài (tính bằng km) của đường đi nối hai thành phố tương ứng, chiều dài theo đường chim bay một thành phố đến Bucharest được cho trong bảng kèm theo. Bảng đồ của Romania với khoảng cách đường tính theo km Khoảng cách đường chim bay từ một thành phố đến Bucharest. Chúng ta sẽ chọn hàm h’ chính là khoảng cách đường chim bay cho trong bảng trên và hàm chi phí cost(Ti, Ti+1) chính là chiều dài con đường nối từ thành phố Ti và Ti+1. Sau đây là từng bước hoạt động của thuật toán A* trong việc tìm đường đi ngắn nhất từ Arad đến Bucharest. Ban đầu : OPEN = {(Arad,g= 0,h’= 0,f’= 0)} CLOSE = {} Do trong OPEN chỉ chứa một thành phố duy nhất nên thành phố này sẽ là thành phố tốt nhất. Nghĩa là Tmax = Arad.Ta lấy Arad ra khỏi OPEN và đưa vào CLOSE. OPEN = {} CLOSE = {(Arad,g= 0,h’= 0,f’= 0)} Từ Arad có thể đi đến được 3 thành phố là Sibiu, Timisoara và Zerind. Ta lần lượt tính giá trị f’, g và h’ của 3 thành phố này. Do cả 3 nút mới tạo ra này chưa có nút cha nên ban đầu nút cha của chúng đều là Arad. h’(Sibiu) = 253 g(Sibiu) = g(Arad)+cost(Arad,Sibiu) = 0+140= 140 f’(Sibiu) = g(Sibiu)+h’(Sibiu) = 140+253 = 393 Cha(Sibiu) = Arad h’(Timisoara) = 329 g(Timisoara) = g(Arad)+cost(Arad, Timisoara) = 0+118= 118 f’(Timisoara) = g(Timisoara)+ h’(Timisoara) = 118+329 = 447 Cha(Timisoara) = Arad h’(Zerind) = 374 g(Zerind) = g(Arad)+cost(Arad, Zerind) = 0+75= 75 f’(Zerind) = g(Zerind)+h’(Zerind) = 75+374 = 449 Cha(Zerind) = Arad Do cả 3 nút Sibiu, Timisoara, Zerind đều không có trong cả OPEN và CLOSE nên ta bổ sung 3 nút này vào OPEN. OPEN = {(Sibiu,g= 140,h’= 253,f’= 393,Cha= Arad) (Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad) (Zerind,g= 75,h’= 374,f’= 449,Cha= Arad)} CLOSE = {(Arad,g= 0,h’= 0,f’= 0)} Bước 1 nút được đóng ngoặc vuông (như [Arad]) là nút trong tập CLOSE, ngược lại là trong tập OPEN. Trong tập OPEN, nút Sibiu là nút có giá trị f’ nhỏ nhất nên ta sẽ chọn Tmax = Sibiu. Ta lấy Sibiu ra khỏi OPEN và đưa vào CLOSE. OPEN = {(Timisoara,g= 118,h’= 329,f’= 447,Cha= Arad) (Zerind,g= 75,h’= 374,f’= 449,Cha= Arad)} CLOSE = {(Arad,g= 0,h’= 0,f’= 0) (Sibiu,g= 140,h’= 253,f’= 393,Cha= Arad)} Từ Sibiu có thể đi đến được 4 thành phố là : Arad, Fagaras, Oradea, Rimnicu. Ta lần lượt tính các giá trị g, h’, f’ cho các nút này. h’(Arad) = 366 g(Arad) = g(Sibiu)+cost(Sibiu,Arad) = 140+140= 280 f’(Arad) = g(Arad)+h’(Arad) = 280+366 = 646 h’(Fagaras) = 178 g(Fagaras) = g(Sibiu)+cost(Sibiu, Fagaras) = 140+99= 239 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 = 413 Nú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ị g và f’ của Arad lưu trong CLOSE. 3 nút còn lại : Fagaras, Oradea, Rimnicu đều không có 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) (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 = 415 Sibiu đã có trong tập CLOSE. Tuy nhiên, do g’(Sibiu) mới (có giá trị là 553) lớn hơn g’(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ưu trong CLOSE. Còn lại 2 thành phố là Pitesti và Craiova đều không có trong cả OPEN và CLOSE nên ta sẽ đưa nó vào OPEN và đặt cha của chúng là R.Vilcea. 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) (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ào CLOSE. 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ủa Bucharest, ta sẽ đưa Bucharest vào tập OPEN, đặt Cha(Bucharest) = Pitesti. h’(Bucharest) = 0 g(Bucharest) = g(Pitesti)+cost(Pitesti, Bucharest) = 317+100= 418 f’(Bucharest) = g(Fagaras)+h’(Fagaras) = 417+0= 417 Ở 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ưu trữ kèm với f’, g và h’ cho đến lúc đến Arad. Cha(Bucharest) = Pitesti Cha(R.Vilcea) = Sibiu Cha(Sibiu) = Arad Vậ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á đơn giả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. Đây là 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ìm kiế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 đổi lại cấu trúc đồ thị và quan sát hoạt động của thuật giải. Giả sử ta có thêm một thành phố tạm gọi là TP và con đường giữa Sibiu và TP có chiều dài 100, con đường giữa TP và Pitesti có chiều dài 60. Và khoảng cách đường chim bay từ TP đến Bucharest là 174. Như vậy rõ ràng, con đường tối ưu đến Bucharest không còn là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest nữa mà là Arad, Sibiu, TP, Pitesti, Bucharest. Trong trường hợp này, chúng ta vẫn tiến hành bước 1 như ở trên. Sau khi thực hiện hiện bước 2 (mở rộng Sibiu), chúng ta có cây tìm kiếm như hình sau. Lưu ý là có thêm nhánh TP. R.Vilcea vẫn có giá trị f’ thấp nhất. Nên ta mở rộng R.Vilcea như trường hợp đầu tiên. Bước kế tiếp của trường hợp đơn giản là mở rộng Pitesti để có được kết quả. Tuy nhiên, trong trường hợp này, TP có giá trị f’ thấp hơn. Do đó, ta chọn mở rộng TP. Từ TP ta chỉ có 2 hướng đi, một quay lại Sibiu và một đến Pitesti. Để nhanh chóng, ta sẽ không tính toán giá trị của Sibiu vì biết chắc nó sẽ lớn hơn giá trị được lưu trữ trong CLOSE (vì đi ngược lại). h’(Pitesti) = 98 g(Pitesti) = g(TP)+cost(TP, Pitesti) = 240+75= 315 f’(Pitesti) = g(TP)+h’(Pitesti) = 315+98= 413 Pistestti đã xuất hiện trong tập OPEN và g’(Pitesti) mới (có giá trị là 315) thấp hơn g’(Pitesti) cũ (có giá trị 317) nên ta phải cập nhật lại giá trị của f’,g, Cha của Pitesti lưu trong OPEN. Sau khi cập nhật xong, tập OPEN và CLOSE sẽ như sau : 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) (Oradea,g= 291,h’= 380,f’= 617,Cha= Sibiu) (Craiova,g= 366,h’= 160,f’= 526,Cha= R.Vilcea) (Pitesti,g= 315,h’= 98,f’= 413,Cha= TP) } 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 ta thấy rằng, ban đầu thuật giải chọn đường đi đến Pitesti qua R.Vilcea. Tuy nhiên, sau đó, thuật giải phát hiện ra con đường đến Pitesti qua TP là tốt hơn nên nó sẽ sử dụng con đường này. Đây chính là trường hợp 2.b.iii.2 trong thuật giải. Bước sau, chúng ta sẽ chọn mở rộng Pitesti như bình thường. Khi lần ngược theo thuộc tính Cha, ta sẽ có con đường tối ưu là Arad, Sibiu, TP, Pitesti, Bucharest. 4.Nhận xét về A* Đến đây, có lẽ bạn đã hiểu được thuật giải này. Ta có một vài nhận xét khá thú vị về A*. Đầu tiên là vai trò của g trong việc giúp chúng ta lựa chọn đường đi. Nó cho chúng ta khả năng lựa chọn trạng thái nào để mở rộng tiếp theo, không chỉ dựa trên việc trạng thái đó tốt như thế nào (thể hiện bởi giá trị h’) mà còn trên cơ sở con đường từ trạng thái khởi đầu đến trạng thái hiện tại đó tốt ra sao. Điều này sẽ rất hữu ích nếu ta không chỉ quan tâm việc tìm ra lời giải hay không mà còn quan tâm đến hiệu quả của con đường dẫn đến lời giải. Chẳng hạn như trong bài toán tìm đường đi ngắn nhất giữa hai điểm. Bên cạnh việc tìm ra đường đi giữa hai điểm, ta còn phải tìm ra một con đường ngắn nhất. Tuy nhiên, nếu ta chỉ quan tâm đến việc tìm được lời giải (mà không quan tâm đến hiệu quả của con đường đến lời giải), chúng ta có thể đặt g=0 ở mọi trạng thái. Điều này sẽ giúp ta luôn chọn đi theo trạng thái có vẻ gần nhất với trạng thái kết thúc (vì lúc này f’ chỉ phụ thuộc vào h’ là hàm ước lượng "khoảng cách" gần nhất để tới đích). Lúc này thuật giải có dáng dấp của tìm kiếm chiều sâu theo nguyên lý hướng đích kết hợp với lần ngược. Ngược lại, nếu ta muốn tìm ra kết quả với số bước ít nhất (đạt được trạng thái đích với số trạng thái trung gian ít nhất), thì ta đặt giá trị để đi từ một trạng thái đến các trạng thái con kế tiếp của nó luôn là hằng số, thường là 1 Nghĩa đặt cost(Ti-1, Ti) = 1 (và vẫn dùng một hàm ước lượng h’ như bình thường). Còn ngược lại, nếu muốn tìm chi phí rẻ nhất thì ta phải đặt giá trị hàm cost chính xác (phản ánh đúng ghi phí thực sự). Đến đây, chắc bạn đọc đã có thể bắt đầu cảm nhận được rằng thuật giải A* không hoàn toàn là một thuật giải tối ưu tuyệt đối. Nói đúng hơn, A* chỉ là một thuật giải linh động và cho chúng ta khá nhiều tùy chọn. Tùy theo bài toán mà ta sẽ có một bộ thông số thích hợp cho A* để thuật giải hoạt động hiệu quả nhất. Điểm quan tâm thứ hai là về giá trị h’ – sự ước lượng khoảng cách (chi phí) từ một trạng thái đến trạng thái đích. Nếu h’ chính là h (đánh giá tuyệt đối chính xác) thì A* sẽ đi một mạch từ trạng thái đầu đến trạng thái kết thúc mà không cần phải thực hiện bất kỳ một thao tác đổi hướng nào!. Dĩ nhiên, trên thực tế, hầu như chẳng bao giờ ta tìm thấy một đánh giá tuyệt đối chính xác. Tuy nhiên, điều đáng quan tâm ở đây là h’ được ước lượng càng gần với h, quá trình tìm kiếm càng ít bị sai sót, ít bị rẽ vào những nhánh cụt hơn. Hay nói ngắn gọn là càng nhanh chóng tìm thấy lời giải hơn. Nếu h’ luôn bằng 0 ở mọi trạng thái (trở về thuật giải AT) thì quá trình tìm kiếm sẽ được điều khiển hoàn toàn bởi giá trị g. Nghĩa là thuật giải sẽ chọn đi theo những hướng mà sẽ tốn ít chi phí/bước đi nhất (chi phí tính từ trạng thái đầu tiên đến trạng thái hiện đang xét) bất chấp việc đi theo hướng đó có khả năng dẫn đến lời giải hay không. Đây chính là hình ảnh của nguyên lý tham lam (Greedy). Nếu chi phí từ trạng thái sang trạng thái khác luôn là hằng số (dĩ nhiên lúc này h’ luôn bằng 0) 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ế đều có cùng f’ và giá trị này sẽ nhỏ hơn tất cả các trạng thái cách trạng thái khởi đầu n+1 bước. Và nếu g luôn bằng 0 và h’ cũng luôn bằng 0, mọi trạng thái đang xét đều tương đương nhau. Ta chỉ có thể chọn bằng trạng thái kế tiếp bằng ngẫu nhiên ! Còn nếu như h’ không thể tuyệt đối chính xác (nghĩa là không bằng đúng h) và cũng không luôn bằng 0 thì sao? Có điều gì thú vị về cách xử lý của quá trình tìm kiếm hay không? Câu trả lời là có. Nếu như bằng một cách nào đó, ta có thể chắc chắn rằng, ước lượng h’ luôn nhỏ hơn h (đối với mọi trạng thái) thì thuật giải A* sẽ thường tìm ra con đường tối ưu (xác định bởi g) để đi đến đích, nếu đường dẫn đó tồn tại và quá trình tìm kiếm sẽ ít khi bị sa lầy vào những con đường quá dở. Còn nếu vì một lý do nào đó, ước lượng h’ lại lớn hơn h thì thuật giải sẽ dễ dàng bị vướng vào những hướng tìm kiếm vô ích. Thậm chí nó lại có khuynh hướng tìm kiếm ở những hướng đi vô ích trước! Điều này có thể thấy một cách dễ dàng từ vài ví dụ. Xét trường hợp được trình bày trong hình sau. Giả sử rằng tất cả các cung đều có giá trị 1. G là trạng thái đích. Khởi đầu, OPEN chỉ chứa A, sau đó A được mở rộng nên B, C, D sẽ được đưa vào OPEN (hình vẽ mô tả trạng thái 2 bước sau đó, khi B và E đã được mở rộng). Đối với mỗi nút, con số đầu tiên là giá trị h’, con số kế tiếp là g. Trong ví dụ này, nút B có f’ thấp nhất là 4 = h’+g = 3 + 1 , vì thế nó được mở rộng trước tiên. Giả sử nó chỉ có một nút con tiếp theo là E và h’(E) = 3, do E các A hai cung nên g(E) = 2 suy ra f’(E) = 5, giống như f’(C). Ta chọn mở rộng E kế tiếp. Giả sử nó cũng chỉ có duy nhất một con kế tiếp là F và h’(F) cũng bằng 3. Rõ ràng là chúng ta đang di chuyển xuống và không phát triển rộng. Nhưng f’(F) = 6 lớn hơn f’(D). Do đó, chúng ta sẽ mở rộng C tiếp theo và đạt đến trạng thái đích. Như vậy, ta thấy rằng do đánh giá thấp h(B) nên ta đã lãng phí một số bước (E,F), nhưng cuối cùng ta cùng phát hiện ra B khác xa với điều ta mong đợi và quay lại để thử một đường dẫn khác. h’ đánh giá thấp h Bây giờ hãy xét trường hợp ở hình tiếp theo. Chúng ta cũng mở rộng B ở bước đầu tiên và E ở bước thứ hai. Kế tiếp là F và cuối cùng G, cho đường dẫn kết thúc có độ dài là 4. Nhưng giả sử có đường dẫn trực tiếp từ D đến một lời giải có độ dài h thực sự là 2 thì chúng ta sẽ không bao giờ tìm được đường dẫn này (tuy rằng ta có thể tìm thấy lời giải). Bởi vì việc đánh giá quá cao h’(D), chúng ta sẽ làm cho D trông dở đến nỗi mà ta phải tìm một đường đi khác – đến một lời giải tệ hơn - mà không bao giờ nghĩ đến việc mở rộng D. Nói chung, nếu h’ đánh giá cao h thì A* sẽ có thể không thể tìm ra đường dẫn tối ưu đến lời giải (nếu như có nhiều đường dẫn đến lời giải). Một câu hỏi thú vị là "Liệu có một nguyên tắc chung nào giúp chúng ta đưa ra một cách ước lượng h’ không bao giờ đánh giá cao h hay không?". Câu trả lời là "hầu như không", bởi vì đối với hầu hết các vấn đề thực ta đều không biết h. Tuy nhiên, cách duy nhất để bảo đảm h’ không bao giờ đánh giá cao h là đặt h’ bằng 0 ! h’ đánh giá cao h Đến đây chúng ta đã kết thúc việc bàn luận về thuật giải A*, một thuật giải linh động, tổng quát, trong đó hàm chứa cả tìm kiếm chiều sâu, tìm kiếm chiều rộng và những nguyên lý Heuristic khác. Chính vì thế mà người ta thường nói, A* chính là thuật giải tiêu biểu cho Heuristic. A* rất linh động nhưng vẫn gặp một khuyết điểm cơ bản – giống như chiến lược tìm kiếm chiều rộng – đó là tốn khá nhiều bộ nhớ để lưu lại những trạng thái đã đi qua – nếu chúng ta muốn nó chắc chắn tìm thấy lời giải tối ưu. Với những không gian tìm kiếm lớn nhỏ thì đây không phải là một điểm đáng quan tâm. Tuy nhiên, với những không gian tìm kiếm khổng lồ (chẳng hạn tìm đường đi trên một ma trận kích thước cỡ 106 x 106) thì không gian lưu trữ là cả một vấn đề hóc búa. Các nhà nghiên cứu đã đưa ra khá nhiều các hướng tiếp cận lai để giải quyết vấn đề này. Chúng ta sẽ tìm hiểu một số phương án nhưng quan trọng nhất, ta cần phải nắm rõ vị trí của A* so với những thuật giải khác. II THUẬT TOÁN VÀ CODE 1.Lưu đồ thuật toán 2.Giao diện a.Giao diện chương trình khi chạy b.Giao diện chương trình khi thực thi c.Giao diện chương trình khi kết thúc 3.Code a.Sơ đồ lớp b.Lớp Dinh Có chức năng lưu giữ thông tin của đỉnh gồm có Struct toadodinh lưu dữ thông tin tọa độ của đỉnh phục vụ cho chức năng vẽ đỉnh, gồm hai thuộc tính là x,y giữ tọa độ x,y tương ứng Thuộc tính h, g, f, cha dùng để lưu trữ chi phí tương lai, chi phí thực tế, tổng chi phí, và đỉnh cha của đỉnh hiện tại Ngoài ra còn có danh sách các đỉnh kề với đỉnh đó Code public struct toadodinh { public float x; public float y; public toadodinh(float x, float y) { this.x = x; this.y = y; } } class Dinh { private float h; public float h_gs { get { return h; } set { h = value; } } private int cha; public int cha_gs { get { return cha; } set { cha = value; } } private float g; public float g_gs { get{return g;} set{g=value;} } private float f; public void f_s() { f = g + h; } public float f_g() { return f; } public List dinhke=new List(); public toadodinh toadodinh; public void toadodinh_gs(int x, int y) { toadodinh = new toadodinh(x, y); } } c.Lớp Dothi Gồm các sử lý chính của thuật toán A* Gồm các thuộc tính dsdinh, dinhdau, dinhcuoi, chiphithucte dùng để lưu trữ tập hợp các đỉnh thuộc đồ thị, đỉnh bắt đầu, đỉnh kết thúc và một mảng các chi phí thực tế của đồ thị Phương thức dothi() để nhập các tham số đỉnh đầu, đỉnh cuối, số đỉnh, chi phí tương lai Phương thức napchiphithucte() và napdinhke() để nạp mảng chi phí thực tế và danh sách các đỉnh kề của đỉnh hiện hành Phương thức vedinh() để vẽ các đỉnh đã có của đồ thị, veduongdi() vẽ các đường đi được xử lý trong astar chi tiết sẽ giải thích trong code Code using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Windows.Forms; using System.Drawing; using System.Threading; namespace trituenhantao { class Dothi { public List dsdinh = new List(); private int sodinh; public int sodinh_gs { get { return sodinh; } set { sodinh = value; } } private int dinhdau; public int dinhdau_gs { get { return dinhdau; } set { dinhdau = value; } } private int dinhcuoi; public int dinhcuoi_gs { get { return dinhcuoi; } set { dinhcuoi = value; } } public float[,] chiphithucte; public Dothi() { } /// /// khoi tao do thi /// /// tong so dinh cua do thi /// /// /// nap chi phi uoc luong public Dothi(int sodinh, int dinhdau, int dinhcuoi,string h) { this.sodinh = sodinh; chiphithucte = new float[sodinh, sodinh]; this.dinhdau = dinhdau; this.dinhcuoi = dinhcuoi; Dinh dinh; for (int i = 0; i < sodinh; i++) { dinh=new Dinh(); dinh.h_gs= float.Parse(h.Split(' ')[i]); dsdinh.Add(dinh); } } public void napchiphithucte(int dinh,string g) { for (int i= 0; i < sodinh; i++) { chiphithucte[dinh, i] = float.Parse(g.Split(' ')[i]);//cat chi phi thuc te tu xau truyen vao } } public void napdinhke() { for (int u = 0; u < sodinh; u++) for (int v = 0; v < sodinh; v++) if (chiphithucte[u,v]!=0) dsdinh[u].dinhke.Add(v); } /// /// ham tinh toan duong di theo thuat toan a* /// /// danh sach dinh xet /// danh dach dinh ke /// danh sach dinh mo /// danh sach dinh dong /// doi tuong do hoa /// public List astar(ListBox lbn, ListBox lbbn, ListBox lbtapmo, ListBox lbtapdong,Graphics g) { List tapmo = new List(); List tapdong = new List(); float fmin = float.MaxValue; float gtrunggian; int S = dinhdau; //xu ly cho dinh dau tien xet toi dsdinh[S].g_gs = 0; dsdinh[S].f_s(); tapmo.Add(S); lbtapmo.Items.Add(tapmo[0].ToString() + ": g = "+dsdinh[S].g_gs.ToString()+" , f = "+dsdinh[S].f_g().ToString()); g.DrawEllipse(new Pen(Color.Aqua, 2), dsdinh[dinhdau_gs].toadodinh.x, dsdinh[dinhdau_gs].toadodinh.y, 20, 20); #region xu ly hang dau tien lbtapdong.Items.Add(""); lbbn.Items.Add(""); lbn.Items.Add(""); lbn.Items.Add(""); lbbn.Items.Add(""); lbtapmo.Items.Add(""); lbtapdong.Items.Add(""); #endregion Thread.Sleep(500); Application.DoEvents(); while (tapmo != null&&S!=int.MaxValue ) { fmin = float.MaxValue; tapmo.Remove(S); tapdong.Add(S); lbtapdong.Items.Add(S.ToString() + ": g = " + dsdinh[S].g_gs.ToString() + " , f = " + dsdinh[S].f_g().ToString() + " , cha(" + S.ToString() + ") = " + dsdinh[S].cha_gs.ToString()); lbn.Items.Add(S.ToString()); if (S != dinhcuoi) { foreach (int item in dsdinh[S].dinhke) { #region lap qua cac dinh if (tapdong.Contains(item) == false && tapmo.Contains(item) == false) { dsdinh[item].g_gs = dsdinh[S].g_gs + chiphithucte[S, item]; dsdinh[item].f_s(); dsdinh[item].cha_gs = S; tapmo.Add(item); lbbn.Items.Add(item.ToString() + ": g = " + dsdinh[item].g_gs.ToString() + " ,f = " + dsdinh[item].f_g().ToString() + " , cha(" + item.ToString() + ") = " + dsdinh[item].cha_gs.ToString()); lbtapmo.Items.Add(item.ToString() + ": g = " + dsdinh[item].g_gs.ToString() + " ,f = " + dsdinh[item].f_g().ToString() + " , cha(" + item.ToString() + ") = " + dsdinh[item].cha_gs.ToString()); lbtapdong.Items.Add(" "); lbn.Items.Add(" "); veduongdi(g, S, item, Color.Aqua, Color.Red); //gan fmin if (fmin > dsdinh[item].f_g()) fmin = dsdinh[item].f_g(); //xu ly thoi gian Thread.Sleep(500); Application.DoEvents(); } else if (tapmo.Contains(item) == true) { gtrunggian = dsdinh[item].g_gs; dsdinh[item].g_gs = dsdinh[S].g_gs + chiphithucte[S, item]; dsdinh[item].f_s(); if (gtrunggian > dsdinh[item].g_gs)//so sanh g de tim f min dsdinh[item].cha_gs = S;//doi cha else//tinh lai f neu g moi lon hon g cu { dsdinh[item].g_gs = gtrunggian; dsdinh[item].f_s(); } lbbn.Items.Add(item.ToString() + ": g = " + dsdinh[item].g_gs.ToString() + " ,f = " + dsdinh[item].f_g().ToString() + " , cha(" + item.ToString() + ") = " + dsdinh[item].cha_gs.ToString()); lbtapmo.Items.Add(item.ToString() + ": g = " + dsdinh[item].g_gs.ToString() + " ,f = " + dsdinh[item].f_g().ToString() + " , cha(" + item.ToString() + ") = " + dsdinh[item].cha_gs.ToString()); lbtapdong.Items.Add(" "); lbn.Items.Add(" "); veduongdi(g, S, item, Color.Aqua, Color.Red); if (fmin > dsdinh[item].f_g()) fmin = dsdinh[item].f_g(); Thread.Sleep(500); Application.DoEvents(); } #endregion } #region vet tap mo foreach (int item in tapmo) { if (!dsdinh[S].dinhke.Contains(item)) { lbbn.Items.Add(item.ToString() + ": g = " + dsdinh[item].g_gs.ToString() + " ,f = " + dsdinh[item].f_g().ToString() + " , cha(" + item.ToString() + ") = " + dsdinh[item].cha_gs.ToString()); lbtapmo.Items.Add(item.ToString() + ": g = " + dsdinh[item].g_gs.ToString() + " ,f = " + dsdinh[item].f_g().ToString() + " , cha(" + item.ToString() + ") = " + dsdinh[item].cha_gs.ToString()); lbn.Items.Add(""); lbtapdong.Items.Add(""); } } #endregion lbbn.Items.Add(""); lbtapmo.Items.Add(""); Thread.Sleep(500); Application.DoEvents(); } else { vedinh(g); lbtapmo.Items.Add(" "); lbbn.Items.Add(" "); //ve lai duong di toi uu cuoi cung while (S != dinhdau) { veduongdi(g, S, dsdinh[S].cha_gs, Color.Aqua, Color.Red); S = dsdinh[S].cha_gs; } return tapdong; } S = int.MaxValue; //tim dinh co fmin trong danh sach tap mo foreach (int item in tapmo) if (dsdinh[item].f_g() == fmin) S = item; #region ve lai mau tim cac duong da chon va mau den voi duong khong chon foreach (int item in tapmo) { if (item == S) veduongdi(g, tapdong[tapdong.Count - 1], S, Color.Aqua, Color.Purple); else { if(dsdinh[tapdong[tapdong.Count - 1]].dinhke.Contains(item)) veduongdi(g, tapdong[tapdong.Count - 1], item, Color.Black, Color.Black); } } #endregion } return tapdong; } public void naptoadodinh(Graphics g,string toado) { int chiso = 0; for (int i = 0; i < sodinh; i++) { dsdinh[i].toadodinh_gs(int.Parse(toado.Split(' ')[chiso]), int.Parse(toado.Split(' ')[chiso + 1]));//cat toa do dinh tu xau truyen vao chiso += 2; } vedinh(g); } private void vedinh(Graphics g) { //ve tat ca cac dinh for (int i = 0; i < sodinh; i++) { g.DrawEllipse(new Pen(Color.Black, 2), dsdinh[i].toadodinh.x, dsdinh[i].toadodinh.y, 20, 20); g.DrawString(i.ToString(), new Font("arial", 10), new SolidBrush(Color.Blue), dsdinh[i].toadodinh.x + 10, dsdinh[i].toadodinh.y - 20);//danh so } for (int i = 0; i < sodinh; i++) { foreach (int item in dsdinh[i].dinhke) { g.DrawLine(new Pen(Color.Black), dsdinh[i].toadodinh.x + 10, dsdinh[i].toadodinh.y + 10, dsdinh[item].toadodinh.x + 10, dsdinh[item].toadodinh.y + 10);//ve duong noi giua cac dinh } } } public void veduongdi(Graphics g,int diemdau,int diemcuoi,Color maudinh,Color mauduong) { g.DrawEllipse(new Pen(Color.Aqua, 2), dsdinh[diemdau].toadodinh.x, dsdinh[diemdau].toadodinh.y, 20, 20);//ve lai dinh dau duong di g.DrawEllipse(new Pen(maudinh, 2), dsdinh[diemcuoi].toadodinh.x, dsdinh[diemcuoi].toadodinh.y, 20, 20);//ve lai dinh cuoi duong di g.DrawLine(new Pen(mauduong, 2), dsdinh[diemdau].toadodinh.x + 10, dsdinh[diemdau].toadodinh.y + 10, dsdinh[diemcuoi].toadodinh.x + 10, dsdinh[diemcuoi].toadodinh.y + 10);//ve lai duong noi } } }