Oheinen metodi etsii kaikki mahdolliset reittivaihtoehdot mitä syötetyillä kohteiden määrällä voi olla.
[URL=http://img35.imageshack.us/i/reittimetodi.jpg/][IMG]http://img35.imageshack.us/img35/5329/reittimetodi.jpg[/IMG][/URL]
Ongelmana onkin että kyseinen metodi on surkuhupaisan hidas. Esim. 9 kohteella reittivaihtoehtoja voi olla 362 880 kpl (ja 4 ytiminen prossu saa laskea sitä about tunnin) niin olisiko jollakulla kokeneemmalla tyypillä ohjeistusta tai esimerkkiä miten tuon saisi näppärämmin selvitettämään reitit?
Lyhyesti selostettuna tuon toiminta menee näin:
sekoitetaan lista(jossa siis on kohteiden nimet), tarkistetaan löytyykö sitä taulukosta ja jollei sitä ole niin se tallennetaan sinne. Ja tätä jyllätään while loopissa niin pitkään kunnes reittivaihtoehtojen maksimimäärä tulee umpeen esim. 9 kohteella kun taulukossa on 362 880 reittiä niin lopetetaan.
laskeReittivaihtoehtojenMaara metodi palauttaa syötetyn arvon kertoman
sekotusLista sisältää kohteitten nimet
Vinkkiä nopeampaan algoritmiin
8
145
Vastaukset
- rautalangast
Kuvan linkki meni hieman pieleen vielä niin laitan toiseen kertaan:
http://img35.imageshack.us/i/reittimetodi.jpg/ - foobarfoo
Koodissasi oli virhe: rivillä 238 vertaat kahta lista-oliota toisiinsa, kun varmaan haluaisit verrata että onko näiden listojen sisältö sama ja samassa järjetyksessä.
Nopein nopeutusidea mikä näin lauantaiaamuna lähtee on, että laitat noi kohteet map-olioon ja vertailet noita avaimia toisiinsa ja vasta lopussa tulostat reitit.
Ilmeisesti suomi24 on blokattu imageshackin sivuilta, koska noi kuvalinkki ei toimi. - rautalangasta
"Koodissasi oli virhe: rivillä 238 vertaat kahta lista-oliota toisiinsa, kun varmaan haluaisit verrata että onko näiden listojen sisältö sama ja samassa järjetyksessä."
Testailin tuota vielä uudelleen ja kyllä se näköjään tajuaa myös tarkistaa onko listat samassa järjestyksessä.
public static void main(String[] args) {
List lista = new ArrayList();
lista.add("helsinki");
lista.add("turku");
List lista2 = new ArrayList();
lista2.add("turku");
lista2.add("helsinki");
if (lista.equals(lista2)) {
System.out.println("ol sama");
} else {
System.out.println(lista " ei ollu " lista2);
}
}
Mutta joo pitää kattoa miten nuo map hommelit menee ja testailla vielä sillä sitten. Tulostus oli kanssa siinä lopussa eikä while silmukan sisällä =)- foobarfoo
Väärin testattu:) haluat aina testata että ohjelma toimii oikealla datalla oikein, et sitä et väärällä datalla väärin. Mut joo, ainoa tapa miten keksin rikkoa tuon oli et vaihdan turku-> Turku . Eikä tuo vertailu myöskään toiminut jos laitoin itse tekemäni luokan tuohon listiin ja en ylikirjoittanut sen luokan equals-metodia.
public static void main(String[] args) {
List lista = new ArrayList();
lista.add("Turku");
lista.add("helsinki");
List lista2 = new ArrayList();
lista2.add("turku");
lista2.add("helsinki");
if (lista.equals(lista2)) {
System.out.println("ol sama");
} else {
System.out.println(lista " ei ollu " lista2); - rautalangasta
foobarfoo kirjoitti:
Väärin testattu:) haluat aina testata että ohjelma toimii oikealla datalla oikein, et sitä et väärällä datalla väärin. Mut joo, ainoa tapa miten keksin rikkoa tuon oli et vaihdan turku-> Turku . Eikä tuo vertailu myöskään toiminut jos laitoin itse tekemäni luokan tuohon listiin ja en ylikirjoittanut sen luokan equals-metodia.
public static void main(String[] args) {
List lista = new ArrayList();
lista.add("Turku");
lista.add("helsinki");
List lista2 = new ArrayList();
lista2.add("turku");
lista2.add("helsinki");
if (lista.equals(lista2)) {
System.out.println("ol sama");
} else {
System.out.println(lista " ei ollu " lista2);Lista on pyyhkästy toisessa metodissa jo lowercaseksi niin ei pitäisi olla ongelma ja ei myöskään sisällä samaa osoitetta toistamiseen.
Eli sinällään muuten tuo toimii oikein mutta pirun hitaasti.. kattelin suorittimen käyttöastetta samalla niin näyttäs siinä 25% kieppeillä pyörivän (vaan yhtä ydintä kuormitti) niin jostain jos sais poppaskonstin jolla pyyhältää tuutin täydeltä soppaa sille :)
Mutta kaitpa tuota muutenkin nopeutettua saisi vaan ei aloittelijana mitään tajua. Aikamoinen sekamelska on muutnenkin kyseinen ohjelma.
- rautalangasta
Poistin rivit 246 ja 250 koska siinä ei tallenneta reittiä mikäli reitin ensimmäinen kohde on kauimmaisena aloituspaikasta, vaikka se pitäisi tehdä vasta kun kaikki reitit on selvillä.
Mielelläni ottaisin vastaan lisää ehdotuksia.
Tuohon linkkiin vielä että näyttäs toimivan kun sen kopioi suoraan osoiteriville.
Vaikka siinä ylimääräistä säätämistä tuleekin niin arvelin koodin näyttävän selkeämmältä tuosta eclipse shotista kuin pasteta se if hässäkkä tähän :)- dx
Siis en oikein käsitä mitä tuo algoritmisi oikein yrittää tehdä. Mutta jos haluat generoida kaikki mahdolliset reitit N-kaupugin välillä, kannattaa varmaan käyttää vaikka jotain noita permutaatioidengenerointimenetelmiä:
http://www.cs.princeton.edu/~rs/talks/perms.pdf
- hhhhggga
Mitä pyrit loppujen lopuksi tekemään, löytämään lyhintä mahdollista reittivaihtoehtoa?
Jos haluat lyhyimmän reitin (reittien välillä on esim joku matka ja haluat löytää mahdollisimman lyhyen matkan kulkea pisteestä a pisteeseen b), käytä jotain siihen soveltuvaa menetelmää esim. dijkstra's sortest path algorithm
Jos taas haluat vain generoida kaikki mahdolliset yhdistelmät, oikea vastaus on jo annettu eli permutointi
Sivuhuomautuksena tuolla prosessorin ytimien määrällä ei ole mitään väliä, ellet tee ohjelmaasi sitä ajatellen (säikeistettynä tai useampaa prosessia apuna käyttäen).
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Voitasko leikkiä jotain tunnisteleikkiä?
Tietäisi ketä täällä käy kaipaamassa.. kerro jotain mikä liittyy sinuun ja häneen eikä muut tiedä. Vastaan itsekin kohta802015Tietysti jokainen ansaitsee
Hän varmasti ansaitsee vain parasta ja sopivinta tietenkin, suon sen onnen hänelle enemmän kuin mielelläni. Aika on nyt181763- 161634
50+ naiset kyl
Lemottaa sillille mut myös niitte kaka lemottaa pahlle ku kävin naiste veskis nuuhiin211430Jotain puuttuu
Kun en sinua näe. Et ehkä arvaisi, mutta olen arka kuin alaston koivu lehtiä vailla, talven jäljiltä, kun ajattelen sinu601337hieman diabetes...
Kävin eilen kaverin kanssa keskusapteekissa kun on muutama kuukausi sitten tullut suomesta ja oli diabetes insuliinit lo181298Välitän sinusta mies
Kaikki mitä yritin kertoa tänään ei mennyt ihan putkeen..Joka jäi jälkeenpäin ajateltuna suoraan sanottuna harmittaa aiv61282En voi sille mitään
Tulen niin pahalle tuulelle tästä paikasta nykyisin. Nähnyt ja lukenut jo kaiken ja teidän juttu on samaa illasta toisee121264Miten joku voi käyttää koko elämänsä
siihen että nostelee täällä vanhoja ketjuja ja troIIaa niihin jotain linkkiä mitä kukaan ei avaa? Ihmisellä ei ole mitää101221- 691216