Đang chuẩn bị liên kết để tải về tài liệu:
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ả | 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ố. -646 417 617 413 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 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. 30 Sưu tầm bởi www.daihoc.com.vn 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 .