---
# System prepended metadata

title: BTVN A* và nhánh cận

---

# 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
![](https://hackmd.io/_uploads/SkPORkj16.png)


## 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**