Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

Az S. 34. feladat (2008. március)

S. 34. Bergengócia királya elérkezettnek látja az időt, hogy férjhez adja leányát, ezért legjobb építészével egy sárkányokkal teli labirintust terveztet. A királylány kezét csak az a lovag nyerheti el, aki ennek egyik bejáratán belépve sikeresen kijut bármelyik másik bejáraton. A király parancsa szerint olyan labirintust kell tervezni, hogy a lovag bármelyik kijáratot is választja, útközben legalább bizonyos számú sárkányfejet le kell vágnia.

Ilyen fontos döntés esetén a király még leghűségesebb embereiben sem bízhat. Így minket kért meg, hogy írjunk programot, mely ellenőrzi, hogy az építész által elkészített labirintusterv teljesíti-e a kívánalmakat.

A program az alaprajzot fájlból olvassa, az eredményt fájlba írja. A bemeneti, illetve kimeneti fájlok nevei az első, illetve második parancssori argumentumok.

A bemenet első sorában szóközzel elválasztva W, H és F, a labirintus szélessége, magassága és a levágandó sárkányfejek minimális F száma szerepel (3\leW,H\le100). Az ezt követő H sor mindegyike W karaktert tartalmaz, mely:

szóköz, ha az adott mező folyosó, melyről tetszőleges szomszédos folyosóra lehet lépni

J, B, F és L, ha az adott mező folyosó, és egy olyan kapu van rajta, melynek hatására a mezőről jobbra, balra, fel vagy lefelé nem lehet lépni

*, ha a mező fal

N=1-9 számjegy, ha a mező folyosó és rajta egy N-fejű sárkány rejtőzik, melyet a mezőre lépve mindenképp le kell győzni.

Bejáratnak a labirintus szélén lévő folyosókat tekintjük, amelyekről feltehetjük, hogy mindig üresek lesznek, illetve legalább 1 fal határolja őket.

A kimenet egyetlen sora K\ A\ B alakban három, szóközzel elválasztott számot tartalmazzon: ha a terv helyes, mindhárom érték legyen 0, egyébként egy olyan A bejárattól B kijáratig vezető útvonal leírása, mely során csak K (K<F) sárkányfejet kell levágnunk. A bejáratokat a bal felső saroktól kezdődően az óramutató járásával megegyezően, 1-től kezdve számozzuk, több megoldás esetén a legkisebb K, majd ezen belül a legkisebb A, majd B értékűt írjuk ki.

Beküldendő a program forráskódja (s34.pas, s34.cpp, ...), valamint a program rövid dokumentációja (s34.txt, s34.pdf, ...), amely tartalmazza a megoldás vázlatos leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2008. április 15-én LEJÁRT.


Első lépes

Egy programozási/algoritmizálási feladat megoldásának első lépése mindig az absztrakció: azért, hogy a megoldás során valóban a feladatra tudjunk koncentrálni, célszerű a feladat szövegében megjelenő érdektelen részletektől elvonatkoztatni, csak a lényeget kiemelni. Esetünkben a probléma érdemi részét remekül lefordíthatjuk a gráfok nyelvére. A labirintushoz rendeljünk hozzá egy G=\left(V,E\right) súlyozott irányított gráfot a következő módon: a gráf V csúcsai az egyes mezőknek feleljenek meg, élek pedig a szomszédos mezőknek megfelelő csúcsok között fussanak. Az a\inV-ból b\inV csúcsba futó e\inE él c\left(e\right)súlya a-ból b-be jutáshoz levágandó sárkányfejek számát jelölje, azaz a következő legyen: ha b fal, vagy a-ról nem lehet rálépni (kapu miatt), akkor a súly legyen végtelen, egyébként pedig egyezzen meg a b mezőn lévő sárkányfejek számával (ez lehet zérus is). Ezen kívül jelölje d(v,w) a v és w csúcsok közti legrövidebb út hosszát, illetve i(w) egy w bejárati csúcs sorszámát.

Az így kapott gráfban egy A-adik bejárattól B-edikig vezető, K sárkányfej levágását igénylő útvonal a gráfban egy K költségű, a megfelelő csúcsok között futó útnak felel meg. A feladatot pedig a következőképpen fogalmazhatjuk meg: adjuk meg a gráfban a legrövidebb, bejárati csúcsok között vezető x\rightarrowy irányított utat. A megadás az út végpontjainak A=i\left(x\right), B=i\left(y\right) sorszámával, illetve az út K=d\left(x,y\right) hosszával történjen. Több legrövidebb út esetén a legkisebb A, majd B értékűt adjuk meg, ezt a továbbiakban az optimális megoldásnak fogjuk nevezni.

