# A* và Nhánh cận
#### **Đề bài**: Tìm đường đi A -> B bằng thuật toán tìm kiếm A* và nhánh cận

## Thuật toán tìm kiếm A*

| <div style="width:41px">Bước</div> | <div style="width:25px">u</div> | <div style="width:115px">Kề u</div> | <div style="width:125px">g(v)</div> | <div style="width:125px">f(u)</div> | <div style="width:125px">OPEN</div> |
|:----------------------------------:|:-------------------------------:|:-----------------------------------:|:-----------------------------------:|:-----------------------------------:|:-----------------------------------:|
| 0 | | | | | A~0~ |
| 1 | A~0~ | D^6^, F^7^ | g(D) = 7 <br> g(F) = 20 | f(D) = 13 <br>f(F) = 27 | D~13~, F~27~ |
| 2 | D~13~ | H^10^, E^8^ | g(H) = 15 <br> g(E) = 11 | f(H) = 25 <br>f(E) = 19 | E~19~, H~25~, F~27~ |
| 3 | E~19~ | K^2^, I^4^ | g(K) = 15 <br> g(I) = 14 | f(K) = 17 <br>f(F) = 18 | K~17~, I~18~, H~25~, F~27~ |
| 4 | K~17~ | B^0^ | g(B) = 21 | f(B) = 21 | I~18~, B~21~, H~25~, F~27~ |
| 5 | I~18~ | B^0^ | g(B) = 19 | f(B) = 19 | B~19~, B~21~, H~25~, F~27~ |
| 6 | B~19~ | **Đích** | | | |

**Chú thích:**
> Số mũ trên là chỉ số của đỉnh
> Số mũ ở dưới là tổng chi phí đi từ đỉnh A tới đỉnh đó

**Đường đi** **:** **A -> D -> E -> I -> B**

## Thuật toán tìm kiếm nhánh cận

| <div style="width:41px">Bước</div> | <div style="width:25px">u</div> | <div style="width:115px">Kề u</div> | <div style="width:75px">g(v)</div> | <div style="width:75px">f(u)</div> | <div style="width:90px">L</div> | <div style="width:160px">OPEN</div> | <div style="width:30px">min</div> |
|:----------------------------------:|:-------------------------------:|:-----------------------------------:|:---------------------------------------:|:---------------------------------------:|:-------------------------------:|:-----------------------------------:|:---------------------------------:|
| 0 | | | | | | A~0~ | +$\infty$ |
| 1 | A~0~ | D^6^, F^7^ | g(D) = 7 <br> g(F) = 20 | f(D) = 13 <br>f(F) = 27 | D~13~, F~27~ | D~13~, F~27~ | +$\infty$ |
| 2 | D~13~ | H^10^, E^8^ | g(H) = 15 <br> g(E) = 11 | f(H) = 25 <br>f(E) = 19 | E~19~, H~25~ | E~19~, H~25~, F~27~ | +$\infty$ |
| 3 | E~19~ | K^2^, I^4^ | g(K) = 15 <br> g(I) = 14 | f(K) = 17 <br>f(I) = 18 | K~17~, I~18~ | K~17~, I~18~, H~25~, F~27~ | +$\infty$ |
| 4 | K~17~ | B^0^ | g(B) = 21 | f(B) = 21 | B~21~ | B~21~ ,I~18~, H~25~, F~27~ | +$\infty$ |
| 5 | B~21~ | **Đích** | | | | I~18~, H~25~, F~27~ | 21 |
| 6 | I~18~ | K^2^, F^7^, B^0^ | g(K) = 23 <br> g(F) = 20 <br> g(B) = 19 | f(K) = 25 <br> f(F) = 27 <br> f(B) = 19 | B~19~, K~25~, F~27~ | B~19~, K~25~, F~27~, H~25~, F~27~ | 21 |
| 7 | B~19~ | **Đích** | | | | K~25~, F~27~, H~25~, F~27~ | 19 |
| 8 | K~25~ | 25 > 19 => **Cắt** | | | | F~27~, H~25~, F~27~ | 19 |
| 9 | F~27~ | 27 > 19 => **Cắt** | | | | H~25~, F~27~ | 19 |
| 10 | H~25~ | 25 > 19 => **Cắt** | | | | F~27~ | 19 |
| 11 | F~27~ | 27 > 19 => **Cắt** | | | | Rỗng => **Stop** | 19 |

**Chú thích:**
> Số mũ trên là chỉ số của đỉnh
> Số mũ ở dưới là tổng chi phí đi từ đỉnh A tới đỉnh đó

**Đường đi** **:** **A -> D -> E -> I -> B**