KöMaL - Középiskolai Matematikai és Fizikai Lapok
Belépés
Regisztráció
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum
Versenykiírás
Tudnivalók
Nevezési lap
Feladatok
Eredmények
Korábbi évek
Arcképcsarnok
Munkafüzet

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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ő.

Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley