物流工程的路徑規(guī)劃(編輯修改稿)
2025-02-08 14:15 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 若節(jié)點(diǎn) n’存在于 CLOSED中 ， 則把它返回到 OPEN后， 再計(jì)算值 f(n’)=g(n’)+h(n’)。 路徑規(guī)劃 ⑥ 返回到 ② 算法 A*(A)的程序流程 路徑規(guī)劃 ? 估計(jì)值 h比真值 h*小或相等時(shí) ， 上述的算法 變?yōu)?A*， 可選出從起始節(jié)點(diǎn) ns到目標(biāo)節(jié)點(diǎn) ng的 最佳路徑 (總計(jì)費(fèi)用最小的路徑 )。 ? 若估計(jì)值 h比真值大 ， h*算法則變?yōu)?A， 可選出從起始節(jié)點(diǎn) ns到目標(biāo)節(jié)點(diǎn) ng的滿足要求的路徑 (總計(jì)費(fèi)用不是最小的路徑 )。 ? 因此 ， 機(jī)器人的路徑規(guī)劃多用從當(dāng)前地點(diǎn) ( , , )到目的地 ( , )的平方范數(shù) 路徑規(guī)劃 定義估計(jì)值 。 這個(gè)估計(jì)值 h常常比 h*小 ，成為算法 A*， 用它可選擇最佳路徑 。 圖 720的搜索圖 G存在估計(jì)值 h(在節(jié)點(diǎn)上用括號(hào)給出 )比真值 h*大的節(jié)點(diǎn) 。 例如 ， 節(jié)點(diǎn) A和H的估計(jì)值 h是 8和 4， 但到達(dá)目的地的最小真值是 7和 2。 由于這個(gè)費(fèi)用評(píng)價(jià)過(guò)大 ， 存在于最短路徑上的節(jié)點(diǎn) H等可以忽略 ， 算法錯(cuò)過(guò)了費(fèi)用 8的最佳路徑 ， 最終得到費(fèi)用 9的滿足要求的路徑 。 路徑規(guī)劃 E D F G H I B C A S (7) 3 2 (5) (5) (5) (3) (8) (1) (4) (3) 2 2 1 3 3 2 3 2 2 4 4 1 圖 720 搜索圖 G(有的地方估計(jì)值比真值大 ) D （ 9 ） S （ 7 ） S ( 7 ) A ( 10 )) B(8 ) ( a ) ( b) S （ 7 ） A ( 10 ） B （ 8 ） D （ 9 ） E （ 8 ） C （ 8 ） F （ 10 ） H ( 10 ) I(1 0) G (9 ) ( e ) A ( 10 )) D (9 ) F (1 0) E (8 ) S （ 7 ） S （ 8 ） ( c ) E （ 8 ） B （ 8 ） A ( 10 ) F (1 0) H ( 10 ) ( d) 屬于 O P E N 表的節(jié)點(diǎn) 屬于 C L O S E 表的節(jié) 點(diǎn) S ( 7 ) 路徑規(guī)劃 A、起始節(jié)點(diǎn) S被代入 OPEN[圖 721(a)]，子節(jié)點(diǎn) A和 B被代人 OPEN[圖 721(b)]。起始節(jié)點(diǎn) S擴(kuò)展后移到 CLOSED， B、由于節(jié)點(diǎn) A、 B的評(píng)價(jià)值分別為 8，所以選中擴(kuò)展節(jié)點(diǎn) B 。 B的子節(jié)點(diǎn) D、 E、 F， 評(píng)價(jià)值分別為 10，全都代人 OPEN，擴(kuò)展后節(jié)點(diǎn) B被移到 CLOSED[圖 721(c)]。 C、節(jié)點(diǎn) E評(píng)價(jià)值最小，選中擴(kuò)展節(jié)點(diǎn) E。 E的子節(jié)點(diǎn) H同評(píng)價(jià)值 10都代入 OPEN，擴(kuò)展后節(jié)點(diǎn) E被移到 CLOSED。 路徑規(guī)劃 D、 OPEN中 當(dāng)前評(píng)價(jià)值最小的子節(jié)點(diǎn)是 D， 所以選中節(jié)點(diǎn) D。 D的子節(jié)點(diǎn) H被再次搜索 ， 節(jié)點(diǎn) D被移到 CLOSED。 注意到節(jié)點(diǎn) H的值 g，由于過(guò)去的費(fèi)用 6(經(jīng)由節(jié)點(diǎn) E、 B返回到節(jié)點(diǎn) S)比新的費(fèi)用 7(經(jīng)由節(jié)點(diǎn) D、 B返回到 S)小，所以不更換指針 [圖 721(d)]。指針仍在 E。 由于當(dāng)前 OPEN上存在評(píng)價(jià)值 f都為 10的三個(gè)節(jié)點(diǎn) A、 H、 F，此時(shí)須對(duì)這三個(gè)節(jié)點(diǎn)A、 H、 F都分別向下擴(kuò)展。 路徑規(guī)劃 E、用中斷連接節(jié)點(diǎn) A，擴(kuò)展節(jié)點(diǎn) C同評(píng)價(jià)值 8都代人 OPEN，節(jié)點(diǎn) A被移到 CLOSED。然后， C的兩個(gè)擴(kuò)展節(jié)點(diǎn) I、 H中， 選中 值 f最小的節(jié)點(diǎn) I （實(shí)際上， ACH路徑在先已經(jīng)被否定），節(jié)點(diǎn) I同評(píng)價(jià)值 10都代人 OPEN，節(jié)點(diǎn)C同評(píng)價(jià)值 8都 被
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1