Oriģinālā versija no šis stāsts parādījās Kvantu žurnālsApvidū
Ja vēlaties atrisināt sarežģītu problēmu, tas bieži palīdz organizēt. Jūs, piemēram, varētu sadalīt problēmu gabalos un vispirms risināt vieglākos gabalus. Wager šāda veida šķirošanai ir izmaksas. Jūs, iespējams, galu galā tērējat pārāk daudz laika, sakārtojot gabalus.
Šī dilemma ir īpaši būtiska vienai no ikoniskākajām datorzinātņu problēmām: īsākā ceļa atrašana no konkrēta sākumpunkta tīklā līdz visiem citiem punktiem. Tā ir kā problēmas, kas saistīta ar problēmu, jums jāatrisina katru reizi, kad pārvietojaties: labāko maršruta apguvi no jaunās mājas uz darbu, sporta zāli un lielveikalu.
“Īsākie ceļi ir skaista problēma, ar kuru ikviens pasaulē var attiekties,” sacīja Mikkel Thorupdatorzinātnieks Kopenhāgenas universitātē.
Intuitīvi vajadzētu būt visvieglāk atrast īsāko ceļu uz tuvējiem galamērķiem. Tātad, ja vēlaties noformēt ātrāko iespējamo algoritmu par īsāko triecienu problēmu, šķiet saprātīgi sākt, atrodot tuvāko punktu, pēc tam nākamo visaptverošo utt. Wager, lai to izdarītu, jums atkārtoti jāizdomā, kurš punkts ir vistuvāk. Jūs sakārtosit punktus pēc attāluma, ejot. Jebkuram algoritmam, kas seko šai pieejai, ir būtisks ātruma ierobežojums: jūs nevarat doties ātrāk nekā laiks, kas nepieciešams kārtošanai.
Pirms četrdesmit gadiem pētnieki, kas projektē īsākos trases algoritmus, stājās pretī šai “šķirošanas barjerai”. Tagad ir izstrādājusi pētnieku komanda jauns algoritms, kas to sabojāApvidū Tas nav šķirots, un tas darbojas ātrāk nekā jebkurš algoritms, kas to dara.
“Autori bija pārdroši, domājot, ka viņi varētu izjaukt šo barjeru,” sacīja Roberts TarjansPrinstonas universitātes datorzinātnieks. “Tas ir pārsteidzošs rezultāts.”
Zināšanu robeža
Lai matemātiski analizētu īsāko problēmu, pētnieki izmanto grafiku valodu-punktu vai mezglu, kas savienoti pēc rindām. Katra saikne starp mezgliem ir marķēta ar skaitli, ko sauc par tā svaru, kas var attēlot šī segmenta garumu vai laiku, kas nepieciešams, lai to šķērsotu. Starp diviem mezgliem parasti ir daudz maršrutu, un īsākais ir tas, kura svars sasniedz vismazāko skaitli. Ņemot vērā grafiku un konkrētu “avota” mezglu, algoritma mērķis ir atrast īsāko ceļu uz katru otro mezglu.
Līdz slavenākais īsāko triecienu algoritmsVerdzība izstrādāts Autors: novatoriskais datorzinātnieks Edgers Dijkstra 1956. gadā, sākas pie avota un soli pa solim darbojas uz āru. Tā ir efektīva pieeja, jo, zinot īsāko ceļu uz tuvējiem mezgliem, var palīdzēt atrast īsākos ceļus uz tālākiem. Wager, tā kā gala rezultāts ir sakārtots īsāko ceļu saraksts, šķirošanas barjera nosaka būtisku robežu, cik ātri algoritms var darboties.
