Ինչպե՞ս է մեքենայի նավիգատորը գտնում ամենակարճ ճանապարհը

Մեզանից շատերը գրեթե ամեն առավոտ բախվում են այս խնդրին տաքսի կանչելիս. հասնել արագ ու առանց խցանումների կամ կարճ ճանապարհով, բայց սպասելով։ Լավագույն դեպքում ստացվում է համատեղել երկուսն էլ և հասնել կարճ ճանապարհով և առանց խցանումների։

Դիցուկ, ունենք մի քանի թաղամաս, որոնց միջև հեռավորությունները մեզ հայտնի են։ Եթե ​​մենք պարզապես վերցնենք տեղանքները՝ նրանց միջև եղած հեռավորություններով, ապա մաթեմատիկայի տեսանկյունից կստանանք մի գրաֆիկ։ Թաղամասերը կլինեն գրաֆիկի գագաթները, իսկ նրանց միջև եղած ճանապարհները՝ գրաֆիկի կողմերը։ Եթե ​​մենք գիտենք յուրաքանչյուր ճանապարհի երկարությունը, ապա դա կլինի գրաֆիկի կողմերի արժեքը: Այս տեսությունն արդեն բավական է, որպեսզի հասկանանք, թե ինչպես է նավիգատորը աշխատում մեքենայում։

Իսկ հիմա փորձենք արագ գտնել ամենակարճ ճանապարհը

Տվյալ խնդիրը լուծելիս հիմնական ժամանակը ծախսվում է ճանապարհի հնարավոր բոլոր տարբերակները հաշվարկելու վրա։ Ուստի, կրճատելով այն, կկարողանանք ավելի արագ գտնել կարճ ճանապարհը։

Եվ ահա 1959թ գիտնական Էդսգեր Դեյկստրան ստեղծեց իր ալգորիթմը, որն օգտագործվում է մինչ օրս։ Դրա գաղափարը ոչ թե բոլոր տարբերակների միջով անցնելն է, այլ ամենակարճ ճանապարհը գտնելը միայն կից գրաֆիկների միջև, և այդպես, քայլ առ քայլ, հասնել դեպի վերջնակետ:

Ենթադրենք, մենք ունենք փողոցներ, խաչմերուկներ և գիտենք դրանց միջև ճանապարհն անցնելու ժամանակը: Պատկերենք այն գրաֆիկի տեսքով՝

A-ից B ամենաարագ ուղին գտնելու համար մենք նախ նայում ենք, թե ինչ ճանապարհներ են դուրս գալիս A կետից: Այստեղ կարելի է տեսնել, որ դեպի ներքև շարժվելն ավելի արագ կլինի, քան աջ գնալը՝

Հետևաբար, ընտրում ենք ներքևի ճանապարհը: Որից հետո կատարում ենք նույն գործողությունները հետևյալ կետի համար. ստուգում ենք, թե որտեղ է ճանապարհն ավելի արագ՝ աջ կողմում, թե ներքևում: Այս պարագայում, ներքև տանող ճանապարհն ավելի արագ է ստացվում, քանի որ 1-ը 4-ից փոքր է։

Միևնույն ժամանակ, մենք չենք հրաժարվում արդեն կատարած հաշվարկներից և պահում ենք դրանք մտքում։ Ներքևի կետից միայն մեկ ճանապարհ կա՝ դեպի աջ, այնպես որ մենք գնում ենք հենց դրա երկայնքով՝

Հետաքրքիր իրավիճակ ստացվեց՝ այստեղից կարող ենք կենտրոնական կետին հասնել և՛ վերևից, և՛ ներքևից, երկուսն էլ 3 րոպեում։ Ուրեմն ճիշտ կլինի հաշվարկել երկու տարբերակն էլ։ Միգուցե վերևից ավելի արագ լինի, և մենք նորից ստիպված լինենք վերակառուցենք երթուղին՝

Եվ այսպես, ստացվում է, որ ներքևից դեպի կենտրոն գնալն ավելի արագ է, քան վերևից՝ 6-ի փոխարեն 4 րոպե։ Ի վերջո, կենտրոնական կետից մինչև B կետ կա միայն մեկ ուղի ՝ դեպի աջ, ուստի մենք ընտրում ենք այն՝

Ինչպես տեսնում ես, մենք ստիպված չեղանք հաշվել բոլոր տարբերակները, ինչը զգալիորեն խնայեց ժամանակը: Ահա այսպիսի ալգորիթմ է ընկած նավիգատորի աշխատանքի հիմքում։ Ահա՝

Կան նաև այլ գործոններ, որոնք հաշվի է առնում նավիգատորը, որոնք են՝

• Հարմարավետ երթևեկությունը
  
  Այս դեպքում սովորաբար ընտրում ենք ավելի լավ ասֆալտ և ավելի քիչ կտրուկ շրջադարձեր ունեցող փողոցները: Որպեսզի նավիգատորը ընտրի հենց այդպիսի ճանապարհներ, դրանց կարելի է կցել 0,8 գործակից, ինչը գործնականում կնվազեցնիայդ փողոցներով երթևեկելու ժամանակը 20% -ով, իսկ նավիգատորը միշտ կընտրի ավելի արագ ճանապարհը:
  
• Երթուղու բարդությունը
  
  A-ից B կետ ճանապարհը գործնականում գրեթե երբեք ուղիղ չի լինում. այն միշտ ունի շրջադարձեր, որոնք ժամանակ են պահանջում: Որպեսզի նավիգատորը դա հաշվի առնի, սյունակներին ավելացվում է շրջադարձի ժամանակը առանձին գործակցով կամ պարամետրով: Այդպես ալգորիթմը կփնտրի իսկապես հեշտ հաղթաղարելի երթուղի` հաշվի առնելով ճանապարհները:
  
• Խցանումները
  
  Եթե ​​կա ինտերնետ, ապա ամեն ինչ պարզ է՝ նավիգատորը տվյալներ է ստանում ճանապարհների վիճակի մասին և ավելացնում է տարբեր գործակիցներ՝ կախված ծանրաբեռնվածությունից։ Երբեմն նավիգատորը տանում է բակերով, երբ ճանապարհն ազատ է։ Դա նավիգատորի սխալը չէ, այլ նրա կանխատեսումը։ Եթե, օրինակ, 10 րոպե անց տվյալ վայրում սովորաբար խցանումներ են հավաքվում, ապա ավելի լավ է չգնալ այնտեղ, այլ շեղվել ճանապարհից՝ նախապես ապահովագրվելով ժամանակ կորցնելուց։
  
  Իսկ եթե ​​ինտերնետ չկա, ապա ալգորիթմը պարզապես օգտագործում է խցանումների միջինացված մոդելը, որը նախապես ներբեռնված է և անընդհատ թարմացվում է:
  
  
  

Ահա այս պարզ ալգորիթմն է, որ ամեն օր մեզ օգնում է հաշվարկել ճանապարհը և տանում է կարճ ու արագ ուղիներով դեպի տուն կամ աշխատանքի վայր։ Այս և այլ՝ ավելի հետաքրքիր նյութերի համար հետևիր մեր բլոգին։