Kezdőoldal » Számítástechnika » Programozás » Hogy lenne a legegyszerűbb...

Hogy lenne a legegyszerűbb lemodelleznem az alábbit?

Figyelt kérdés

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:


[link]


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.



2016. márc. 31. 19:00
1 2
 11/18 anonim ***** válasza:

A másik kérdésed a permutációk előállítására vonatkozott:

[link]


Pythonban javaslom az itertools modult:

[link]

2016. ápr. 1. 09:31
Hasznos számodra ez a válasz?
 12/18 anonim ***** válasza:
37%
Ez ugyanúgy dijstra algoritmus, csak bele kell venni azt is hogy a fordulási szög a lehető legnagyobb legyen, de így sincs sok variáció. Rakjál a labdaszedőre stoplis cipőt. Egyébként érdekes hogy olyanon problémázol hogy ne kelljen lelassítania a vödör elhaladása mellett (amihez kb egyszer elég nagy csak a szög), de olyan béna a labdaszedő hogy csak egy labdát tud vinni egyszerre. A kettő a minimum, ha pedig nem egy 5 évessel szedeted a labdát, akkor 4.
2016. ápr. 1. 10:31
Hasznos számodra ez a válasz?
 13/18 anonim ***** válasza:
100%
Egyébkén a legoptimàlisabb ha magával viszi a vödröt, és úgy csak 1-szer kell fordulnia! :)
2016. ápr. 1. 10:33
Hasznos számodra ez a válasz?
 14/18 A kérdező kommentje:

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!

2016. ápr. 1. 13:00
 15/18 anonim ***** válasza:

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.


[link]

2016. ápr. 1. 13:46
Hasznos számodra ez a válasz?
 16/18 anonim ***** válasza:
#14 Hogy érted hogy nincs köze a programozáshoz? Először arra gondoltam hogy egy teniszes játékhoz kell, ahol a labdaszedőt akarod reálisan leprogramozni, de így amit mondtál, a programozáshoz már nem sok köze van, és az eddzésnél sincs értelme alkalmazni, mivel ott a legnagyobb teljesítmény elérése a cél, nem pedig az hogy a legkisebb energiabefektetéssel hajtsunk végre egy feladatot.
2016. ápr. 1. 13:58
Hasznos számodra ez a válasz?
 17/18 anonim ***** válasza:
100%

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

2016. ápr. 1. 14:27
Hasznos számodra ez a válasz?
 18/18 A kérdező kommentje:

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)

2016. ápr. 1. 20:00
1 2

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!