Բրաեսի պարադոքս

Բրաեսի պարադոքս

Պարադոքս

Կիրառությունը	Հոսքային ցանց
Կոչվել է ի պատիվ	Dietrich Braess
Հայտնաբերող կամ հնարող	Dietrich Braess

Բրաեսի պարադոքսն այն դիտարկումն է, որ ճանապարհային ցանցին մեկ կամ մի քանի ճանապարհ ավելացնելը կարող է դանդաղեցնել դրա միջով երթևեկող մեքենաների ընդհանուր հոսքը: Պարադոքսն առաջին անգամ ձևակերպվել է Արթուր Պիգուի կողմից 1920 թվականին։ Ավելի ուշ այն անվանվել է գերմանացի մաթեմատիկոս Դիտրիխ Բրաեսի անունով, 1968 թվականին։

Պարադոքսը զուգահեռներ ունի էլեկտրական ցանցերում և կենսաբանական համակարգերում: Առաջակվել է տեսություն, որ անսարք ցանցի բարելավումը կարող է իրականացվել՝ հեռացնելով դրա որոշ մասերը: Պարադոքսն օգտագործվել է երթևեկության հոսքի բարելավման օրինակները բացատրելու համար, երբ առկա հիմնական ճանապարհները փակ են եղել:

Բացահայտում և սահմանում

Գերմանիայի Ռուր համալսարանի մաթեմատիկոս Դիտրիխ Բրաեսը, երթևեկության մոդելավորման վրա աշխատելիս նկատել է, որ ճանապարհային ցանցում հոսքը կարող է խոչընդոտվել նոր ճանապարհ ավելացնելով: Նրա գաղափարն այն էր, որ եթե յուրաքանչյուր վարորդ սեփական շահերից ելնելով որոշում է կայացնում, թե որ երթուղին է ամենաարագն իր համար, ապա նույն դյուրանցումը կարող է շատ հաճախ ընտրվել վարորդների կողմից: Ավելի ֆորմալ, Բրաեսի հայտնագործության հիմքում ընկած գաղափարն այն է, որ Նեշի հավասարակշռությունը նման համակարգերում պարտադիր չէ լինի օպտիմալ։

Պարադոքսը պնդում է հետևյալը.

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

Ցանցին լրացուցիչ ուղիներ ավելացնելը, երբ շարժվող մեքենաները իրենք են ընտրում են իրենց երթուղին, որոշ դեպքերում կարող է բերել ընդհանուր արդյունավետության նվազեցման: Դա պայմանավորված է նրանով, որ նման համակարգի Նեշի հավասարակշռությունը պարտադիր չէ, որ օպտիմալը լինի: Ցանցի փոփոխությունը առաջացնում է խաղի նոր կառուցվածք, որը հանգեցնում է (բազմախաղացող) բանտարկյալի երկընտրանքի : Նեշի հավասարակշռության պայմաններում վարորդները չունեն իրենց երթուղիները փոխելու խթան: Քանի դեռ համակարգը չի գտնվում Նեշի հավասարակշռության մեջ, առանձին վարորդներ կարող են բարելավել իրենց ճամփորդության ժամանակները՝ փոխելով իրենց երթուղիները: Բրաեսի պարադոքսի դեպքում վարորդները կշարունակեն փոխել ճանապարհները, մինչև հասնեն Նեշի հավասարակշռությանը՝ չնայած ընդհանուր արդյունավետության նվազմանը:

Պարադոքսի հնարավոր օրինակներ

Տարածվածություն

1983-ին Սթայնբերգը և Զանգվիլը տրամադրեցին անհրաժեշտ և բավարար պայմանները, որպեսզի ողջամիտ ենթադրությունների պարագայում տրանսպորտային ցանցում տեղի ունենա Բրաեսի պարադոքսը, երբ նոր երթուղի է ավելացվում: (Նկատի ունեցեք, որ դրանց արդյունքը վերաբերում է ցանկացած նոր երթուղու ավելացմանը, այլ ոչ միայն մեկ կապող ճանապարհի:) Որպես արդյունք նրանք ստացան, որ պատահական նոր երթուղի ավելացնելիս Բրաեսի պարադոքսի տեղի ունենալը նույնքան հավանական է, որքան չունենալը։