A továbbiakban fontos lesz fejben tartani, hogy az optimális megoldás megadásához lényegében nem mást teszünk, mint az összes bejáratok között futó összes utakat leíró összes \left(K',A',B'\right) számhármasok halmazából kiválasztjuk a legjobbat, azaz a legkisebb K', majd A', majd B' értékűt. A hangsúly azon van, hogy e exponenciális méretű halmaz elemeiből minél kevesebbet kelljen egyáltalán számba vennünk, az optimum kiválasztásához.

Első megközelítés

Kézenfekvő ötlet, hogy minden bejáratból indítunk egy legrövidebbút-keresést az összes többi pontba - például Dijkstra algoritmusával. Ugyanakkor ezzel rengeteg felesleges munkát végzünk: csupán azt szeretnénk tudni ugyanis, hogy F-nél rövidebb út létezik-e egyáltalán egy bejáratból egy másikba, az számunkra teljességgel érdektelen, hogy mindenféle bejáratokból mindenféle pontokba mekkora a legrövidebb utak hossza. Dijkstra algoritmusának futásideje O\left(\left(n+e\right)logn\right), ahol n a gráf csúcsainak, e pedig éleinek a száma, mely utóbbi esetünkben a négyzetháló-topológia miatt n-nel arányos. Mivel az algoritmust minden bejáratra lefuttatjuk, melyből (a oldalhosszú négyzetalakú labirintust feltételezve) O\left(a\right) van, az így kapott algoritmus műveletigénye O\left(a\left(a^{2}+a^{2}\right)loga^{2}\right)=O\left(a^{3}loga\right).

Hasonló módon rengeteg felesleges munkát végeznénk, ha például Warshall algoritmusával meghatároznánk minden pontpárok között a legrövidebb utak hosszát.

Egy hatékony megoldás irányítatlan gráfokra

Az egyszerűség kedvéért oldjuk meg először az előbbi irányítottgráf-modellre felírt problémát egy irányítatlan gráfra, majd ezután terjesszük ki az algoritmust az irányított esetre! Fontos megjegyezni, hogy az irányítatlan gráf már nem modellezi az eredeti feladatot, hiszen például a kapukat sehogyan sem tudjuk reprezentálni. A tárgyalás érdekében azonban mindenképp érdemes bevezetni ezt a további - ha úgy tetszik - veszteséges absztrakciót.

Alkalmazzuk az első bekezdésben bevezett jelöléseket! Bejáratoknak továbbra is a gráf csúcsainak egy adott részhalmazát tekintsük, illetve ahogyan már tárgyaltuk, több megoldás esetén pedig az optimálisnak pedig azt az, melynél az A\neqB értékek a lehető legkisebbek. A két végpont sorrendje most viszont az irányítatlanság miatt érdektelen. Vezessük még be a következőket: jelölje b\left(v\right) a v csúcshoz legközeleb eső bejárati csúcsot (több, azonos távolságra lévő bejárat esetén a legkisebb sorszámút), \dot{d}\left(v\right)=d\left(v,b\left(v\right)\right) pedig v ettől vett távolságát. A w bejárati csúcsokra legyen definíció szerint b\left(w\right)=w.

Tegyük fel, hogy valamilyen módon a b és \dot{d} értékeket már minden csúcsra kiszámoltuk (a d értékeket csak a bizonyításhoz használjuk, a megoldás kiszámításához nem szükségesek). Tegyük fel, hogy az optimális megoldás az A=i\left(x\right) sorszámú x bejárati csúcsból a B=i\left(y\right) sorszámú y-ba érkezik, és K=d\left(x,y\right) költségű!

Lemma 1. Az optimális út minden v csúcsára b\left(v\right)=x vagy b\left(v\right)=y.

Biz. A végpontokra az állítás bejárati csúcs voltuk miatt áll. Egy közbülső v pontra tegyük fel, hogy b\left(v\right)=z\neq x,y. Ez vagy akkor áll fenn, ha d(v,z)<min\left\{ d(v,x),d(v,y)\right\} vagy pedig ha d(v,z)=min\left\{ d(v,x),d(v,y)\right\} de az i\left(z\right) sorszáma kisebb. Ekkor x,y közül bármelyik bejáratot lecserélve z-re az első esetben egy rövidebb, a második esetben pedig egy alacsonyabb bejárati sorszámú, tehát mindkét esetben egy jobb utat kapnánk, ami ellentmond annak a feltételnek, hogy az eredeti út optimális.

Lemma 2. Az optimális útnak van olyan \left\{ v,w\right\} éle, hogy b(v)=x és b(w)=y. Ezekre az élekre c\left(v,w\right)+d(v,x)+d(w,y)=d\left(x,y\right).

Biz. Mivel az út csúcsainak b-értéke az 1. lemma miatt csak x vagy y lehet, és a végpontok b-értékei különböznek, biztosan van egy ilyen él. A második állítás pedig azért igaz, mivel a bal oldalon is az x-y út hossza szerepel, csak három szakaszra (x-v,v-w,w-y) egyenként összegezve.

A 2. lemma állítását felhasználva azonnal konstruálhatunk is egy algoritmust a feladat megoldására. Vegyük ugyanis sorra a gráf éleit, és minden \left\{ v,w\right\} élre képezzük az adott élen áthaladó utat leíró \left(K',A',B'\right) számhármast a következő módon:

A'=i\left(b\left(v\right)\right)

B'=i\left(b\left(w\right)\right)

K'=c\left(v,w\right)+\dot{d}(v)+\dot{d}(w)

Az így képzett legális (A'\neqB') számhármasokat mint potenciális megoldásokat jegyezzük meg, majd közülük válasszuk ki a legjobbat, azaz a legkiseb K', majd A', majd B' értékűt. Az így kapott számhármas épp az optimális megoldást írja, hiszen a 2. lemma miatt a gráf tartalmazott legalább 1 olyan \left\{ v,w\right\} élet, melyre:

b(v)=x, így A'=i\left(b\left(v\right)\right)=i\left(x\right)

b(w)=y, így B'=i\left(b\left(w\right)\right)=i\left(y\right)

c\left(v,w\right)+d(v,x)+d(w,y)=d\left(x,y\right), így K'=c\left(v,w\right)+\dot{d}(v)+\dot{d}(w)=c\left(v,w\right)+d(v,x)+d(w,y)=d\left(x,y\right)

Azaz az ebből az élből képzett \left(K',A',B'\right) hármas épp az optimális megoldást leíró \left(K=d\left(x,y\right),A=i\left(x\right),B=i\left(y\right)\right) hármassal egyezik meg, azaz a potenciális megoldások között az optimális megoldás is szerepelt, így amikor közülük a legjobbat kiválasztottuk, az épp az optimális megoldás volt.

Már csak a b-értékek, illetve az egyes pontok legközelebbi bejárattól vett \dot{d}\left(v\right)=d\left(v,b\left(v\right)\right) távolságértékeinek a meghatározása maradt hátra. A bejárati csúcsokra \dot{d}\left(w\right)=0 és b\left(w\right)=w . Ezután pedig Dijkstra algoritmusának egyszeri lefuttatásával megkaphatjuk a két értéket az összes többi pontra (a legrövidebbút-keresést az összes bejárati csúcsból egyszerre indítva, a b-értékeket a minimumot adó őstől másolva).

A megoldás kiterjesztése irányított gráfokra

Irányított élek esetén mindössze annyi változik, hogy mind a \dot{d}, mind pedig a b értékekből két készletünk van: az egyik arra vonatkozik, amikor az élek irányításának megfelelően haladunk (b_{e},\dot{d}_{e}), a másik pedig az irányítással ellentétes haladásra (b_{v},\dot{d}_{v}). Kiszámításuk külön-külön, az előző bekezdésben leírt módon történik, tehát összesen 2 db legrövidebút-keresésre van szükségünk. Az éleket sorban megnézve a \left(v,w\right) irányított él a következő potenciális megoldást adja:

A'=i\left(b_{v}\left(v\right)\right)

B'=i\left(b_{e}\left(w\right)\right)

K'=c\left(v,w\right)+\dot{d}_{v}(v)+\dot{d}_{e}(w)=c\left(v,w\right)+d_{v}(v,x)+d_{e}(w,y)

Az optimális megoldást itt is a potenciális megoldásokat leíró számhármasok közül a legjobbat választva kapjuk.

A algoritmus műveletigénye általános esetben O\left(e+\left(n+e\right)logn\right), mivel konstans számú (2 db) legrövidebbút-keresést hajtunk végre, illetve egyszer végiglépkedünk az összes élen. Esetünkben a gráf kötött felépítése miatt a műveletigény O\left(a^{2}+\left(a^{2}+a^{2}\right)loga^{2}\right)=O\left(a^{2}loga\right), ami felhasználva, hogy az élsúlyok egy kis elemszámú halmazból származnak (0...9, ha végtelen súly esetén az élet kitöröljük) Dijkstra algoritmusának mozgókupacos megvalósításával O\left(a^{2}\right)-re csökkenthető, azaz a feladat meglepő módon a mezők számával egyenesen arányos időben megoldható.

Engedy Balázs


Statisztika:

5 dolgozat érkezett.
7 pontot kapott:2 versenyző.
5 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.

A KöMaL 2008. márciusi informatika feladatai