Nad koostavad Ameerika Ühendriikide kõige tõhusama maanteereisi kaardi

Anonim

Nad koostavad Ameerika Ühendriikide kõige tõhusama maanteereisi kaardi

48 osariigi pealinna 8 1/2 päevaga

Olson kehtestas rea ruume, mis määrasid tema hilisemad arvutused. Esiteks ei olnud eesmärk külastada linnu, vaid nii palju osariigi pealinnasid kui võimalik . Teisel kohal, sõidaks ainult autoga , mis jätab Alaska oma kauguse tõttu marsruudist välja ja Hawaii lennukiga sõitmise vajaduse tõttu, piirates marsruudi 48 külgneva osariigiga. Kolmas ja viimane, Välistatud oleksid marsruudid, mis nõuavad teiste riikide läbimist et vältida passe ja piirikontrolli, mis aeglustavad mis tahes reisi, selgitab Randal S. Olson oma veebisaidil.

Seda arvesse võttes uurija kasutas geneetiliste algoritmide, Google Mapsi ja Pareto mitme eesmärgi optimeerimise kombinatsiooni , või mis on seesama, avastasid, et täiuslikkust läbi Ameerika Ühendriikide teekonna eeldab külastada 48 osariigi pealinna, läbides 8 ja poole päevaga 21 420 km . Kuni liiklust pole muidugi. Lisaks määras see kindlaks, et reisi saab alustada mis tahes punktist marsruudil ilma lõpptulemust muutmata.

Nagu tegi? Kui pealinnade nimekiri käes, pidi Olson kindlaks määrama, milline oli tegelik vahemaa nende hoonete vahel maanteel ja mitte sirgjooneliselt. Selleks pöörduti Google Mapsi API poole, mis arvutas välja 2256 võimaliku marsruudi vahemaad.

Kui marsruudid olid välja arvutatud, siis järgmiseks tuli need järjestada, et nende kombineerimisel oleks võimalikult vähe läbitud kilomeetreid. Geneetilisel algoritmil oli vastus. Tema huvi seisneb selles, et kõigi võimalike variantide otsimise asemel pakub ta juhuslikke lahendusi, proovides alati midagi muud ja jättes alles parimad ettepanekud, kuni paremat ei leia.

Kõik see koos Pareto mitme eesmärgi optimeerimise rakendamine , mis võimaldab optimeerida mitut kriteeriumi korraga. Antud juhul käsil see suurendaks külastatavate riikide arvu ja minimeeriks selleks kuluvat aega.

Loe rohkem