Az S. 26. feladat (2007. április)

S. 26. A Kincsfelderítő és -kiásó Intézet (KFKI) munkatársai régi kincsestérképeket és a modern technika legújabb vívmányait ötvözve végzik rég eltemetett értéktárgyak felszínre hozatalát.

Az intézet sokéves tapasztalata azt mutatja, hogy a kincsek java része karszthegységekben kerül elásásra, amelyek kemény kőzetében azonban barlangok találhatók. Ezek néhány kisebb-nagyobb, gömb alakúnak tekinthető - akár egymásba lógó - üregből állnak. A fúrás során e barlangokba lyukadva az a barlang tetszőleges másik pontjából folytatható, ily módon a ténylegesen fúrandó távolság lerövidíthető.

Írjunk programot, amely a terep szerkezetének ismeretében meghatározza, hogy a kincs kiásásához - az üregeket is kihasználva - optimális esetben mennyit kell fúrni és a fúrást a felszín mely pontjából kell indítani.

A program a kincs helyzetét és az üregek elhelyezkedését a standard bemenetről olvassa. A bemenet első sora az üregek N (0N1000) számát és a vízszintes síknak tekinthető felszín tengerszint feletti Y_f magasságát tartalmazza. A második sor a kincs X_k, Y_k, Z_k koordinátáit, az ezt követő N sor pedig X_i, Y_i, Z_i, R_i alakban a földalatti üregeket írja le, ahol X_i, Y_i, Z_i az i-edik üreg középpontjának koordinátái, R_i pedig az üreg sugara. Feltehetjük, hogy minden üreg teljes egészében a föld alatt van.

A program az eredményt a standard kimenetre írja. Ennek egyetlen sora négy, tizedes tört alakban, legalább két tizedes pontossággal megadott számot tartalmazzon: a furat kezdőpozíciójának X, Y, Z koordinátáit és a minimálisan fúrandó L távolságot.

Beküldendő a program forráskódja (S26.pas, S26.cpp, ).

(10 pont)

A beküldési határidő 2007. május 15-én LEJÁRT.

A megoldás részletes menete

A feladat megoldásához elemezzük egy optimális fúrási nyomvonal szerkezetét! Ez a felszín egy pontjából indul, olykor-olykor egy üregbe lyukad ki és annak valamely másik pontjából halad tovább, végül pedig a kincsben végződik.

Nyilvánvaló, hogy két üreg között nincs értelme görbevonal mentén haladni, tehát a nyomvonal üregek közötti egyenes szakaszokból épül fel. Szintén könnyen látható, hogy egy üregből úgy juthatunk egy másikba a legkevesebb fúrással, ha egy olyan egyenes mentén haladunk, amely átmegy mindkét üreg középpontján.

Hasonlóan a felszínről az első üregbe is a felszínre merőleges, az üreg középpontján átmenő egyenes mentén juthatunk a legkevesebb fúrással.

Láthatjuk tehát, hogy az optimális nyomvonal szerkezete rendkívül kötött: üregből üregbe haladunk - a fentiek szerint - jól meghatározott hosszúságú egyenes szakaszokon. Azaz az üregek egy tetszőleges sorrendjéhez pontosan egy legrövidebb nyomvonal van, és ennek a hosszát is könnyen kiszámíthatjuk. Feladatunk tehát egy olyan üregsorrend megtalálása, amelyre ez a hossz minimális.

Ha az üregeket egy olyan gráf csúcsainak képzeljük el, hogy bármely két csúcs között fut él, és ezen élekre - élsúlyként - a két üreg közti átjutáshoz szükséges fúrandó távolságot írjuk, a probléma egy legrövidebbút-kereséssel modellezhető. Ugyanis feladatunk nem más, mint egy olyan üregsorrend (azaz csúcsok egy sorrendje, egy út) megtalálása, amely esetén a sorrendben szomszédos üregek közti fúrandó távolságok (az egymás utáni csúcsokat összekötő élek súlyai), illetve a felszínről az első, és az utolsó üregből a kincsbe vezető szakaszok hosszainak összege minimális.

Fontos megemlíteni, hogy a gráf felépítésénél az üregek közti távolságok meghatározása egy egyszerű heurisztikával történhet: elegendő középpontjaik távolságából sugaraikat kivonni, nem kell törődni azzal, hogy más üreg belelóg-e az ehhez tartozó legrövidebb nyomvonalba. Így egyes esetekben felülbecsüljük a távolságot, ami viszont nem baj, hisz, a feladat elején megkezdett gondolatmenet folytatva, ha nem közvetlenül, hanem az útban lévő üreget is középpontosan útba ejtve haladunk, még az előbb felmerülő ténylegesnél is kisebb távolságot kell fúrni, tehát a túlbecsült távolság nem fog részt venni az optimum alakításában.

Mivel az összes élsúly nemnegatív, és az esetlegesen felülbecsült távolságú élek nem játszanak szerepet, a legrövidebb út keresésére alkalmazható pl. Dijkstra módszere.

Ennek egyszerű változata a következőből áll: kitüntetjük a gráf egy pontját (jelen esetben a kincset mint 0-sugarú üreget), amelytől az összes többi pont távolságát (az élek mentén haladva) meg kívánjuk határozni. Minden csúcshoz két extra értéket rendelünk: a csúcs jelenleg ismert legkisebb távolságát a kitüntetett ponttól, illetve azt, hogy -le van-e zárva -, azaz, hogy ez a távolság már végleges, bizonyosan az optimum-e. A kincsre a távolság nyilván 0, és ennél kevesebb nem lehet. Az algoritmus további N-1 lépésének mindegyike a következő: kiválasztjuk a lezáratlanak közül azt a csúcsot, melyre a jelenleg ismert távolság minimális, ezt a csúcsot lezárjuk, és megnézzük, hogy ebből a maradék lezáratlan csúcsokba közvetlenül lépve azok távolságát lehet-e javítani. Ha igen, akkor a kisebb értékkel felülírjuk az eredetit.

Az algoritmus végén minden csúcsra tudjuk, hogy a kitüntetett ponttól mekkora távolságra van. Esetünkben ez a kincstől vett minimális fúrandó távolság. Mivel a gráfban a kincs szerepelt, de a felszín nem, a probléma teljes megoldásához még azt is meg kell nézni, hogy a felszínről az adott üregekbe mennyi fúrással juthatunk, ez hogy viszonyul az üregtől a kincsig fúrandó távolsághoz, és ennek alapján választhatjuk ki az optimális kezdőpozíciót.

Természetesen a legrövidebbút-keresést úgy is végezhettük volna, hogy felszínt egy speciális csúcsként felvesszük a gráfba; vagy akár úgy is, hogy minden csúcsnak a felszíntől való távolságát adjuk kezdeti értékül, és így, fordított irányban hajtjuk végre az algoritmust.

Engedy Balázs

Mintamegoldás és tesztadatok

A feladathoz tartozó mintamegoldás és a tesztadatok:

s22tesztadatok.zip

s26mmo.cpp

Statisztika:

2 dolgozat érkezett.
10 pontot kapott:	Kezes Balázs.
8 pontot kapott:	1 versenyző.

A KöMaL 2007. áprilisi informatika feladatai