Երթևեկություն

Երբ Սեուլում արագընթաց մայրուղին հանվեց, որպեսզի վերականգնվի գետը, երթևեկությունը տարածքում բարելավվեց։

Բրաեսի պարադոքսին նման պնդում է՝ ճանապարհային ցանցի կրճատումը կարող է հանգեցնել անհատական երթևեկության ժամանակի կրճատմանը։

Հարավային Կորեայի Սեուլ քաղաքում երթևեկությունն արագացել է, երբ Չեոնգյե արագընթաց մայրուղին հանվել է Չեոնգյեչեոնի վերականգնման ծրագրի շրջանակներում։ Գերմանական Շտուտգարտում, 1969 թվականին ճանապարհային աշխատանքների մեջ ներդրումներ կատարելուց հետո, երթևեկության իրավիճակը չբարելավվեց, մինչև նորակառույց ճանապարհի մի հատվածը կրկին չփակվեց։ 1990 թվականին Երկրի օրվա կապակցությամբ Նյու Յորքի Մանհեթենի 42-րդ փողոցի ժամանակավոր փակումը նվազեցրեց այդ տարածքում խցանումների քանակը։ 2008 թվականին Յունը, Գաստները և Ջոնգը ցույց տվեցին կոնկրետ երթուղիներ Բոստոնում, Նյու Յորքում և Լոնդոնում, որտեղ խցանումներ կարող էին լինել, և մատնանշեցին ճանապարհներ, որոնց փակելու դեպքում կանխատեսված ճանապարհորդության ժամանակը կնվազեր։ 2009-ին Նյու Յորքը փորձարկեց փակել Բրոդվեյը Թայմս Սքվերում և Հերալդ Սքվերում, ինչը հանգեցրեց երթևեկության բարելավմանը և մշտական հետիոտնային հրապարակներին։

2012-ին Պոլ Լեկրոտը, Իլ-դե-Ֆրանսի պլանավորման և զարգացման ինստիտուտից, գրել է՝ «Չնայած մտավախություններին, հիմնական ճանապարհների հեռացումը չի հանգեցնում երթևեկության պայմանների վատթարացմանը:»: Նա նաև նշում է, որ մասնավոր տրանսպորտային միջոցներով որոշ ուղևորություններ (և հարակից տնտեսական գործունեություն) չեն տեղափոխվում հասարակական տրանսպորտ և պարզապես անհետանում են («գոլորշիանում»)։

Նույն երևույթը նկատվել է նաև, երբ ճանապարհների փակվել են ոչ թե քաղաքային ծրագրի շրջանակներում, այլ վթարի հետևանքով։ 2012 թվականին Ռուենում կամուրջ է ավերվել հրդեհից։ Հաջորդ երկու տարիների ընթացքում ավելի շատ օգտագործվեցին այլ կամուրջներ, սակայն կամուրջներով անցնող մեքենաների ընդհանուր թիվը կրճատվեց։

Էլեկտրականություն

2012թ.-ին Մաքս Պլանկի դինամիկայի և ինքնակազմակերպման ինստիտուտի գիտնականները մոդելավորման միջոցով ցույց տվեցին երևույթի հավանականությունը էլեկտրահաղորդման ցանցերում, որտեղ էլեկտրաէներգիայի արտադրությունը ապակենտրոնացված է:

2012 թվականին Institut Néel (CNRS, Ֆրանսիա), INP (Ֆրանսիա), IEMN (CNRS, France) և UCL (Բելգիա) հետազոտողների միջազգային թիմը Physical Review Letters ամսագրում հրապարակեց մի գիտական աշխատանք, որը ցույց էր տալիս, որ Բրաեսի պարադոքսը կարող է առաջանալ մեզոսկոպիկ էլեկտրոնային համակարգերում։ Մասնավորապես, նրանք ցույց տվեցին, որ նանոսկոպիկ ցանցում էլեկտրոնների համար ուղի ավելացնելը պարադոքսալ կերպով նվազեցնում է դրա հաղորդունակությունը: Դա ցույց են տվել ինչպես սիմուլյացիաները, այնպես էլ ցածր ջերմաստիճանում արված փորձերը:

