Преглед на кода на Парадокс на Браас

'''Парадоксът на Браас''' е [[явление]], при което добавянето на нова връзка в дадена мрежа може да доведе до влошаване на пропускливостта на цялата (или голяма част) от мрежата. Парадоксът е открит от [[Германия|германския]] [[математик]] Дитрих Браас през 1968 г.

В първоначалния си труд<ref>D. Braess, [http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/paradox.pdf Unternehmensforschung 12, 258 (1968)] {{икона|de}}</ref><ref>D. Braess, [http://www.uvm.edu/~pdodds/files/papers/others/2005/braess2005a.pdf On a Paradox of Traffic Planning. Transportation Science, Vol. 39, No. 4, November 2005, pp. 446 – 450] (превод на английски от оригиналната статия)</ref> Браас изследва парадоксалната ситуация, при която изграждането на нова [[улица]] (т.е. локално увеличение на капацитета на една мрежа) води до удължено време на пътуване за всички участници в движението (т.е. капацитетът на мрежата се намалява). Приема се, че всеки участник в движението избира маршрута си така, че да няма друг маршрут с по-кратко време за пътуване.

== Откритие и определение ==
През 1968 г. Дитрих Браас, математик в [[Рурски университет|Рурския университет]] в Германия, занимаващ се с моделиране на трафика, забелязва, че потокът в една пътна мрежа може да бъде забавен от добавянето на нов път към нея. Прозрението на Браас било, че ако всеки водач взема оптималното от гледна точка на личния му интерес решение относно маршрута си, то някои преки пътища ще бъдат предпочетени от голям брой водачи, което ще увеличи времето на пътуване (поради задръстване). По-формално казано, [[равновесие на Наш|равновесието]] на [[Наш]] може да не съвпада с оптималния поток през дадена мрежа.<ref>New Scientist, 42nd St Paradox: Cull the best to make things better, 16 January 2014 by Justin Mullins </ref>

Парадоксът може да бъде определен по следния начин:<blockquote>„Нека е дадена пътна мрежа. За всяка точка от мрежата са дадени броя автомобили и желаната им крайна цел. При тези условия се търси разпределението на трафика. Дали дадена улица е за предпочитане пред друга зависи не само от качеството на пътя, а и от натовареността ѝ. Ако всеки водач избере маршрута, който изглежда най-изгоден за него, това може да доведе до време на пътуване над минималното. Освен това се демонстрира с пример, че разширяване на пътната мрежа може да доведе до такова преразпределение на трафика, че времето за пътуване да се увеличи.“</blockquote>

== Примери в реални ситуации ==
=== Пътен трафик ===
В Сеул, Южна Корея, времето за пътуване се съкращава след премахването на магистрална отсечка като част от възстановителния проект Чеонггйечеон. В Щутгарт, Германия, след инвестиции в пътната мрежа трафикът не се подобрява, докато една от новопостроените отсечки не бива затворена.<ref name="Knödel1969">{{Cite book|last = Knödel|first = W.|title = Graphentheoretische Methoden Und Ihre Anwendungen|url = http://books.google.com/books?id=bJ22pwAACAAJ|date =31 януари 1969|publisher = [[Springer-Verlag]]|isbn = 978-3-540-04668-4|pages = 57 – 59}}</ref> Затварянето на 42-ра улица в [[Ню Йорк]] намалява задръстванията в района.<ref>{{Cite news|last = Kolata|first = Gina|authorlink = Gina Kolata|date = 25 декември 1990|publisher = New York Times|url = http://www.nytimes.com/1990/12/25/health/what-if-they-closed-42d-street-and-nobody-noticed.html|title = What if They Closed 42d Street and Nobody Noticed?|accessdate = 16 ноември 2008}}</ref> През 2008 г. Юн, Гастнър и Йеонг демонстрират, че това може да се случи и при определени маршрути в Бостън, Ню Йорк и Лондон и посочват кои улици трябва да се затворят, за да се съкрати времето за пътуване.<ref name="YounGastner2008">{{Cite journal|last1 = Youn|first1 = Hyejin|last2 = Gastner|first2 = Michael|last3 = Jeong|first3 = Hawoong|title = [http://arxiv.org/pdf/0712.1598.pdf Price of Anarchy in Transportation Networks: Efficiency and Optimality Control]|journal = [[Physical Review Letters]]|volume = 101|issue = 12|year = 2008|issn = 0031 – 9007|pmid = 18851419|doi = 10.1103/PhysRevLett.101.128701|arxiv = 0712.1598|bibcode = 2008PhRvL.101l8701Y|pages = 128701}}</ref>

=== Електроразпределение ===
През 2012 г. учени от института Макс Планк в [[Гьотинген]], Германия демонстрират чрез [[компютърна симулация]], че този феномен може да се наблюдава и в [[Електроснабдителна мрежа|електроснабдителни мрежи]], където производството на [[електроенергия]] е децентрализирано<ref>[http://www.rdmag.com/news/2012/09/study-solar-and-wind-energy-may-stabilize-power-grid www.rdmag.com]</ref>. Същата година международен екип от учени публикуват документ, доказващ, че парадоксът на Браас може да се прояви в [[Мезоскопична физика|мезоскопични]] системи<ref>с мащаб между между макроскопичен и микроскопичен.</ref> от електрони. По-конкретно те показват, теоретично и експериментално, че добавянето на път за електроните в наноскопична мрежа парадоксално намалява [[проводимост]]та ѝ<ref>[http://arxiv.org/abs/1112.1170 arxiv.org]</ref>.

=== Биология ===
{{раздел-мъниче}}

== Теоретичен пример ==
[[Файл:Braess_paradox_road_example.svg|ляво|500x500px]]

Нека е дадена пътна мрежа като тази на фигурата вляво и нека има 4000 водача, които желаят да се придвижат от точката, обозначена с английската дума ''Start'', до точка ''End''. Пътят, свързващ ''Start'' с точка А, е сравнително тесен и времето на пътуване зависи от натовареността:

<math> t_{Start \rightarrow A} = \frac{N_a}{100}</math>,

където <math> t_{Start \rightarrow A}</math> е времето за пътуване в минути, а <math>N_a</math> е натовареността на пътя към ''А'', измерена в брой автомобили. От друга страна отсечката ''Start-B'' е с висок капацитет (магистрала), но е по-дълга, и времето на пътуване по нея на практика не зависи от натовареността:

<math>t_{Start \rightarrow B} = 45 min</math>

От другата срана на мрежата (към точка ''End'') положението е същото, само че магистралната и бавната отсечка са разменени, така че пътуването по маршрут ''А-End'' отнема винаги 45 мин., а по другата отсечка зависи от натовареността по гореописания начин.

Ако пътят обозначен с пунктир не съществува, то двата маршрута (през точки ''A'' или ''B'') са еквивалентни и времетраенето на пътуването по тях ще е:

<math> t_{Start \rightarrow A \rightarrow End} = \frac{N_a}{100} + 45 min </math>

<math> t_{Start \rightarrow B \rightarrow End} = 45 min + \frac{N_b}{100}</math>

Ако водачите действат рационално и избират винаги по-малко натоварения път (защото е по-бърз), се стига до равновесно положение, при което по всеки от двата маршрута преминават 2000 автомобила (<math>N_a = N_b = 2000 </math>) и пътуването отнема едно и също време:

<math>t_{Start \rightarrow A \rightarrow End} = t_{Start \rightarrow B \rightarrow End} = 45 min + 20 min = 65 min</math>.

Нека сега предположим, че пунктираната линия между точки ''А'' и ''B'' обозначава път с пренебрежимо кратко (или много кратко) време на пътуване. Тогава рационалните шофьори, тръгвайки от ''Start'', винаги ще предпочетат по-тесния, но и по-кратък път ''Start-А'', защото по него пътуването отнема най-много <math>\frac{4000}{100} = 40 min</math>, докато по магистралата е най-малко 45 минути. По същата причина всеки рационален шофьор, щом стигне до втората част на трасето би избрал по-тесния, но къс път (отсечката ''B-End''). Така общото време за пътуване е 80 минути.

Разбира се, шофьорите биха могли да постигнат предварително съгласие да не използват бързата отсечка свързваща ''А'' и ''B'', за да спестят 15 минути от пътуването си. Но тъй като за всеки водач поотделно отсечката дава предимство, социално оптималното разпределение не е стабилно и не се осъществява. Така се стига до парадокса на Браас.

== Източници ==
{{Reflist}}

[[Категория:Теория на игрите]]
[[Категория:Рурски университет]]