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.
válasza:
válasza: válasza:#1, #2: Elnézést, átolvasva, valóban, ez nem elég világos, és ezért én vagyok a ludas. Az irányváltás az, ami időigényes, gondolj bele, pl. A-ból B-be elfutni (rövid távon) sokkal kevesebb időbe telik, mint elfutni a táv feléig, ott lefékezni, s visszafutni A-ba. Vagy pl. gyorsabb két utcahossznyit futni, ha a két utca egymás utáni, és nem kell a sarkon irányt váltani.
Értékelési szempont tehát a minél kisebb irányváltoztatás, vagy, ha úgy tetszik, a kanyarok meredeksége. Például, ha csak két labdát kellene összegyűjteni, az 15 útvonal a legoptimálisabb, mert szinte egyáltalán nem kell irányt váltani, a labda bedobása nyugisan megoldható futás közben is (a pontatlanságtól tekintsünk el), szemben ha az 12 útvonalat választod, akkor le kell fékezned, és irányt változtatnod, mert szinte ugyanarra futsz vissza, ahonnan jöttél.
Remélem, ezúttal érthetőbbre sikerült, és még egyszer elnézést az alapkérdés érthetetlenségéért.
#3: Köszönöm a választ, de azt hiszem, félreértetted, nem útvonalat akarok optimalizálni (bár valószínűleg át lehet írni a problémát úgy, hogy azzá váljon, és ez talán egy jó kezdés lenne).
válasza:#1, #2: Próbáljátok elképzelni hogy egy labdaszedő rohangál ott és szedi fel a labdákat és mindig visszatér a sárga körbe. Az optimális útvonal az ha fent tudja tartani a sebességét, nem kell 180 fokos fordulatokat vennie. Pl. 1-ből az 5-be úgy tud átfutni hogy csak érinti a sárga kört, de megtartja a lendületét és fut tovább. De ha 1 után 2-be kell mennie akkor elfut a sárga körhöz, megáll és vesz 180 fokos fordulatot, ezzel elveszítve a lendületét és a sebességet. Nem optimális.
Először én egészen biztosan egy spline-t terveztem volna a modellezéséhez, de átgondolva az ismert adatokat, a fizikai modellt és a kikötéseket amiket be kell tartani (max. gyorsulás, lassulás, sebesség), időminimumot alig ha lehet számolni belőle de még csak közelíteni se biztos hogy fogjuk tudni. Elég mély matematikai ismeretek kellenek hogy analitikusan tudjuk ezt megoldani, ha egyáltalán meg lehet.
Viszont a probléma nagyon hasonlít egy másik problémához: ipari robotkarok pályatervezése. A robotkarnak van egy kinematikus és egy dinamikus modellje, van maximális nyomaték és sebesség, van egy pálya amit pontokkal definiáltunk és egy szabályzási kör ami egyik pontból átviszi a kart a másik pontba.
A különbség az, hogy a modellünk sokkal de sokkal egyszerűbb. Nem igazán lehet minimum számítással jól megoldani ezt a problémát, de nem is kell ha egy jól megtervezett szabályzó megteszi helyettünk. Rengeteg algoritmus és szabályzás született meg ezzel kapcsolatban már, de a téma elég bonyolult és pár hét alatt nem igazán lehet átlátni a dolgot.
Még talán a genetikus algoritmusok és neurális hálók jutnak eszembe, de ezek nem gyorsak és nem megbízhatóak eléggé az ilyen típusú feladatokhoz.
válasza:Számomra ez továbbra sem tiszta.
Ha, ahogy a többi válaszoló is írja, 1-1 lapba felszedése és kosárba juttatása ugyanolyan költséggel jár, bármelyikkel is kezded. Ennek tehát nincs problémaértéke. Ha úgy tetszik, nem is probléma.
Feladattá akkor válik, ha legalább kettesével kell a labdákat begyűjteni, mert akkor, ismerve a labdák pozícióját, egy-egy háromszöget kell bejárni, arra törekedve, hogy a háromszögek minél kisebb területet fedjenek le, pontosabban a háromszögek oldalai a lehető legrövidebbek legyenek. Itt már alkalmazható a shortest path algoritmus (kissé kiterjesztve a feladatot akárhány de mindenképpen véges labdaszámra).
Ha pedig az a cél, hogy az összes labdát a lehető legkisebb költséggel (fáradsággal) gyűjtsük be, akkor nyújt megoldást az utazó ügynök problémájára kifejlesztett algoritmus.
A fogalmazásodban, kérlek 15 és 12 útvonal helyett írj inkább 1-5, vagy 1-2 útvonalat. Ez érthetőbb.
#5: Valóban, a modell elég egyszerű, és csak a gyorsulást szeretném minimalizálni. Nem akarok mást figyelembe venni, mint azt, hogy minél kevesebbet kelljen irányt váltsak, mert a tapasztalat azt mutatja, hogy ez szokott a szűk keresztmetszet lenni.
#6: Kérlek olvasd át #4. hozzászólásomat, azt hiszem, elég jól leírtam, továbbá #5 első bekezdése szintén elmagyarázza.
Azt hiszem, át tudom írni egy gráfelméleti problémára a kérdést, talán így egyszerűbb:
Van egy öt pontból álló teljes gráf, minden csúcsa mag van számozva. Egyes csúcsok között az útvonal egyenlő a csúcsok sorszámának a különbségével, tehát az 1 és 2 csúcsok közti út hossza 1, az 1 és 5 közti út hossza 4, a 4 és 2 csúcsok közti út hossza 2 stb. Cél a legHOSSZABB útvonal megtalálása úgy, hogy minden pontot csak egyszer érintünk (ez kvázi az utazó ügynök problémájának fordítottja, nevezhetem esetleg a csatangoló turista problémájának?). Amennyiben ezt át lehetne írni egy utazó ügynök problémára, a feladat meg lenne oldva.
válasza: válasza: válasza:Én megpróbálkoznék valami greedy algoritmussal, azt hiszem az a megoldás, hogy el kell kezdeni az egyik szélsővel és mindig az lesz a következő, amelyik legmesszebb van tőle (szögben kifejezve természetesen).
Már csak bizonyítani kellene :)
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!