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
314
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
Porvarimediat paniikissa demareiden huiman kannatuksen vuoksi
Piti sitten keksiä "nimettömiin lähteisiin" perustuen taas joku satu. Ovat kyllä noloja, ja unohtivat sen, että vaalit986278KATASTROFI - Tytti Tuppurainen itse yksi pahimmista kiusaajista!!!
STT:n lähteiden mukaan SDP:n eduskuntaryhmän puheenjohtaja Tytti Tuppurainen on käyttäytynyt toistuvasti epäasiallisesti3505764Mikä siinä on ettei persuille leikkaukset käy?
On esitetty leikkauksia mm. haitallisiin maataloustukiin, kuin myös muihin yritystukiin. Säästöjä saataisiin lisäksi lei602763Lääppijä Lindtman jäi kiinni itse teosta
Lindtman kyselemättä ja epäasiallisesti koskettelee viestintäpäällikköä. https://www.is.fi/politiikka/art-20000117808521072198Juuri nyt! Tytti Tuppurainen on käyttäytynyt toistuvasti epäasiallisesti
Ai että mä nautin, Tytti erot vireille! "Käytös on kohdistunut avustajia ja toisia kansanedustajia kohtaan, uutisoi STT1071888- 1251744
Puolen vuoden koeaika
Voisi toimia meillä. Ensin pitäis selvittää "vaatimukset" puolin ja toisin, ennen kuin mitään aloittaa. Ja matalalla pro191633Tytti Tuppurainen nöyryyttää avustajiaan
Tytti Tuppurainen nöyryyttää SDP:n eduskuntaryhmän kokouksissa sekä avustajia että kansanedustajia. Hän nolaa ihmisiä ju1811290- 731197
Huomaatteko Demari Tytti ei esitä pahoitteluitaan
Samanlainen ilmeisesti kuin Marin eli Uhriutuu no he ovat Demareita ja muiden yläpuolella siis omasta mielestään331088