fbpx

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

08/09/2022
theme picturenbsp| WEBSTART

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

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

nbsp| WEBSTART

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

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

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

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

nbsp| WEBSTART

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

nbsp| WEBSTART

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

nbsp| WEBSTART

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

nbsp| WEBSTART

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

nbsp| WEBSTART

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

nbsp| WEBSTART

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

nbsp| WEBSTART

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

  • Հարմարավետ երթևեկությունը

    Այս դեպքում սովորաբար ընտրում ենք ավելի լավ ասֆալտ և ավելի քիչ կտրուկ շրջադարձեր ունեցող փողոցները: Որպեսզի նավիգատորը ընտրի հենց այդպիսի ճանապարհներ, դրանց կարելի է կցել 0,8 գործակից, ինչը գործնականում կնվազեցնիայդ փողոցներով երթևեկելու ժամանակը 20% -ով, իսկ նավիգատորը միշտ կընտրի ավելի արագ ճանապարհը:
  • Երթուղու բարդությունը

    A-ից B կետ ճանապարհը գործնականում գրեթե երբեք ուղիղ չի լինում. այն միշտ ունի շրջադարձեր, որոնք ժամանակ են պահանջում: Որպեսզի նավիգատորը դա հաշվի առնի, սյունակներին ավելացվում է շրջադարձի ժամանակը առանձին գործակցով կամ պարամետրով: Այդպես ալգորիթմը կփնտրի իսկապես հեշտ հաղթաղարելի երթուղի` հաշվի առնելով ճանապարհները:
  • Խցանումները

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

    Իսկ եթե ​​ինտերնետ չկա, ապա ալգորիթմը պարզապես օգտագործում է խցանումների միջինացված մոդելը, որը նախապես ներբեռնված է և անընդհատ թարմացվում է:


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