<prompt> Tumia utafutaji wa Heuristic kutafuta njia ambayo PacMan inapaswa kupita ili kufikia nodi ya lengo.  <response>: Kanuni za utafutaji za Heuristic hutumia maarifa mahususi ya tatizo zaidi ya ufafanuzi wa tatizo lenyewe ili kupata suluhu kwa ufanisi zaidi kuliko algoriti za kawaida za utafutaji ambazo hazijaarifiwa. Mojawapo ya algoriti ya utaftaji ya kawaida inaitwa algoriti ya A. Nitatumia algorithm hii kupata njia ambayo PacMan inapaswa kuchukua ili kufikia nodi ya lengo. Kwanza, tunahitaji kufafanua kazi yetu ya heuristic. Chaguo la kawaida kwa utaftaji wa msingi wa gridi ni umbali wa Manhattan, ambao hupima umbali kati ya nukta mbili kwenye gridi ya taifa kulingana na njia iliyo mlalo na wima. Kwa chaguo hili la kukokotoa la kiheuristic, makadirio ya umbali kati ya nukta n na pointi ya lengo g, inayoashiria hn, ni absnx - gx absny - gy, ambapo nx na ny ni viwianishi vya x na y vya nukta n, na gx na gy ni viwianishi vya x na y vya nukta ya lengo g. Kanuni ya A hudumisha orodha mbili: orodha wazi na orodha iliyofungwa. Orodha iliyo wazi ina nodi ambazo zinazingatiwa kwa uchunguzi, wakati orodha iliyofungwa ina nodi ambazo tayari zimegunduliwa. Hapo awali, orodha iliyo wazi ina node ya kuanzia tu, na orodha iliyofungwa haina tupu. Kisha kanuni huingiza kitanzi, ambapo kwa kila marudio, huchagua nodi katika orodha iliyo wazi yenye makadirio ya gharama ya chini kabisa fn gn hn , ambapo gn ni gharama halisi ya njia kutoka nodi ya kuanzia hadi nodi n. Nodi hii huondolewa kwenye orodha iliyo wazi, kuongezwa kwenye orodha iliyofungwa, na kupanuliwa kwa kuzalisha majirani zake kwenye gridi ya taifa. Kwa kila jirani m ya nodi n, ikiwa m haipo kwenye orodha iliyofungwa na haijazuiwa, tunakokotoa alama yake ya g ya muda kama gm gn cn , m, ambapo cn, m ni gharama ya kuhamisha kutoka nodi n hadi nodi m, ambayo kwa kawaida ni sawa na 1 katika gridi ya taifa. Ikiwa m haipo katika orodha iliyo wazi, au ikiwa alama g yake ya muda ni ya chini kuliko alama yake ya sasa ya g, tunaweka alama yake g kwa alama ya g ya muda na kuweka mzazi wake kwenye nodi . n, na uiongeze kwenye orodha iliyo wazi. Algorithm inaendelea mchakato huu hadi nodi ya lengo iongezwe kwa 