Զսպանակներ

Աջ կողմում երկու զսպանակներ են՝ հաջորդաբար միացված կարճ պարանով։ Երբ B և C-ն միացնող կարճ պարանը հանվում է (ձախ), քաշը ավելի բարձր է կախվում:

Զսպանակներով և պարաններով մոդելը ցույց է տալիս, որ կախված կշիռը կարող է բարձրանալ, չնայած, որ կախովի համակարգում ձգված պարանը կտրված է։ Սա բխում է նույն մաթեմատիկական կառուցվածքից, ինչպիսին Բրաեսի սկզբնական պարադոքսն է։

Կարճ պարանով միմյանց հաջորդաբար միացված երկու միանման զսպանակների ընդհանուր զսպանակային հաստատունը յուրաքանչյուր առանձին զսպանակի հաստատունի կեսին է հավասար, ինչը հանգեցնում է երկար ձգման, երբ կախված է որոշակի քաշ: Այսպես է մնում, երբ մենք երկու երկար պարան ենք ավելացնում, որպեսզի միացնենք վերին զսպանակի ստորին ծայրը կախված քաշին (ներքևի զսպանակի ստորին ծայրը), իսկ ստորին զսպանակի վերին ծայրը կախված կետին (վերին զսպանակի վերին ծայրը): Այնուամենայնիվ, երբ կարճ պարանը կտրվում է, երկար պարանները ձգվում են, և երկու զսպանակները դառնում են զուգահեռ (մեխանիկական իմաստով) միմյանց: Զսպանակի ընդհանուր հաստատունը երկու անգամ գերազանցում է յուրաքանչյուր առանձին զսպանակի հաստատունին, և երբ երկար պարանների երկարությունը շատ մեծ չէ, կախված քաշը իրականում ավելի բարձր կլինի՝ համեմատած կարճ պարանը կտրելուց առաջ:

Կախված կշռի բարձրանալը, կարճ պարանը կտրելուց հետո, կարող է հակաինտուիտիվ թվալ, բայց սա բխում է Հուկի օրենքից և զսպանակների հաջորդական և զուգահեռ աշխատանքի եղանակից:

Կենսաբանություն

Ադիլսոն Է. Մոթերը և նրա գործընկերները ցույց տվեցին, որ Բրաեսի պարադոքսը հաճախ կարելի է տեսնել կենսաբանական և էկոլոգիական համակարգերում: Մոթերն առաջարկում է, որ խաթարված ցանցի մի մասը հեռացնելը կարող է փրկել այն: Վտանգված տեսակների սննդային ցանցերի ռեսուրսների կառավարման համար, որտեղ շատ տեսակների անհետացում կարող է լինել, դատապարտված տեսակների ընտրովի հեռացումը ցանցից սկզբունքորեն կարող է բերել դրական արդյունքի՝ կանխելով հետագա անհետացումները:

Թիմային սպորտի ռազմավարություն

Առաջարկվել է տեսություն, որ բասկետբոլում թիմը կարող է դիտվել որպես գնդակը զամբյուղին հասցնելու հնարավոր երթուղիների ցանց՝ յուրաքանչյուրը տարբեր արդյունավետությամբ, իսկ լավագույն խաղացողը կարող է նվազեցնել թիմի ընդհանուր արդյունավետությունը՝ ինչպես ճանապարհային դյուրանցում, որը չափից շատ է օգտագործվում՝ ավելացնելով ճանապարհային ցանցով երթևեկության ընդհանուր ժամանակը: Միավորներ հավաքելու առավելագույն արդյունավետության համար առաջարկվող լուծումն այն է, որ լավագույն խաղացողը նույնքան հարված կատարի, որքան իր թիմակիցները: Սակայն այս մոտեցումը չի հաստատվել վիճակագրական ապացույցներով, ինչպես նշված է սկզբնական գիտական աշխատանքում:

