Hogy lenne a legegyszerűbb lemodelleznem az alábbit?
Egy elég nyelvfüggetlen problémával állok szemben (de, ha valakit érdekel, valószínűleg PHP-ban vagy JavaScriptben fogom megcsinálni).
Egy teniszpályán elhelyezünk öt labdát, ezek az ábrán pirossal vannak jelölve:
A játékos a sárgával jelölt vedertől indul, elmegy egy labdáig, visszaviszi a vederbe, és ezt a folyamatot megismétli minden labdára. Feladat: A legoptimálisabb út megtalálása, ami azt jelenti, hogy a legkevesebb fordulást igényli.
Például: az 12345 útvonal egyáltalán nem optimális, mert rengeteg fordulást feltételez. Az 15243 útvonal jobb, mert van benne egy teljesen egyenes szakasz is(15). Még hasznosabb azonban (gyakorlatban ezt szoktam alkalmazni) a 25143 útvonal, mert ebben szintén benne van az egyenes útvonal, viszont nem kell az élesnek számító 24 kanyart bevenni.
Az érdekesség kedvéért viszont szeretném kipróbálni, számítógép szerint melyik a legoptimálisabb útvonal, és szeretnék segítséget kérni a lemodellezéshez. Íme, eddig mit találtam ki:
Az egyszerűség kedvéért lehet minden fordulást úgy tekinteni, hogy ugyanannyi fokot kell a játékos forduljon, így pl. az 12 és 34 fordulások is mondjuk 1-nek felelnének meg, az 13 és 35 mondjuk 2-nek, az 15 pedig 4-nek és így tovább. Ilyen modell esetén a fordulások által jelentett számok összegét maximalizálni kellene.
Arra gondoltam, hogy egy 5*120-as kétdimenziós tömbben elmenthetném a pontok összes lehetséges sorrendjét, majd mondjuk egy új tömbben mindenik útvonalnál az összeget (amit egyszerűen úgy számolnék ki, hogy a pontok sorszámát kivonom egymásból, és a különbségeket összeadom), és ezek közül kikeresem a maximálisat, majd az ennek megfelelő sorrendet megnézem. Ezen megoldással több baj is van: egyrészt, kissé túl erőforrásigényesnek tűnik (bár ez nem egy életbevágó probléma, ha igazán optimalizált kódot akarnék, nem scriptnyelven írnám meg), a másik, hogy nem ismerek általános módszer arra, hogy az öt szám összes permutációját beírjam egy kétdimenziós tömbbe.
Akinek ötlete, ajánlata van a probléma másirányú megközelítésére (ha lehet, továbbra is nyelvfüggetlenül), kérem válaszoljon. Szeretnék minél több megoldási módot látni.
Előre is köszönöm a válaszokat.
Nagyon szépen köszönöm a válaszokat, azt hiszem, ez alapján fel tudom építeni, legalább egy jó kis agytorna lesz.
#9: Ebből fogok valószínűleg elindulni, köszönöm.
scriba: Egy okos greedy algoritmus lehet valóban hasznos, még agyalok rajta.
Permutációk tekintetében pedig köszönöm a választ.
#12(ez már inkább off/kötekedés, a programozási részhez nincs sok köze): A kérdés egy valós problémát vet fel, edzésen szoktuk csinálni ezt (futás-és gyorsulástechnika fejlesztésére), és ilyenkor, hogy sokat kelljen futni, egyesével szedjük őket. Általában a 2-5-1-4-3 útvonalat járjuk be, de gondoltam, megkérdezek egy számítógépet is, hogy mit szól ehhez az útvonalhoz. Ami pedig a lassítást illeti, nem csak egyszer elég nagy a szög, mert nem mindegy, hogy 1-ből 2-be fordulsz, vagy 4-be. Persze, kell lassítani, de messze nem annyit.
Még egyszer köszönöm a segítőkész válaszokat!
Ez a bruteforce megoldás pythonban, elég tömören.
Érdekes, hogy mindig van legalább két optimális út, akkor is, ha a szimmetrikus eseteket egynek vesszük és az elrendezés sem szimmetrikus. Ebből gondolom, hogy nem teljesen utazó ügynök probléma, mert ez esetleg adhat lehetőséget egyszerűsítésre.
#14: arról van szó, hogy egy adott feladatra kell hatékony algoritmust találni, és ilyenkor a jelentéktelen részletektől eltekintünk, nem érdekel hány éves a labdaszedő és az sem milyen színű a fű.
Egy útvonaltervező algoritmusnál se megfelelő válasz, hogy menj inkább helikopterrel, akkor nem kell követned az utakat. De az se, hogy minek az útvonaltervező, ha baleset van valahol, akkor úgyis kerülnöd kell.
scriba: Köszönöm nagyon szépen a programot, igazán sokat segítettél!
#16: Szerintem azért egy optimális út megtalálása minősülhet programozással kapcsolatos kérdésnek. Valóban, edzésen nem a legüdvösebb alkalmazni, mert a megszokott útvonalon már elég jól ismerek minden fordulót, viszont agytornának elég jó feladat (legalábbis nekem, jó/nálam jobb programozók valószínűleg éjjel háromkor, holtrészegen is meg tudják oldani)
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!