對(duì)一個(gè)有向圖，要找到從起始到終點(diǎn)的一條路徑，既可以用圖搜索脱羡，也可以用樹搜索
- 圖搜索不允許重復(fù)訪問結(jié)點(diǎn)，即OPEN表 ∩ CLOSED表 = ?免都，此處重復(fù)的結(jié)點(diǎn)不一定是父節(jié)點(diǎn)锉罐。
- 樹搜索允許重復(fù)訪問結(jié)點(diǎn)。
下面以A* 搜索為例绕娘，分別解釋圖搜索和樹搜索脓规。
例子
A* 樹搜索
允許重復(fù)訪問結(jié)點(diǎn)
| 擴(kuò)展路徑 | 拓展但未經(jīng)過的路徑 |
|---|---|
| S | S-A(2+0); S-B(1+6); S-G(9+0) |
| S-A | S-A-D(5+1); S-B(1+6); S-A-C(4+4); S-G(9+0) |
| S-A-D | S-B(1+6); S-A-C(4+4); S-G(9+0); S-A-D-G(9+0) |
| S-B | S-B-D(3+1); S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
| S-B-D | S-B-D-G(7+0); S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
| S-B-D-G | S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
A* 圖搜索
不允許重復(fù)訪問結(jié)點(diǎn)，設(shè)置了CLOSED表
| 擴(kuò)展路徑 | CLOSED表 | 拓展但未經(jīng)過的路徑 |
|---|---|---|
| S | S | S-A(2+0); S-B(1+6); S-G(9+0) |
| S-A | S A | S-A-D(5+1); S-B(1+6); S-A-C(4+4); S-G(9+0) |
| S-A-D | S A D | S-B(1+6);S-A-C(4+4); S-G(9+0); S-A-D-G(9+0) |
| S-B | S A D B | S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
| S-A-C | S A D B C | S-A-C-G(8+0); S-G(9+0);S-A-D-G(9+0); S-B-E(5+10) |
| S-A-C-G | S A D B C G | S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
