tailieunhanh - Programming HandBook part 163

Tham khảo tài liệu 'programming handbook part 163', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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 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 E 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 Arad jituu Timisoara r 140 253 f l 18 329 447 393 Zeiind f 75 374 449 Hình 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 193 g g Sibiu cost Sibiu 140 80 220 f g h 220 193 413 Nút Arad đã có trong CLOSE. Tuy nhiên do g Arad mới được tạo ra có giá .