Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Сетевые игровые модели и парадокс Браеса
Сетевые модели и игры трафика (congestion games), как раздел теории игр, впервые были определены в 1973 году Робертом Розенталем (Robert W. Rosenthal). В качестве примеров применения теории игр в сетевых моделях можно привести моделирование транспортных сетей или прохождение интернет траффика. В планировании распределенных вычислений с помощью сетевых моделей можно моделировать выполнение сложноструктуированных заданий с зависимостями по данным, а также возникновение задержек при передаче данных между узлами и доменами вычислительных узлов. В подобных моделях значение имеет не только кратчайший путь от вершины отправления до вершины назначения, важным фактором является уровень загрузки ресурсов: объем трафика в различных ветвях сети и связанные с ним задержки. Сетевая модель задается ориентированным графом, ветви которого представляют собой магистрали и каналы передачи данных, а вершины - пункты пересадки, перекрестки или точки разделов сети, маршрутизаторы и т.п. В качестве примера сетевой задачи можно привести парадокс Браеса. Рассмотрим модель на рис. 4.3, а: каждый день большое количество автомобилей совершает поездку из пригородного города S в промышленный и бизнес центр – город t. Причем существует два различных S-t маршрута: транзитом через город A или через город B. Качество и продолжительность магистралей между городами различно. Так, дороги S-B и A-t имеют много полос, покрывают большое расстояние, и вне зависимости от уровня траффика время перемещения по ним составляет 1 час (соответствующее время отмечено на ребре на рис. 4.3, а). Дороги S-A и B-t относительно короткие, но однополосные, поэтому время движения x по ним пропорционально загруженности движения. Например, если дорогу S-A-t выберут 2/3 от общего количества участников движения S-t, то время в пути до города A для каждого в среднем составит 2/3 часа или 40 минут. Возникает вопрос, возможно ли в такой системе равновесие и каким образом оно достигается. Очевидно, что каждый участник движения стремиться минимизировать время в пути и каждый следующий день будет выбирать тот путь, который по его предыдущему опыту обеспечивает наименьшую задержку. Логично предположить, что из-за симметричности путей S-A-t и S-B-t после некоторого периода переходных процессов потоки движения распределятся между ними равномерно.
На рис. 4.3, б пунктирной линией представлены два потока с уровнем загрузки 0.5. Время в S-t пути, таким образом, составляет 0.5+1 = 1.5 часа на каждом из маршрутов.
а б
Рис. 4.3. Парадокс Браеса. Первоначальная структура сети (а) и распределение траффика (б)
Данная ситуация, очевидно, является равновесной, так как ни одному из участников невыгодно изменять собственный маршрут: с добавлением нового участника загруженность нового маршрута незначительно, но превысит 0.5, а значит время в пути будет больше по сравнению со старым маршрутом. а б
Рис. 4.4. Парадокс Браеса. Модифицированная структура сети (а) и новое распределение траффика (б)
Предположим далее, что администрация области решила радикально улучшить транспортную систему и в экспериментальном режиме установила между городами A и B телепортер, позволяющий мгновенно перемещаться по маршруту A-B. Модифицированная структура сети представлена на рис. 4.4, а и включает в себя ребро A-B с весом 0. С учетом этой модификации новое равновесное распределение траффика представлено на рис. 4.4, б пунктирной линией: весь поток движется по единственному маршруту S-A-B-t, уровень его загрузки равен 1, а среднее время в пути: x + 0 + x = 2 часа. Действительно, при попытке какого-либо из участников изменить маршрут и срезать через дороги S-B или A-t, его время в пути останется неизменным: 1+x = 2 часа. Путь A-A-B-t при этом станет немного быстрее из-за отклонения одного участника и, тем самым, более выгодным по сравнению с объездным путем. Таким образом, данное кажущееся улучшение транспортной сети с применением новых технологий на треть увеличивает среднее время в пути для всех участников движения. При этом пути S-A-t и S-B-t остались неизменными и при равномерном распределении траффика между ними (как на рис. 4.3, б), без использования телепортера A-B, можно уменьшить время в пути обратно до 1.5 часов. Однако с учетом рационального эгоистичного поведения каждого участника такое равномерное распределение траффика не является устойчивым в модифицированной структуре сети: каждому участнику выгодно воспользоваться телепортером, пока им не воспользовались другие, и уменьшить время в пути до 1 часа. Стоит отметить, что данный парадокс не является чисто умозрительным, и подобные закономерности наблюдаются, например, в компьютерных сетях и в физических процессах.
|
|||||
Последнее изменение этой страницы: 2020-12-09; просмотров: 186; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.184.117 (0.007 с.) |