Kaikki varmaan tietää?
https://fi.wikipedia.org/wiki/Kauppamatkustajan_ongelma
Kerron silti:
Olkoon esimerkiksi kymmenen kaupunkia, joista kaikista tiedetään etäisyydet toisiin. Kuinka selvitetään lyhin reitti, joka kulkee kaikkien kaupunkien kautta, missä palataan lähtökaupunkiin ja käydään jokaisessa (paitsi lähtökapungissa) vain kerran.
Täydellinen ratkaisu: muodostetaan kaikki reitit ja valitaan lyhkäsin - on vain pirun hidas, koska, jos kaupunkeja olisi n kappaletta, olisi reittejä (n-1)! eli 10:llä esimerkiksi 9!=362 880 kappaletta.
Käytännössä siis koodilla ei kannattane kovin montaa kaupunkia tarkastella. Jos kärsivällisyys riittää, niin 10 on maksimi. Kokeilin yhdeksää ja parisen minuuttiaa meni.
Ja tämä on sitten taas vähän sellaista räpellyskoodia - ei kannattane liian tiukkapipoisesti suhtautua? Toimii kuitenkin jotenkuten?
# Kauppamatkustajan ongelma
from itertools import permutations
import random
print('Montaa kaupunkia haluat tarkastella?')
lkm=int(input())
lista=[]
for i in range(1,lkm+1,1):
lista.append(i)
# tuotetaan kaikki permutaatiot joukolle [1,2, 3,...,lkm]
perm = list(permutations(lista))
etäisyydet=[]
# arvotaan etäisyydet
#Muodostetaan kaksiulotteinen taulukko etäisyyksille
for i in range(0,lkm+1,1):
etäisyysalkio=[]
for j in range(0,lkm,1):
if i==j:
etäisyys=0 #etäisyys on nolla kaupungista itseensä
else:
etäisyys=random.randint(1,100)
etäisyysalkio.append(etäisyys)
etäisyydet.append(etäisyysalkio)
reitit=[] #permutaatiot taulukosta poimitaan eri reitit
print('Arvotut etäisyydet',etäisyydet)
for i in range(0,len(perm)-1,1):
reitti = []
reitti.append(1) # lähtökaupunki on aina eka
for j in range(0,lkm,1):
if perm[i][j] not in reitti:
reitti.append(perm[i][j])
reitti.append(1) #ja vika on 1
if reitti not in reitit:
reitit.append(reitti)
print('Kaikki mahdolliset reitit',reitit)
lyhinmatkareitti=99999999
#lasketaan eri reittien pituudet
pituudet=[]
for i in range(0,len(reitit)-1,1):
reitinpituus = 0
for k1 in range(0,lkm-1,1):
k2=k1+1
reitinpituus=reitinpituus+etäisyydet[reitit[i][k1]-1][reitit[i][k2]-1]
if reitinpituus<lyhinmatkareitti:
lyhinmatkareitti=reitinpituus
lyhinreitti=reitit[i]
pituudet.append(reitinpituus)
#tulostetaan manuaalisen tarkistuksen takia vielä reitit ja niiden pituudet
for i in range(0,len(reitit)-1,1):
print(reitit[i],pituudet[i])
print('Lyhin reitti on pituudeltaan',lyhinmatkareitti,'ja se on kaupunkien',lyhinreitti,'kautta')Hain ohjelmallisesti Red kielellä etäisyydet Suomen suurimmista kaupungeista netistä ao. ohjelmalla :) Tältä sivustolta: https://kartta.com/etaisyydet-kartalla/ Kohta, kenties huomenna, alan tuottamaan koodia tutkiakseni millä reitillä nopeiten koluaa läpi Suomen suurimmat kaupungit Helsingistä lähtien (Espoota ja Vantaata en luonnollisestti lisännyt joukkoon). Luonnollisesti hain vähän turhaa haun kaupungista A:sta B:hen ja B:stä A:han, mutta karsin koodissa nuo typeryydet... EDIT: Enpä hakenutkaan! Esimerkiksi etäisyys Helsingistä Turkuun on eri kuin Turusta Helsinkiin...sadan metrin tarkkuudella - ja tuossa tapauksessa on jopa parin kilometrin ero - johtuu kai jotenkin ajoreiteistä. Toista kaistaa ajaen sisämutkalla on lyhkäsempi matka tms.
Red[] substr: func [string start length][ copy/part at string start length ] lmrk: to-char 34 kaupungit: ["Helsinki" "Turku" "Lahti" "Tampere" "Oulu" "Jyv%C3%A4skyl%C3%A4" "Kuopio" "Pori"] foreach k1 kaupungit [ foreach k2 kaupungit [ if k1 <> k2 [ osoite: rejoin ["https://kartta.com/etaisyydet-kartalla/" k1 "/" k2 "/"] ;print osoite sivu: read to-url osoite etsi1: rejoin["ajaen on <b><span class=" lmrk "res-etaisyys" lmrk ">"] sivu: find sivu etsi1 loop (length? etsi1) [sivu: next sivu] alku: index? sivu sivu: find sivu "<" loppu: index? sivu matka: substr sivu 1 (alku - loppu) matka: replace matka "," "." matka: to-float matka print rejoin[lmrk k1 lmrk ", " lmrk k2 lmrk ", " matka] ] ] ] halt
Ohjelma listasi:
"Helsinki", "Turku", 169.2 "Helsinki", "Lahti", 109.9 "Helsinki", "Tampere", 190.8 "Helsinki", "Oulu", 608.7 "Helsinki", "Jyv%C3%A4skyl%C3%A4", 270.8 "Helsinki", "Kuopio", 391.3 "Helsinki", "Pori", 245.1 "Turku", "Helsinki", 165.8 "Turku", "Lahti", 245.6 "Turku", "Tampere", 163.6 "Turku", "Oulu", 648.1 "Turku", "Jyv%C3%A4skyl%C3%A4", 307.7 "Turku", "Kuopio", 453.4 "Turku", "Pori", 151.3 "Lahti", "Helsinki", 107.7 "Lahti", "Turku", 244.0 "Lahti", "Tampere", 132.6 "Lahti", "Oulu", 507.7 "Lahti", "Jyv%C3%A4skyl%C3%A4", 169.8 "Lahti", "Kuopio", 290.3 "Lahti", "Pori", 247.8 "Tampere", "Helsinki", 179.1 "Tampere", "Turku", 163.6 "Tampere", "Lahti", 132.6 "Tampere", "Oulu", 490.3 "Tampere", "Jyv%C3%A4skyl%C3%A4", 149.9 "Tampere", "Kuopio", 295.6 "Tampere", "Pori", 112.1 "Oulu", "Helsinki", 608.0 "Oulu", "Turku", 648.3 "Oulu", "Lahti", 507.1 "Oulu", "Tampere", 490.8 "Oulu", "Jyv%C3%A4skyl%C3%A4", 341.3 "Oulu", "Kuopio", 286.8 "Oulu", "Pori", 509.0 "Jyv%C3%A4skyl%C3%A4", "Helsinki", 269.4 "Jyv%C3%A4skyl%C3%A4", "Turku", 307.8 "Jyv%C3%A4skyl%C3%A4", "Lahti", 169.1 "Jyv%C3%A4skyl%C3%A4", "Tampere", 149.7 "Jyv%C3%A4skyl%C3%A4", "Oulu", 340.2 "Jyv%C3%A4skyl%C3%A4", "Kuopio", 146.8 "Jyv%C3%A4skyl%C3%A4", "Pori", 264.6 "Kuopio", "Helsinki", 383.9 "Kuopio", "Turku", 454.1 "Kuopio", "Lahti", 290.4 "Kuopio", "Tampere", 296.0 "Kuopio", "Oulu", 287.2 "Kuopio", "Jyv%C3%A4skyl%C3%A4", 147.4 "Kuopio", "Pori", 410.9 "Pori", "Helsinki", 245.5 "Pori", "Turku", 142.1 "Pori", "Lahti", 248.3 "Pori", "Tampere", 113.4 "Pori", "Oulu", 508.0 "Pori", "Jyv%C3%A4skyl%C3%A4", 265.3 "Pori", "Kuopio", 411.0
Kaupunkien etäisyydet linnuntietä saisin suoraan 8th:lla:
needs geo/distance \ Esimerkiksi Lahti - Tampere etäisyys linnuntietä. 60.983 25.661 61.498 23.761 geo:distance "%.2f km\n" s:strfmt .
Tulostaa:
116.66 km
Ajokilometrit täytyisi kyllä sitten hakea jostain...
jalski kirjoitti:
Ajokilometrit täytyisi kyllä sitten hakea jostain...
Noi on nimenomaan ajokilometrejä. Autolla ajo kilometrejä.
Jos tarkkaan katsot koodia, niin etsin sivun HTML-koodista elementtiä:
etsi1: rejoin["ajaen on <b><span class=" lmrk "res-etaisyys" lmrk ">"]
Eli "ajaen..."
Hiio hoi! Kuokkasin ja muokkasin REBOL:lla tuota listaani ja sain 2-ulotteisen listan etäisyyksistä kivuttomasti. Ohjelma tulosti:
Lyhin reitti on pituudeltaan 1170.3 ja se on kaupunkien [1, 2, 8, 4, 3, 6, 7, 5, 1] kautta
Eli seuraavien kaupunkien kautta
Helsinki
Turku
Pori
Tampere
Lahti
Jyväskylä
Kuopio
Oulu
Helsinki
Process finished with exit code 0
# Kauppamatkustajan ongelma
from itertools import permutations
lkm=8
lista=[]
for i in range(1,lkm+1,1):
lista.append(i)
# tuotetaan kaikki permutaatiot joukolle [1,2, 3,...,lkm]
perm = list(permutations(lista))
kaupungit=["Helsinki", "Turku", "Lahti", "Tampere", "Oulu", "Jyväskylä", "Kuopio", "Pori"]
etäisyydet=[
[0, 169.2, 109.9, 190.8, 608.7, 270.8, 391.3, 245.1],
[165.8, 0, 245.6, 163.6, 648.1, 307.7, 453.4, 151.3],
[107.7, 244.0, 0, 132.6, 507.7, 169.8, 290.3, 247.8],
[179.1, 163.6, 132.6, 0, 490.3, 149.9, 295.6, 112.1],
[608.0, 648.3, 507.1, 490.8, 0, 341.3, 286.8, 509.0],
[269.4, 307.8, 169.1, 149.7, 340.2, 0, 146.8, 264.6],
[383.9, 454.1, 290.4, 296.0, 287.2, 147.4, 0, 410.9],
[245.5, 142.1, 248.3, 113.4, 508.0, 265.3, 411.0, 0]
]
reitit=[] #permutaatiot taulukosta poimitaan eri reitit
for i in range(0,len(perm)-1,1):
reitti = []
reitti.append(1) # lähtökaupunki on aina eka
for j in range(0,lkm,1):
if perm[i][j] not in reitti:
reitti.append(perm[i][j])
reitti.append(1) #ja vika on 1
if reitti not in reitit:
reitit.append(reitti)
lyhinmatkareitti=99999999
#lasketaan eri reittien pituudet
pituudet=[]
for i in range(0,len(reitit)-1,1):
reitinpituus = 0
for k1 in range(0,lkm-1,1):
k2=k1+1
reitinpituus=reitinpituus+etäisyydet[reitit[i][k1]-1][reitit[i][k2]-1]
if reitinpituus<lyhinmatkareitti:
lyhinmatkareitti=reitinpituus
lyhinreitti=reitit[i]
pituudet.append(reitinpituus)
print('Lyhin reitti on pituudeltaan',lyhinmatkareitti,'ja se on kaupunkien',lyhinreitti,'kautta')
print('Eli seuraavien kaupunkien kautta')
for kaup in range(1,10,1):
print(kaupungit[lyhinreitti[kaup-1]-1])PetriKeckman kirjoitti:
(29.05.2023 20:03:22): ”– –” Noi on nimenomaan ajokilometrejä. Autolla...
Huomasin asian kyllä. Tuo 8th:n mukana tuleva toiminnallisuus on lähinnä hyödyllinen aikojen ja sijaintitietojen kanssa touhutessa. Itse olen toteuttanut astronomisen kellon toiminnot kotiautomaatio-ohjaimeeni.
Esimerkiksi:
needs geo/cities
needs geo/nearest
needs astro/sunrise
\ Set location
: location! \ latitude longitude --
astro:longitude ! astro:latitude ! ;
: d:tzoffset? \ -- n
"%Z" d:new d:format ":" s:/ ' >n a:map
[60,1] ' n:* a:2map ' n:+ 0 a:reduce ;
: astro \ d -- sunrise sunset
"%Y-%M-%DT" over d:format >r astro:sunrise 2 a:close
( 60 n:* 60 n:/mod "%02d:%02d:00+00:00" s:strfmt r@ swap s:+ d:parse d:tzoffset? d:tzadjust ) a:map
rdrop a:open ;
: app:main
"Hämeenlinna" true loc:city
a:len if
a:open ["lat", "lon"] m:_@ dup
a:open location!
d:new d:>fixed d:fixed>dow
["sunnuntai","maanantai","tiistai","keskiviikko","torstai","perjantai","lauantai"] caseof
d:new d:ymd swap astro 2 a:close ( "%H:%T" d:format ) a:map a:open 4 a:close
"Tänään on %s ja päivämäärä on: %s\n\nHämeenlinnassa aurinko nousee klo: %s ja aurinko laskee klo: %s\n" s:strfmt .
"\n\nPaikkakunnat 15 km säteellä Hämeenlinnasta:\n\n" .
a:open 15 geo:nearest 1 -1 a:slice
( [0,3] a:_@ "%s: %.1f km\n" s:strfmt . ) a:each! drop
else
drop
then ;Ohjelma tulostaa:
Tänään on maanantai ja päivämäärä on: 2023-05-29 Hämeenlinnassa aurinko nousee klo: 04:06 ja aurinko laskee klo: 22:33 Paikkakunnat 15 km säteellä Hämeenlinnasta: Parola: 8.1 km Turenki: 12.7 km Janakkala: 12.9 km Renko: 14.7 km
Wau! Jos Facebookissa oltaisiin niin peukuttaisin.
Onpas tehokas työkalu tuo 8th. Harmi, että en tunne kieltä ollenkaan ja näyttää heprealta.
Lomamatkat maailman parhaiden lomakaupunkien läpi.
Tuolta: https://www.thedistancenow.com/fi/ sain ohjelmallisesti poimittua melko kätevästi kaupunkien väliset etäisyydet linnuntietä. Tuolta: https://kerranelamassa.fi/matkakohteet/
New York – maailman pääkaupunki
Lontoo – maailman kosmopoliittisin kaupunki
Tokio – maailman suurin kaupunki
Rooma – ikuinen kaupunki
Istanbul – eksotiikkaa lähellä!
Bangkok – samaan aikaan sopivan moderni ja eksoottinen.
Intian eksotiikkaan tutustuu Delhissä, jonne on Suomesta suorat lennot.
Singapore – siistiä eksotiikkaa
Hongkong – pilvenpiirtäjiä ja herkullista ruokaa
Havanna – ihanaa rappioromantiikkaa
Helsinki - Maailman paras kaupunki
Tavallinen tietsikka hyytyy siis kauppamatkustajan täydellisen ratkaisun ratkaisemisessa jo 13 kaupungilla. Toisaalta ihminen pystyy järkevästi ilman laskelmia päättelelemään, että jos on Euroopassa, niin ensin täytyy koluta kaikki Euroopan kaupungit eikä lähteä tutkimaan muita haaroja, kuten, että kannattaisiko Roomasta lentää ensin Tokioon ja sieltä Lontooseen. Mietin, että mitenköhän mahdollinen kvanttitietokone - pystyisikö se ratkaisemaan ongelman täydellisesti. Kvanttitietokone kai on useissa tiloissa yhtäaikaa tms...
Muun muassa tuolla sivustolla: http://users.jyu.fi/~jorma/kauppam.htm ongelman "epätäydellisiä" ratkaisuja esitetään.
Tämä on nyt vähän laitonta puuhaa - jaan hs:n artikkelia, mikä on tarkoitettu vain tilaajille. Ymmärrän jos tämä viesti halutaan poistaa foorumilta. Toisaalta tämä voidaan tulkita hesarin mainokseksi. Mielestäni artikkeli vain on niin mielenkiintoinen tämän threadin keskustelun aiheen kannalta. Ihmetyttää mitä keinoja sitten käytetään artikkelin lopussa mainittavien tulosten saantiin: "Jos sallitaan yhden prosentin virhemarginaali, miljoonia kaupunkeja käsittävän kauppamatkustajan ongelman voi ratkoa muutamassa tunnissa."
(PS: osaatteko arvioida missä ajassa edellisessä viestissäni esittelemän tapauksen ohjelmani laskee kun kaupunkeja on 11 kpl? Ohjelma on nyt noin tunnin pyörinyt. En luovuta vielä - onhan mulla aikaa odottaa vaikka viikko :) )
---
Miten suuri kauppamatkustajan ongelma voidaan ratkaista?
Tilaajille
Kauppinen Touko, Merimaa Juha
15.11.2011 2:00
Niin kutsutussa
kauppamatkustajan ongelmassa etsitään lyhin reitti kaupunkien välillä. Joka kaupungissa saa vierailla kerran, ja paluu on lähtöpaikkaan. Jos kaupunkeja on pari, ongelma on helppo, mutta vaihtoehtojen lisääntyessä vaadittava laskentateho kasvaa nopeasti. Kuinka suuri ongelma on ratkaistavissa nykytietokoneilla?
Ongelmaa voi lähestyä kolmella tavalla. Yksinkertaisin on niin sanotusti raaka voima eli kaikkien vaihtoehtojen laskeminen läpi. Näin saadaan varmasti oikea vastaus.
Ongelmaksi muodostuu laskemisen hitaus. Jo 27 kaupungin ongelma on niin suuri, että sen laskemiseen kuluva aika ylittäisi universumin iän. 21 kaupungin ongelmassa kuluisi noin tuhat vuotta.
Ongelmaa ratkaistaessa voi hyödyntää myös laskenta-algoritmeja. Esimerkiksi tuhat kaupunkia käsittävän ongelman voisi ratkaista tavallisella kannettavalla tietokoneella noin tunnissa. Suurimmassa tarkasti ratkaistussa kauppamatkustajan ongelmassa on ollut hieman alle 100000 kaupunkia.
Kolmas vaihtoehto ovat vielä paljon nopeammat algoritmit, jotka laskevat matkustajalle erittäin hyvän reitin, joskaan eivät välttämättä kaikkein lyhintä. Näin laskettu reitti voi erota parhaasta mahdollisesta reitistä esimerkiksi yhden prosentin. Mitä tarkempi tulos halutaan, sitä kauemmin laskeminen kestää.
Jos sallitaan yhden prosentin virhemarginaali, miljoonia kaupunkeja käsittävän kauppamatkustajan ongelman voi ratkoa muutamassa tunnissa.
Olli Serimaa
sovellusasiantuntija Tieteen tietotekniikan keskus
PetriKeckman kirjoitti:
osaatteko arvioida missä ajassa edellisessä viestissäni esittelemän tapauksen ohjelmani laskee kun kaupunkeja on 11 kpl?
EDIT: Huoh! Kohta menny vuorokausi ja ohjelma pyörii yhä - arvioin väärin ajon aika tarpeen.
ohjelma ratkaisi 8 kaupungin tapauksen muistaakseni noin ajassa 1 minuutti. 10!/7!=720 ja 720 minuuttia = 12 tuntia. Ohjelman ajon pitäisi valmistua noin aamyöstä kello 5.
EDIT:
Tässä kun ohjelma vielä pyörii, niin yritän vajavaisella omalla aivotoiminnallani arvata tulosta "manuaalisesti"
Helsinki
Lontoo
Rooma
Istanbul
Delhi
Bangkok
Singapore
Hongong
Tokio
Havanna
New York
Helsinki
Melko varmaan tämä? Aikaa meni noin 3 minuuttia :)
Aihe on jo aika vanha, joten et voi enää vastata siihen.