用全局擇優(yōu)搜索法求解重排九宮問題,設(shè)初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如下: 估價(jià)函數(shù)定義:f(x)=d(x)+h1(x),其中d(x)表示結(jié)點(diǎn)x的深度,h1(x)表示結(jié)點(diǎn)x中的數(shù)字位置和目標(biāo)結(jié)點(diǎn)中不相同的數(shù)字個(gè)數(shù)。例如:
全局擇優(yōu)搜索樹如下圖所示:
推銷員旅行問題。設(shè)有5個(gè)相互可直達(dá)的城市A、B、C、D、E,如下圖所示,各城市間的交通費(fèi)用已在圖中標(biāo)出。推銷員從城市A出發(fā),去每個(gè)城市各旅行一次,最后到達(dá)城市E。
代價(jià)樹如下圖: