1.6 Lập trình cấu trúc dữ liệu và giải thuật  (Page 14/46)

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)}

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’(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