Игра с минимальными затратами на связующее дерево
Игра связующего дерева с минимальной стоимостью ( игра MCST ) — это разновидность кооперативной игры . В игре MCST каждый игрок является узлом полного графа . Граф содержит дополнительный узел — узел снабжения , обозначаемый s . Цель игроков состоит в том, чтобы всех их соединил путь к s . Для этого им необходимо построить связующее дерево . Каждое ребро в графе имеет стоимость, и игроки строят остовное дерево с минимальной стоимостью . Тогда возникает вопрос, как распределить стоимость этого МЦСТ между игроками?
Решение, предлагаемое теорией кооперативных игр, состоит в том, чтобы рассмотреть стоимость каждой потенциальной коалиции – каждого подмножества игроков. Стоимость каждой коалиции S — это минимальная стоимость остовного дерева, соединяющего только узлы в S с узлом предложения s . Стоимость S стоимость S. минус Используя эти определения, можно применять различные концепции решений из теории кооперативных игр. Игры MCST были представлены компанией Bird в 1976 году. [1]
Характеристики
[ редактировать ]- Ядро каждой игры MCST не пусто. [1] [2]
- Ядрышко — единственная точка пересечения ядра и ядра . [3]
- Если базовая сеть представляет собой дерево, то ядрышко совпадает с ядром. [4]
Вычисление
[ редактировать ]- Одно решение в ядре можно прочитать непосредственно из любого графа связующего дерева с минимальной стоимостью, связанного с проблемой. [2]
- Существует алгоритм, который требует O(n 2 ) элементарные операции по вычислению каждой дополнительной точки в ядре. [3]
- В обычных играх MCST вычисление ядрышка является NP-сложным; доказательство проводится путем редукции к задаче о покрытии минимального множества . [5] Существует алгоритм, вычисляющий ядрышко за время O( n 3 | B |), где B — множество соответствующих коалиций (вообще говоря, |B|=2 н , но в некоторых особых случаях актуальна только часть коалиций). [6]
- Если базовая сеть представляет собой дерево , то ядрышко можно вычислить за O( n 3 ) время, а значение Шепли можно вычислить за время O( n ). [7] Время выполнения вычисления ядрышка можно сократить до O( n log n ) с помощью эффективно объединяемых куч . [8] В частных случаях ядрышко можно вычислить за время O( n ). [4]
Захватывающие лесные игры
[ редактировать ]Игра охватывающего леса с минимальной стоимостью (игра MCSF) представляет собой обобщение игры MCST, в которой допускается наличие нескольких узлов снабжения. В общем, ядро игры MCSF может быть пустым. [1] Однако, если базовая сеть представляет собой дерево, ядро всегда непусто, а точки ядра можно вычислить за сильно полиномиальное время . [9]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Берд, CG (1976). «О распределении затрат для связующего дерева: теоретико-игровой подход» . Сети . 6 (4): 335–350. дои : 10.1002/net.3230060404 .
- ^ Jump up to: а б Гранот, Дэниел; Губерман, Гур (1 декабря 1981 г.). «Минимальная стоимость охватывающего дерева игр» . Математическое программирование . 21 (1): 1–18. дои : 10.1007/BF01584227 . ISSN 1436-4646 . S2CID 26198019 .
- ^ Jump up to: а б Гранот, Дэниел; Губерман, Гур (1 июля 1984 г.). «О ядре и ядрышке остовного дерева игр минимальной стоимости» . Математическое программирование . 29 (3): 323–347. дои : 10.1007/BF02592000 . ISSN 1436-4646 . S2CID 12124235 .
- ^ Jump up to: а б Гранот, Д.; Машлер, М.; Оуэн, Г.; Чжу, WR (1 июня 1996 г.). «Ядро/ядрышко стандартной древовидной игры» . Международный журнал теории игр . 25 (2): 219–244. дои : 10.1007/BF01247104 . ISSN 1432-1270 . S2CID 120669939 .
- ^ Фэйгл, Ульрих; Керн, Уолтер; Койперс, Йерун (1 декабря 1998 г.). «Вычисление ядрышка в играх на связующем дереве с минимальной стоимостью NP-сложно» . Международный журнал теории игр . 27 (3): 443–450. дои : 10.1007/s001820050083 . ISSN 0020-7276 . S2CID 46730554 .
- ^ Кейперс, Йерун; Солимоси, Тамаш; Аартс, Гарри (1 сентября 2000 г.). «Вычисление ядрышка некоторых комбинаторно-структурированных игр» . Математическое программирование . 88 (3): 541–563. дои : 10.1007/PL00011385 . ISSN 1436-4646 . S2CID 13149058 .
- ^ Мегиддо, Нимрод (август 1978 г.). «Вычислительная сложность подхода теории игр к распределению затрат для дерева». Математика исследования операций . 3 (3): 189–196. дои : 10.1287/moor.3.3.189 . ISSN 0364-765X .
- ^ Галил, Цви (1 января 1980 г.). «Применение эффективных объединяемых куч для задач оптимизации на деревьях» . Акта Информатика . 13 (1): 53–58. дои : 10.1007/BF00288535 . ISSN 0001-5903 . S2CID 39221796 .
- ^ Гранот, Дэниел; Гранот, Фрида (1992). «Вычислительная сложность подхода к распределению затрат для решения задачи охватывающего леса с фиксированной стоимостью» . Математика исследования операций . 17 (4): 765–780. дои : 10.1287/moor.17.4.765 . ISSN 0364-765X . JSTOR 3690069 .