Բլոկչեյն ցանցեր

Բրաեսի պարադոքսը դիտվում է նաև բլոկչեյն վճարային ուղիների ցանցերում: Վճարային ուղիների ցանցերը լուծում են բլոկչեյն ցանցերի մասշտաբայնության խնդիրը՝ թույլ տալով բարձր դրույքաչափերով գործարքներ՝ առանց դրանք բլոկչեյնում գրանցելու: Նման ցանցում օգտատերերը կարող են ստեղծել ուղի՝ փակելով միջոցները ուղու յուրաքանչյուր կողմում: Գործարքները կատարվում են կա՛մ վճարողին և ստացողին ուղղակի կապող ուղու միջոցով, կա՛մ միջանկյալ օգտվողների հետ կապուղիների միջոցով, որոնք պահանջում են որոշակի վճար:

Թեև ինտուիտիվ կերպով, նոր ուղիների բացումը բերում է երթուղիների ավելի ճկուն ընտրության հնարավորության, նոր ուղի ավելացնելը կարող է ավելի բարձր վճարներ առաջացնել, և նմանապես՝ գոյություն ունեցող ուզիների փակումը կարող է նվազեցնել վճարները:

Մաթեմատիկական մոտեցում

Օրինակ

Դիտարկենք ճանապարհային ցանց, ինչպես ցույց է տրված պատկերում, որի վրա 4000 վարորդ ցանկանում է մեկնել սկզբնակետից վերջնակետ: Start–A ճանապարհի վրա ճամփորդության ժամանակը րոպեներով հավասար է ճամփորդների քանակը (T) բաժանած 100-ի, իսկ Start–B-ում՝ հաստատուն 45 րոպե է (նմանապես նրանց դիմացի ճանապարհներին)։ Եթե կետագծերով ճանապարհը գոյություն չունենա (այսինքն երթևեկության ցանցն ընդհանուր առմամբ ունենա 4 ճանապարհ), ապա Start-A-End երթուղին անցնելու համար անհրաժեշտ ժամանակը $a$ վարորդների դեպքում կլինի ${\tfrac {a}{100}}+45$ . Ժամանակը, որն անհրաժեշտ կլինի Start-B-End երթուղին վարելու համար $b$ վարորդների դեպքում կլինի ${\tfrac {b}{100}}+45$ . Քանի որ ընդհանուր 4000 վարորդ կա, $a+b=4000$ պայմանից կարելի է ստանալ հետևություն, որ $a=b=2000$ երբ համակարգը գտնվում է հավասարակշռության մեջ։ Հետևաբար, յուրաքանչյուր երթուղի տևում է ${\tfrac {2000}{100}}+45=65$ րոպե. Եթե որևէ երթուղի ավելի քիչ ժամանակ պահանջեր, ապա Նեշի հավասարակշռություն տեղի չէր ունենա. ռացիոնալ վարորդը ավելի երկար երթուղուց կանցներ ավելի կարճ երթուղու:

