Привет,
столкнулся с интересной задачкой, которую очень хочется решить правильно.
Натолкните пожалуйста на мысль, о возможных алгоритмах для ее решения, спасибо.


В двух соседних королевствах есть по N городов в каждом. Правители договорились соединить их N дорогами таким образом, чтобы между двумя городами из разных королевств была только одна дорога.
Строительство дорог ведется совместными усилиями, но количество работников для строительства дороги между двумя  городами может быть разной для каждого из королевств.
При строительстве самой первой дороги, жребием определяется королевство, которое первое выбирает один из своих городов. Затем другое королевство выбирает один из своих городов и между ними строится дорога. Для строительства следующей дороги, право первым выбрать город, еще не соединенный никакой дорогой, переходит к королевству, которое выбирало город для предыдущей дороги во вторую очередь и так далее меняется очередность права первым выбрать город для очередной дороги, пока не будут построены все N дорог.
Задачей каждого королевства, является трудоустройство большего числа работников, чем у соседнего королевства.

Исходные данные:
Количество городов в каждом из королевств: 2 <= N <= 10
Разница в количестве работников, необходимых для постройки дорог, между первым и вторым королевством: W[1..N, 1..N], где W[i, j] - это целое число от -255 до 255, разница в количестве работников между первым и вторым королевством, которые будут заняты при постройке дороги между i-м городом первого и j-м городом второго королевства.

Каких алгоритмов необходимо придерживаться при ведении строительства дорог от лица первого королевства, если второе королевство также будет стараться использовать самый оптимальный алгоритм для своей победы при выборе городов?


Пример:
N = 2
W = {{ 2, 2 }, { -4, -2 }}

Предположим, что второе королевство для первой дороги делает выбор первым и предлагает первый город, тогда нам как представителю первого королевства выгоднее соединить его дорогой с первым городом и трудоустроить на 2 работника больше. Тогда для второй дороги мы трудоустроим на 2 работника меньше и в результате будет ничья.
Если мы для первой дороги выберем второй город первого королевства, то по результатам строительства двух дорог мы трудоустроим на 2 работника меньше и проиграем.

Edited by author 21.06.2014 17:51