Versioni origjinal nga kjo histori u shfaq në Revista Quanta.
Nëse doni të zgjidhni një problem të ndërlikuar, shpesh ndihmon për t’u organizuar. Për shembull, ju mund ta prishni problemin në copa dhe të trajtoni së pari pjesët më të lehta. Por kjo lloj klasifikimi ka një kosto. Ju mund të përfundoni duke shpenzuar shumë kohë duke i vendosur pjesët në rregull.
Kjo dilemë është veçanërisht e rëndësishme për një nga problemet më ikonike në shkencën e kompjuterave: gjetja e rrugës më të shkurtër nga një pikë fillestare specifike në një rrjet deri në çdo pikë tjetër. Likeshtë si një version i supuar i një problemi që ju duhet të zgjidhni sa herë që lëvizni: Mësoni rrugën më të mirë nga shtëpia juaj e re për të punuar, palestër dhe supermarket.
“Shtigjet më të shkurtra janë një problem i bukur me të cilin mund të lidhet kushdo në botë,” tha Mikkel Thorupnjë shkencëtar kompjuterik në Universitetin e Kopenhagës.
Intuitivisht, duhet të jetë më e lehtë të gjesh rrugën më të shkurtër drejt destinacioneve të afërta. Pra, nëse doni të hartoni algoritmin më të shpejtë të mundshëm për problemin e rrugëve më të shkurtra, duket e arsyeshme të filloni duke gjetur pikën më të afërt, atëherë më e mira tjetër, etj. Por për ta bërë atë, duhet të kuptoni vazhdimisht se cila pikë është më e afërta. Ju do t’i renditni pikat sipas distancës ndërsa shkoni. Ekziston një kufi themelor i shpejtësisë për çdo algoritëm që ndjek këtë qasje: Ju nuk mund të shkoni më shpejt se koha që duhet për të renditur.
Dyzet vjet më parë, studiuesit që hartojnë algoritme të rrugëve më të shkurtra u zhvilluan kundër këtij “pengese klasifikimi”. Tani, një ekip studiuesish ka krijuar një algoritëm i ri që e prish atë. Nuk renditet, dhe shkon më shpejt se çdo algoritëm që bën.
“Autorët ishin të guximshëm kur menduan se mund ta thyejnë këtë pengesë,” tha Robert Tarjannjë shkencëtar kompjuterik në Universitetin Princeton. “Anshtë një rezultat i mahnitshëm.”
Kufiri i njohurive
Për të analizuar problemin më të shkurtër të rrugës matematikisht, studiuesit përdorin gjuhën e grafikëve-punimet e pikave ose nyjet, të lidhura me linja. Linkdo lidhje midis nyjeve është etiketuar me një numër të quajtur pesha e tij, e cila mund të përfaqësojë gjatësinë e këtij segmenti ose kohën e nevojshme për ta përshkuar atë. Zakonisht ka shumë rrugë midis çdo dy nyjeve, dhe më e shkurtër është ajo që peshat e të cilit shtojnë numrin më të vogël. Duke pasur parasysh një grafik dhe një nyje specifike “burim”, qëllimi i një algoritmi është të gjejë rrugën më të shkurtër në çdo nyje tjetër.
algoritmi më i famshëm i rrugëve më të shkurtra, i realizuar Nga shkencëtari pionier i kompjuterit Edsger Dijkstra në 1956, fillon në burim dhe funksionon jashtë hap pas hapi. Shtë një qasje efektive, sepse njohja e rrugës më të shkurtër drejt nyjeve të afërta mund t’ju ndihmojë të gjeni shtigjet më të shkurtra drejt atyre më të largëta. Por për shkak se rezultati përfundimtar është një listë e renditur e shtigjeve më të shkurtra, pengesa e klasifikimit vendos një kufi themelor se sa shpejt mund të funksionojë algoritmi.