Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 26. (April 2007)

S. 26. A treasure hunting company combines ancient maps with the latest technology to uncover buried valuables. Their many years of experience shows that treasures are buried in karst mountains with hard rocks and caves. Caves are sphere shaped, possible overlapping holes of different sizes. If they enter or dig into a cave, they can proceed digging from any other point of the cave, this way hard underground work can be reduced.

Write your program to determine the starting point on the surface such that the length of digging to reach the treasure is minimal, taking into account the possible shortcuts through the caves. You should also give this optimal length.

The position of the treasure and location of the caves are read from the standard input. The first line of the input contains the number of caves N (0\leN\le1000) and the elevation of the horizontal surface Yf relative to the sea level. The second line of the file contains the Xk, Yk, Zk coordinates of the treasure, while the following N lines the Xi, Yi, Zi, Ri coordinates of the caves. (Here the first three numbers represent the center of the cave, and Ri is the radius of the ith cave. We can suppose that all caves are completely under ground level.)

The program should display the results on the standard output in one line. This line should contain four decimal fractions (with at least two digits of accuracy) describing the X, Y, Z starting coordinates of the tunnel and the minimal distance L to dig.

The source code of your program (S26.pas, S26.cpp, \ldots) is to be submitted.

(10 pont)

Deadline expired on May 15, 2007.


Sorry, the solution is available only in Hungarian. Google translation

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


Statistics:

2 students sent a solution.
10 points:Kezes Balázs.
8 points:1 student.

Problems in Information Technology of KöMaL, April 2007