TAILIEUCHUNG - Thuật Toán Và Thuật Giải part 7

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. . Ví dụ minh họa hoạt động của thuật giải A* | 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. . 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. Hình Bảng đồ của Romania với khoảng cách đường tính theo km And Butbanl Ctakm DébMtt DMi FtfKM Hlnm M Lun 3H 0 100 M3 101 in 77 Dl 3M 344 MI Hmế 334 Ondn XO nnH 91 R-VLkn 193 Skill 333 ĨUmh 3 ŨriMd n VnU 199 Zml 374 Bảng 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 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ị E 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 E Sibiu g Sibiu h Sibiu 140 253 393 Cha Sibiu Arad h Timisoara 329 g Timisoara g Arad cost Arad Timisoara 0 118 118 E Timisoara g Timisoara h Timisoara 118 329 447 Cha Timisoara Arad h Zerind 374 g .

• Kỹ thuật lập trình
• máy tính
• mạng máy tính
• internet
• phần mềm
• ứng dụng
• lập trình
• dữ liệu
• SQL
• PHP
• AutoIT
• Phần cứng máy tính
• lắp ráp máy tính
• sửa chữa máy tính
• lỗi máy tính
• hệ thống mạch máy tính
• điện máy tính
• Tài liệu máy tính