NézetNyomtat

3. óra
Címkék > Óra

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.
A vázlatos algoritmus:

 inicializálás
   (üres mezők, 0-ák és 1-ek)
 n := 1
 Ciklus
    szürke mezők meghatározása
    új mezők számozása: ( n + 1 )
    n := n + 1
 amíg volt új mező
 kiírás