3. óra
Az előző óra
Üldözés feladatát
oldjuk meg, most már a matematikai
levezetés alapján. Most azt adjuk meg, hogy egy végtelen pályán melyek az
"elkapási mezők", de ebből könnyen kapunk választ a véges táblákra is.
Rufus Isaacs: Differential Games című könyvének megoldását beszéltük meg.
Az alapötlet a következő: rögzítsük a koordinátarendszert a rendőrautóhoz. Ekkor ábrázolhatjuk úgy a lépéseket, mintha mindkét fél a bünözők autóját mozgatná.
Ha a bűnözők autója a $B(x;y)$ mezőn áll, akkor a rendőrautó előre lépése
a bűnözőket a $B'(x;y-2)$ pontba juttatja.
Ha pedig jobbra fordul a rendőr, akkor $B'(-y;x-2)$ pontba kerülnek a menekülők.
Ezután az algoritmus a következő: Minden mezőre beírjuk, hogy ha onnan indul a bűnözők autója, akkor hány lépés kell a rendőröknek az elfogáshoz. Kezdetben a 0-kat és az 1-eket
tudjuk beírni.
Ezután megkeressük azokat a mezőket, amelyeknek mind a 4 szomszédja számozott. Ez lesz a szürke tartomány. A rendőrautó mindkét lehetséges lépésére megnézzük, hogy mely számozatlan mezőket "húzunk be" a szürke tartományba. Ezek a mezők kapják a következő még ki nem osztott számot.
Addig futtatjuk ezt a lépést, amíg legalább egy új mezőt beszámozunk vele.
Ezután megkeressük azokat a mezőket, amelyeknek mind a 4 szomszédja számozott. Ez lesz a szürke tartomány. A rendőrautó mindkét lehetséges lépésére megnézzük, hogy mely számozatlan mezőket "húzunk be" a szürke tartományba. Ezek a mezők kapják a következő még ki nem osztott számot.
Addig futtatjuk ezt a lépést, amíg legalább egy új mezőt beszámozunk vele.
A vázlatos algoritmus: