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
248
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
- 1452549
En kai koskaan saa sinua
Koska et usko että riitäisit minulle. Olet aina pitänyt itseäsi liian risana ja heikkona. Katkot korkeutesi, ja poraat k1541649Terveystalon lääkärit ylilaskuttaneet
Tämän pörriäiset osaavat, laskuttamisen. Terveystalo myöntää asian. https://www.hs.fi/suomi/art-2000011134269.html "K1331623Saran ökytyyli käänsi katseita.
On nyt kyllä Sara kasvoistaan, kuvan perusteella todellakin pyöristynyt ainakin kuvan perusteella.1461344- 661338
The Summit Suomi: Maxie avaa hyytävästä tilanteesta kuvauksissa: "Veri roiskui ja tajusi, että..."
Oletko seurannut The Summit Suomea? Tykkäätkö vai et tai mitä mieltä ylipäätään olet sarjasta? Moni katsoja on kaikonnut131170Työttömille lusmuille luvassa lisää keppiä
Hallitus aikoo kiristää velvoitteiden laiminlyönnistä seuraavia työttömyysturvan karensseja ensi vuodesta alkaen. Hall2721147- 156976
Miksi ihmeessä?
Erika Vikman diskattiin, ei osallistu Euroviisuihin – tilalle Gettomasa ja paluun tekevä Cheek22904Tiedän kaiken sinusta ja kaikesta
Tiedän miten kärsit. Tiedän millanen oikeesti oot. Tiedän miksi valehtelit, tiedän miksi satutit mua. Tiedän mitä tapaht58889