Valaki felvetette már ezt a problémát?
Vegyünk egy olyan várost, melynek utcái négyzetrácsot alkotnak, és minden négyzet ugyanakkora (akárcsak a "kockás" füzet lapjai). Ennek a városnak az egyik sarkából kell eljutnunk a vele átellenes sarkába kocsival, viszont szeretnénk a legkevesebbszer megállni. Az autóval két esetben kell kötelezően megállnunk:
-ha kanyarodunk, vagy
-ha a tábla szerint elsőbbséget kell adnunk. A táblák csak a kereszteződésekben fordulhatnak elő, és míg az egyik út szabad, a rá merőleges úton meg kell állni (akárcsak a való életben).
Ha nincs se tábla, se nem kanyarodunk, megállás nélkül folytathatjuk az utat.
Tehát a feladat egy olyan út találása, amelyben a legkevesebbszer kell megállni.
Kérdés, hogy erre van-e általános megoldási mód, vagy esetleg NP-teljes-e?
válasza:a jobb alsó sarokból indulsz (egyébként mindegy, mert az el ugyanaz). elindulsz felfelé a jobb felső sarokig. majd balra fordulsz és mész a bal felső sarokig. egyetlen egyszer sem kell megállnod, mert nincs sehol keresztező forgalom, ezért tábla sincs.
nem gondoltad át a feladatot.
válasza: válasza:Vedd a gráfod duálisát, vagyis legyenek az új gráfunk csúcsai a régi élei. Tegyük irányítottá, úgy, hogy minden élt kicserélünk egy oda-vissza élpárra. Ekkor minden irányított élhez hozzárendelsz 0-t vagy 1-et, miszerint meg kell-e állni az adott útszakaszok között az adott irányban haladva. Világos, hogy ez egy konzervatív súlyozás, azaz a Bellman-Ford minden csúcsból minden csúcsba megmondja a legrövidebb utat, tehát csak a 16 pár közül (az első és utolsó él a rendes gráfban 4-4 féle lehet) kell a legkisebbet kiválasztani, ami természetesen P beli, sőtt O(n^2)-ben megoldható.
Ráadásul ezzel általánosabban meg van oldva a kérdés, hiszen csúcsonként tetszőleges megállási szabályt megadhatunk, nem csak az általad leírtakat.
válasza:"Vagy csak nem sikerült értelmezned... Az is kereszteződésnek számít, ahol az út csak beletorkollik a másikba, így ott is lehet STOP-tábla."
mármint egy T alakú kereszteződésben azoknak, akik egyenesen haladnak át, úgy, hogy becsatlakozó út balról jön? (mert ügye az óramutató járásával ellentétesen haladok a szélen) Hát hogyne...
"Egyébként meg egyszer meg kell állni, mivel kanyarodsz a jobb felső sarokban."
technikailag az nem kanyarodás, mert semmilyen más irányba nem lehet menni. (max. vissza, azt meg nem akarok)
mint mondottam volt, nem gondoltad ezt te át. leginkább semennyire sem.
válasza:"Az is kereszteződésnek számít, ahol az út csak beletorkollik a másikba, így ott is lehet STOP-tábla."
Mi az, hogy LEHET Stop-tábla? Most van, vagy nincs? Vagy szabadon választott, hogy az én megoldásom szerint van-e? Mert akkor nyilván sehol sincs, hiszen úgy lehet a legkevesebb megállással abszolválni a feladatot.
5-ös, köszönöm a választ. Viszont ha veszünk egy n*n kereszteződést tartalmazó várost, akkor ott az egyik sarokból a másikba (2n alatt az n)-féle különböző útvonal van, amit ha egyesével véggnézünk, akkor az már nem polinom időben fut le.
Ez akkor nem azt jelenti, hogy találtunk egy problémát, ami egyébként "sok" esetet tartalmaz, mégis adható rá "rövid" algoritmus?
"mármint egy T alakú kereszteződésben azoknak, akik egyenesen haladnak át, úgy, hogy becsatlakozó út balról jön? (mert ügye az óramutató járásával ellentétesen haladok a szélen) Hát hogyne..."
Ne a való életből indulj ki. A táblákat -jobb esetben- úgy rakják ki, hogy a lehető legoptimálisabb legyen a közlekedés. Egy adott matematikai probléma általában túlmutat a valóságon. Az volt a kérdés, hogy ha például van 100 kereszteződés, és mi random kiszórunk 10 táblát, akkor abban az esetben melyik a legjobb út számunkra, illetve az hogyan található meg.
"technikailag az nem kanyarodás, mert semmilyen más irányba nem lehet menni. (max. vissza, azt meg nem akarok)"
Mivelhogy a kanyarodást úgy definiáltam, hogy ha nem egyenesen (és itt geometriai értelemben értsd az egyenes fogalmát) haladunk tovább, akkor az kanyarodásnak számít, és a kanyarodáshoz (szintén definíció szerint) meg kell állni, így az is kanyarodásnak számít.
"mint mondottam volt, nem gondoltad ezt te át. leginkább semennyire sem."
Azért, mert neked csak egysíkúan sikerül gondolkodnod, és aszerint vonsz le következtetéseket, az inkább csak azt mutatja, hogy te nem gondoltad át ezt az egészet, semennyire sem.
"Mi az, hogy LEHET Stop-tábla? Most van, vagy nincs? Vagy szabadon választott, hogy az én megoldásom szerint van-e? Mert akkor nyilván sehol sincs, hiszen úgy lehet a legkevesebb megállással abszolválni a feladatot."
Nem tudom megérteni, hogy akinek minimális köze sincs a matematikához, az minek ír ilyen stílusban...
Maradjunk annál, hogy a városban van 100 kereszteződés. Értelemszerűen minden kereszteződésre igaz, hogy ott vagy van tábla, vagy nincs, eszerint 2^98=316.912.650.057.057.350.374.175.801.344-féle lehet a város térképe, és lehet, hogy míg az egyik esetben valamelyik kereszteződésben van tábla, egy másik esetet véve ott már nem lesz.
válasza:Igen, nagyon sok út van, de mi nem akarjuk az összes hosszt kiszámítani, csak a legrövidebbet megtalálni.
Erre az algoritmusra hivatkoztam. Egy konzervatív súlyozású n csúcsú gráfon legrosszabb esetben n^3 idő alatt megtalálja egy csúcsból az összes csúcsba a legrövidebb utat. Ha ezt minden csúcsra futtatjuk, akkor n^4 idő alatt minden csúcsból minden csúcsba megtaláltuk a legrövidebb utat.
Egyébként mivel nemnegatív a súlyozás, a Dijkstra algoritmus gyorsabb, egyszerűbb, és ugyan ezt tudja.
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!