Mitenkä seuraavanlainen reitinlaskentaonglma kannattaisi tehdä Pythonilla:
Minulla on iso graafi ja siinä annettu kaksi solmua, joiden välisen lyhimmän etäisyyden haluaisin selvittää. Graafi on niin iso, että se ei millään mahdu kerralla koneen muistiin. Kuitenkin annettujen pisteiden lyhin reitti mahtuu helposti muistiin. Edelleen kullakin solmulla on vain noin pari tuhatta solmua, joiden välillä on särmä. Lisäksi oletetaan, että jos kahden solmun välillä on särmä, niin solmusta toiseen kulkeminen vie aikaa aina yhden yksikön.
Eli ohjelman tulisi kasvattaa ja tuhota verkkoa sitä mukaa kun laskenta etenee. Lisäksi en tiedä onko nopein tapa tehdä reitinhakualgoritmi suoraan, kuten Dijkstra tai Thorup, vai onko olemassa algoritmia, joka palauttaisi true/false sen mukaan onko reittiä kahden annetun pisteen välillä ja joka toimisi nopeammin kuin Thorup tai Dijkstra, jonka jälkeen voisin laskea eksplisiittisen reitin jommalla kummalla algoritmilla. Vai kannattaisikohan opetella A*:n tekeminen lyhimmän reitin etsintään?
Vai onkohan valmista ohjelmistoa tällaiseen? Joka tapauksessa jotain ohjelmointia vaaditaan, kun verkon särmien määrä on valtava, mutta laskentaa voisi rajoittaa vaikkapa asettamalla polun maksimipituudeksi 2000.
Mikä verkon koko (solmujen ja kaarten määrä) oikeasti on? "Ei mahdu muistiin" on melko suhteellinen kuvaus.
Python on paljon hitaampi ja vie paljon enemmän muistia kuin vaikka C++ tai Java. Datamäärältään suuressa ongelmassa kielen valinta ja tietorakenteiden optimointi on jo olennaista.
Algoritmiksi sopii luultavasti parhaiten leveyshaku (breadth-first search). Se on tehokas ja myös helppo toteuttaa. A* tulee kyseeseen, jos verkkoon liittyy jotain hyödyllisiä lisä vihjeitä maalin suunnasta.
A*-algoritmin idea on, että hakua voi nopeuttaa luotettavalla arviolla siitä, miten lähellä maalia tietty solmu on. Algoritmi soveltuu esimerkiksi karttoihin: kannattaa koettaa ensin suorimpia reittejä ja vasta toisena vaihtoehtona kiertoteitä. Jos ei ole mitään vihjeitä maalin suunnasta, A* ei sovellu.
Dijkstran algoritmissa lasketaan etäisyys lähtöpisteestä jokaiseen muuhun solmuun siten, että hakua jatketaan aina siitä solmusta, johon on ollut toistaiseksi lyhin matka. Saavutettuja solmuja pidetään prioriteettijonossa. Dijkstran algoritmi soveltuu käyttöön graafeissa, joissa kaarilla on jokin ei-negatiivinen painoarvo. Periaatteessa voisit käyttää sitä, mutta koska tapauksessasi jokaisen kaaren arvo on sama, saavutettuja solmuja ei tarvitse pitää prioriteettijonossa vaan ne voidaan pitää tavallisessa jonossa ja käsitellä löytöjärjestyksessä, jolloin kyseessä on leveyshaku.
Metabolix kirjoitti:
Mikä verkon koko (solmujen ja kaarten määrä) oikeasti on? "Ei mahdu muistiin" on melko suhteellinen kuvaus.
En osaa tarkkaan sanoa. Siis periaatteessa lyhin reitti solmusta toiseen on noin 1500. Kustakin solmusta pääsee noin 2000 muuhun solmuun. Laskin verkon solmujen lukumääräksi 2^1000 solmua, eli erittäin tiukkaa karsintaa pitäisi tehdä laskennan edetessä.
Universumissa on arvioitu olevan n. 10^80 eli 2^266 atomia. Verkkosi on tämä potenssiin neljä, siis mahdottoman suuri. Jos oletetaan, että 2^30 solmun verkko ratkeaisi sekunnissa (mikä olisi jo melkoinen saavutus) ja että käsittelyaika solmua kohti pysyisi samana, niin jo 2^60 solmun verkkoon kuluisi 34 vuotta.
Jos et oikeasti tiedä, mitkä osat verkosta voitaisiin jättää tutkimatta, kaikki ”karsinta” johtaa vain siihen, että algoritmilta jää suurin osa ratkaisuvaihtoehdoista tutkimatta ja näin ollen suurin osa ratkaisuista löytämättä. Eli onko verkossa jotain lisäinformaatiota?
Mistä tuollainen verkko edes muodostuu? Onko verkon muodostustavassa jotain säännöllisyyttä, jota voisi hyödyntää laskuissa? Herää kysymys, mitä edes etsitään eli onko kysymyksellä mitään todellista relevanssia.
Aika vaikea keksiä mitään todellista relevanssia. Mietin lähinnä tällaisen pelin ratkaisemista optimaalisesti: http://www.artbylogic.com/puzzles/numSlider/
Kyllähän tuo näyttäisi todella nopeasti vaikenevan ruudukon kasvaessa. Esim täällä voi testailla:
https://n-puzzle-solver.appspot.com/
15-pelissä ja vastaavissa laatoilla on selvä oikea järjestys, ja silloin kyllä A* (tai IDA*) soveltuu. Tilanteen hyvyyttä voi kuvata esimerkiksi sillä, kuinka monta laattaa on saatu oikeaan kohtaan, ts. loppusiirtojen määrän voi arvioida siitä, että jokainen seuraava siirto saisi kaikki siirtoon osallistuvat palat oikeille paikoilleen. (Tietenkään näin ei yleensä tapahdu, ja jos keksit paremman arvion, se voi nopeuttaa algoritmia.)
Kuitenkin jo 15-peli ihan tavallisilla säännöillä on niin vaikea, että ei todellakaan kannata lähteä miettimään suoraan mitään satojen ruutujen kokoista. Ratkaise ensin tavallinen 4×4-ruudukon 15-peli ja kokeile sitten, miten ratkaisu pärjää isommissa ruudukoissa.
Jaska kirjoitti:
Taitaapi IDA* olla tehokkaampi kuin Dijkstra.
A* (ja näin ollen myös IDA*) on riippuvainen arvion (heuristiikan) tarkkuudesta. Jos arvio on kovin epätarkka, A* tulee Dijkstran algoritmia huonommaksi (koska arviointi ei hyödytä ja toisaalta arviointikin vie aikaa). Jos arvio on väärä, A* ei ehkä löydä parasta ratkaisua.
IDA* voi olla hitaampi kuin A*, koska se tekee samat laskut moneen kertaan, jos hakusyvyyden raja on ensin liian matala. Se käyttää hieman vähemmän muistia kuin A*, jos raja on juuri oikean ratkaisun yläpuolella. Jos raja on asetettu ”turvallisesti” liian korkeaksi, IDA* onkin täsmälleen sama kuin A*.
Tuossa hyvyyden arvioinnissa "kuin monta laattaa on oikeassa ruudussa" perusteella voi olla se ongelma, että joskus on parempi että laatta on väärässä ruudussa kuin että se olisi oikeassa ruudussa.
Aihe on jo aika vanha, joten et voi enää vastata siihen.