Այժմ ենթադրենք, որ A–B կետագիծը ճանապարհ է, որով երթևեկելը չափազանց արագ է, մոտավորապես 0 րոպե: Ենթադրենք, որ ճանապարհը բաց է, և մի վարորդ փորձում է Start–A–B–End երթուղին: Ի զարմանս իրեն նա գտնում է, որ իր ժամանակը ${\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01$ րոպե է դառնում, գրեթե 25 րոպե կարճ: Շուտով 4000 վարորդներից շատերը կփորձեն այս նոր երթուղին: Ժամանակը բարձրանում է 40.01-ից և շարունակում է բարձրանալ: Երբ նոր երթուղին փորձող վարորդների թիվը հասնում է 2500-ի, իսկ 1500-ը դեռ Start-B-End ուղու վրա են, նրանց ժամանակը կկազմի ${\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65$ րոպե, ինչը բարելավում չէ սկզբնական երթուղու համեմատ: Մինչդեռ այդ 1500 վարորդների երթևեկությունը դարձավ $45+{\tfrac {4000}{100}}=85$ րոպե, 20 րոպե ավելի երկար: Նրանք պարտավորված են այժմ նոր երթուղով գնալ՝ անցնելով A կետով, ուստի իրենց ժամանակը կդառնա ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ րոպե։ Ոչ ոք որևէ դրդապատճառ չունի ճանապարհորդելու A-End կամ Start-B ուղիներով, քանի որ ցանկացած վարորդ այդ դեպքում կծախսի 85 րոպե: Այսպիսով, խաչմերուկի բացումը հանգեցնում է բոլորի կողմից դրա անշրջելի փոփոխությանը՝ յուրաքանչյուրի համար ճանապարհի տևողությունը սկզբնական 65-ի դարձնելով 80 րոպե: Եթե բոլոր վարորդները համաձայնվեն չօգտվել A-B ուղուց, կամ եթե այդ երթուղին փակվի, ապա յուրաքանչյուր վարորդ կշահի ճանապարհորդության ժամանակի 15 րոպեի կրճատում:

Հավասարակշռության առկայությունը

Հավասարակշռությունը միշտ գոյություն կունենա եթե կա ենթադրություն, որ բոլոր անձանց երթևեկության ժամանակը ուղու վրա հավասար է:

Դիցուկ $L_{e}(x)$-ը $e$ ուղով ճանապարհորդող յուրաքանչյուր անձի ճամփորդության ժամանակի բանաձևն է, երբ այդ ուղով երթևեկում են $x$ մարդիկ: Ենթադրենք, որ կա երթևեկության գրաֆ, որտեղ $x_{e}$ մարդիկ քշում են $e$ կողով։ Թող $e$-ի էներգիան՝ $E(e)$-ն լինի

$\sum _{i=1}^{x_{e}}L_{e}(i)=L_{e}(1)+L_{e}(2)+\cdots +L_{e}(x_{e})$

(Եթե $x_{e}=0$ թող $E(e)=0$)։ Դիցուկ տրաֆիկի գրաֆի ընդհանուր էներգիան հավասար է նրա բոլոր կողերի էներգիաների գումարին:

Ընտրեք երթուղիներ, որոնք նվազագույնի են հասցնում ընդհանուր էներգիան: Նման ընտրություն պետք է գոյություն ունենա, քանի որ երթուղիների ընտրությունը վերջավոր է: Դա կլինի հավասարակշռության կետը:

Այժմ ենթադրենք հակառակը․ սա կնշանակի, որ կա առնվազն մեկ վարորդ, ով կարող է փոխել երթուղին և բարելավել իր ճամփորդության ժամանակը: Ենթադրենք սկզբնական երթուղին է $e_{0},e_{1},\ldots ,e_{n}$, մինչդեռ նոր երթուղին է $e'_{0},e'_{1},\ldots ,e'_{m}$ ։ Թող $E$-ն լինի երթևեկության գրաֆի ընդհանուր էներգիան․ նկատենք, թե ինչ է տեղի ունենում երբ $e_{0},e_{1},...e_{n}$ երթուղին հանվում է։ Յուրաքանչյուր կողի էներգիան՝ $e_{i}$-ն կկրճատվի $L_{e_{i}}(x_{e_{i}})$-ով, և այսպիսով $E$-ն կկրճատվի ${\textstyle \sum _{i=0}^{n}L_{e_{i}}(x_{e_{i}})}$-ով։ Սա պարզապես ճանապարհորդության ընդհանուր ժամանակն է, որն անհրաժեշտ է սկզբնական երթուղին անցնելու համար: Եթե նոր $e'_{0},e'_{1},\ldots ,e'_{m}$երթուղին ավելացվի, ընդհանուր էներգիան կավելանա նոր երթուղին անցնելու համար անհրաժեշտ ընդհանուր ժամանակով: Քանի որ նոր երթուղին ավելի կարճ է, քան սկզբնական երթուղին, $E$-ն պետք է նվազի սկզբնականի համեմատ՝ հակասելով այն ենթադրությանը, որ երթուղիների սկզբնական խումբը նվազագույնի է հասցրել ընդհանուր էներգիան:

Հետևաբար, ընդհանուր էներգիան նվազագույնի հասցնելու երթուղիների ընտրությունը հավասարակշռության կետն է:

Հավասարակշռություն գտնելը

Վերոհիշյալ ապացույցը ցույց է տալիս մի ընթացակարգ, որը հայտնի է որպես լավագույն արձագանքի դինամիկա, որը գտնում է տրաֆիկի գծային գրաֆի հավասարակշռությունը և ավարտվում է վերջավոր քանակությամբ քայլերով: Ալգորիթմը կոչվում է «լավագույն արձագանք», քանի որ ալգորիթմի յուրաքանչյուր քայլում, եթե գրաֆը հավասարակշռության մեջ չէ, մի վարորդ տալիս է իր լավագույն արձագանքը՝ մյուս բոլոր վարորդների ռազմավարություններին։

Լավագույն արձագանքման դինամիկայի կոդ.

Let P be some traffic pattern.
while P is not at equilibrium:
    compute the potential energy e of P
    for each driver d in P:
        for each alternate path p available to d:
            compute the potential energy n of the pattern when d takes path p
            if n < e:
                modify P so that d takes path p
continue the topmost while

Յուրաքանչյուր քայլում, եթե որոշակի վարորդ կարող է կրճատել իր ժամանակը՝ անցնելով այլընտրանքային ճանապարհի («լավագույն արձագանքը»), ապա դա անելը խստորեն նվազեցնում է գրաֆի էներգիան: Եթե ոչ մի վարորդ չունի լավագույն արձագանք, ապա գրաֆը գտնվում է հավասարակշռության մեջ: Քանի որ գրաֆի էներգիան խստորեն նվազում է յուրաքանչյուր քայլի հետ, լավագույն արձագանքի դինամիկայի ալգորիթմը ի վերջո ավարտին կգա:

Որքա՞ն հեռու է օպտիմալից երթևեկությունը հավասարակշռության մեջ:

Եթե երթևեկության ժամանակի ֆունկցիաները գծային են, այսինքն $L_{e}(x)=a_{e}x+b_{e}$ որոշ $a_{e},b_{e}\geq 0$-ի համար, ապա վատագույն դեպքում՝ էներգիան նվազագույնի հասցնող հավասարակշռության մեջ երթևեկությունը երկու անգամ ավելի վատն է, քան սոցիալապես օպտիմալը:

Ապացույց․ դիցուկ $Z$-ը երթևեկության որոշակի կոնֆիգուրացիա է՝ $E(Z)$ էներգիայով և $T(Z)$ ճանապարհորդության ընդհանուր ժամանակով։ Յուրաքանչյուր կողի համար էներգիան թվաբանական պրոգրեսսիայի գումարն է, և օգտագործելով թվաբանական պրոգրեսսիայի գումարի բանաձևը, կարելի է ցույց տալ, որ $E(Z)\leq T(Z)\leq 2E(Z)$ ։ Եթե $Z_{o}$-ն սոցիալապես օպտիմալ երթևեկության հոսքն է և $Z_{e}$-ն էներգիան նվազագույնի հասցնող երթևեկության հոսքն է, անհավասարությունը ցույց է տալիս, որ $T(Z_{e})\leq 2E(Z_{e})\leq 2E(Z_{o})\leq 2T(Z_{o})$ ։

Այսպիսով, էներգիան նվազագույնի հասցնող հավասարակշռության մեջ ընդհանուր ճանապարհորդության ժամանակը առավելագույնը երկու անգամ ավելի վատն է, քան օպտիմալ հոսքի ժամանակ:

Ցանցի տոպոլոգիայի ազդեցություն

Միլխտայքը ապացուցել է, որ Բրաեսի պարադոքսը կարող է առաջանալ միայն այն դեպքում, եթե ցանցը շարքային զուգահեռ գրաֆ չէ: