нется по С I С первый, С убьет Б) х Р(С убьет д I С первый, С убьет Б, д промахнется по С)= = (1/2)(1)(1/2)(1)=1/4

Аналогично

Р (**)= (1/2) (1/5) (1) (1/2) (1)=1/20

Обратите внимание на то, что структура дерева гарантирует взаимнооднозначное соответствие между конечным событием и единственным путем от корня в конечной вершине. Дерево было построено так, чтобы вычисление различных сложных условных вероятностей сводилось не более, чем к перемножению всех чисел вдоль ребер данного пути. Мы успешно вычисляем составные вероятности по мере «наращивания» дерева. Тогда Рс=Р(,С выживет)=1/4+1/20=3/10. Теперь перейдем к Б: а

Рб = Р {Б выживет) ==Р (Б убьет С)хР(,Б убьет д\Б убьет С) = = Р{Б первый)X(Б убьет С\Б первый)х хР{Б убьет д\Б убьет С) =

= (l/2)(4/5)f;(2/5)(4/9) = 8/45 /1=1

с учетом того, что все исходы, в которых Б побеждает расположены на правой верхней ветви дерева рис. 6.1.6 (все эти события обозначены номерами в кружочках).

Вероятность выживания д Рд можно получить из условия нормировки Рс +Рб +Рд =1- Получим Рд =47/90. Таким образом, немного подумав, д может гарантировать себе наибольшие шансы на выживание в ситуации, которая на первый взгляд казалась для него крайне невыгодной.

Упражнения 6.1

6.1.1. Воспользуйтесь алгоритаом ODDMS, чтобы построить магический квадрат 7X7.

6.1.2. Выпишите в явном виде части X иУ чисел, составляющих магический квадрат, построенный в упр. 6.1.1 (см. рис. 6.1.2).

*6.1.3. Магические квадраты. Докажите, что сумма элементов по строке, столбцу и главной диагонали магического квадрата NxN равна [iV(№-bl)]/2.

6.1.4. Воспользуйтесь алгоритаом DEMS для построения магического квадрата8х8. Совпадает ли он с квадратом, построенным на рис. 6.1.3?

6.1.5. Покажите явно расположение пометок в алгоритме DEMS.

**6.1.6. Алгоритм ODDMS (правильность). Покажите, что алгоритм располагает UV(N+l)y2 главных диагоналей так, что сумма по каждой из них равна

6.1.7. Алгоритмы ODDMS и DEMS (сложность). Покажите явно, что эти алгоритм имеют сложность О(Л).

*L6.1.8. Латинские квадраты (полное построение). Латинским квадратом называется матрица NxN, элементы которой выбраны из целых чисел от 1 до так, что каждое число встречается только один раз в каждой строке и каждом столбце. Заметим, что каждое из N чисел используется N раз. Полностью постройте алгоритм заполнения латинского квадрата.

**L6.1.9. Игра на матрице. Постройте выигрышную стратегию для одного из игроков в следующей игре. Два игрока, «нечетный» и «четный», по очереди ставят единицы и нули в незанятые позиции поля JVxN. Каждый из игроков может ставить 1 или О в произвольную свободную позицию, тем самым занимая е е. Заметим, что «нечетный» не обязательно должен пользоваться только единицами, а «четный» - нулями. Игра продолжается до заполнения всех позиций. После этого суммируются числа вдоль каждой строки, иаждого столбца и главных диагоналей. Число ODD нечетных сумм далее сравнивается с числом EVEN четных сумм. Если ODD>EVEN, выигрывает «нечетный»; если EVEN>ODD, выигрывает «четный»; если ODD=EVEN, результат считается ничейным.

**L6.1.10. Алгоритм SEMS (полное- построение). Постройте полностью алгоритм SEMS (однократно четные магические квадраты), для заполнения магических квадратов NXN при Л/=4/и-Ь2, т=1, 2, 3, ... .

6.1.11. Найдите выигрышную стратегию игрока А в игре в «нимбы» для полей 10 X Ю, 9x9, 9X10.

6.1.12. Какова доллша быть стратегия игрока В при игре в «нимбы» на четно-нечетной доске?

**L6.1.13. Алгоритм EXNIM (формулировка, реализация). Сформулируйте и запрограммируйте алгоритм EXNIM.

*6.1.14. Алгоритм EXNIM (сложность). Проанализируйте сложность программы для упр. 6.1.13.

*L6.1.15. Простой ((.HuMti (полное построение). Это хорошо известная игра двух лиц, в которой игроки по очереди берут предметы из наборов. Имеется п наборов предметов. Каждый набор содержит т,- предметов при i=l, 2, . . . , п. Игрок при очередном ходе берет один или несколько предметов из какого-то одного набора. Игра продолжается до тех пор, пока все предметы не будут взяты; игрок, сделавший последний ход, считается победителем.

Постройте полностью алгоритм игры в эту игру. Указание: воспользуйтесь двоичными числами для представления количества предметов в каждом наборе.

*6.1.16. Классические нимбы (эвристика). В классические «даимбы» играют аналогично описанной нами игре «иимбы» с той разницей, что необязательно занимать все квадраты, в которые можно попасть, не пересекая границы поля или квадрата противника. Не существует также предпочтительных направлений. Например, на первом ходе А не обязан занимать целую строку, а молгет занять строку любого размера из расположенных подряд квадратов. Общая стратегия выигрыша для этой игры неизвестна. Разработайте некоторые полезные эвристики для игры п классические нимбы.

*6.1.17. Фальшивые монеты. Имеется 12 не различимых по внешнему виду монет. Одна монета фальшивая и отличается от остальных по весу. Даны простые рычажные весы без гирь. Определите, которая монета фальшивая. Попытайтесь изобрести алгоритм, требующий только трех взвешиваний, чтобы идентифицировать фальшивую монету и определить, «тялжлая» она или «легкая».

**6.1.18. Головоломка кв». Рассмотрите опять пример из разд. 3.3 с головоломкой «8». Разработайте эфс11ективный алгоритм, проверяющий, возможно ли (не обязательно выполняя это) перевести одну заданную конфигурацию в другую. Попытайтесь обобщить ваш алгоритм на головоломку «Л». Указание: воспользуйтесь соображениями четности.

L6.1.19. Крестики-нолики, Постройте алгоритм беспроигрышной игры в крестики-нолики.

L6.1.20. Трехмерная игра крестики-нолики. Эта игра похожа на обычные крестики-нолики, но играется в кубе, ребром три или четыре. Игрок выигрывает, заполнив строку, столбец или диагональ. Разработайте алгоритм реализации этой игры и используйте его для проверки нескольких стратегий. Существует ли выигрышная стратегия для куба 3x3x3?

6.1.21. Повторите анализ тройной дуэли для общего случая вероятностей попадания р1, Ръ и Рз, где pi>pz>ps>0.

6.1.22. Из обычной колоды взяты карты пик и червей. 13 пиковых карт выложены по порядку от туза до короля. Карты червей перетасованы и выложены вниз лицевой стороной. Их переворачивают по одной. Как только очередная карта перевернута, соответствующая карта пик удаляется из ряда. Игрок выигрывает, если карты червей окажутся в таком порядке, что не возникает «просвета» между любыми из остающихся карт пик. Какова вероятность выигрыша в этой игре?

L6.1.23. Вероятностный вариант крестиков-ноликов. Пронумеруем клетки обычной игры в крестики-нолики 3x3 числами от I до 9. Игрок, пытающийся поместить крестик или нолик в клетку i, с вероятностью р,- (0>р,->1) не сможет сделать этого, теряя ход. Центральная клетка всегда имеет большую вероятность потери хода, чем любая из остальных. Запрограммируйте и испытайте алгоритм игры, приняв различные наборы {/?;} и различные стратегии игры.

*6.1.24. Модифицированная рулетка. В игре используется рулеточное колесо с номерами от I до N. Игрок, ставящий D долларов ня число k, выигрывает (k-{-2)D долларов, если это число выпадает при данной ставке. Возможно ли играть в эту игру, никогда не проигрывая?

*L6.1.25. Ноль за единит (моделирование). Смоделируйте следующую игру, иногда называемую «ноль за единицу», и экспериментально подберите хорошее правило принятия решений.

Зафиксирована очередность ходов двух игроков. Каждый из игроков, когда иа-ступяет его очередь, бросает игральную кость до тех пор, пока не решит прекратить иЛи не выпадет I. Если выпадает 1, за этот ход игроку приписывается ноль очков; если единица ни разу не выпадет, ему приписывается сумма всех выпавших чисел. Очки, полученные за все ходы, суммируются в конце игры. Выигрывает игрок, получивший наибольшую сумму очков за все N ходов.

6.2. Кратчайшие пути

Пусть нам дана часть карты дорожной сети, показанная на рис. 6.2.1 (где 32 @ 70 означает 32 мили при г,азрешенной скорости до 70 миль в час), и нужно найти наилучший мар1лрут от Лексингтона (Lexington) до Дэнвилла (Danville). Такая задача выгл»!, достаточно простой, но небольшое размышление выявляет, что «наилучш™-,» jp. шрут могут определять многие факторы. Например, к этим факторе.,, относятся: (1) расстояние в милях; (2) время прохождения маршрута с учетом ограничений скорости; (3) ожидаемая продолжительность поездки с учетом дорожных условий и плотности движения; (4) задержки, вызванные проездом через города или объездом городов; (5) число городов, которые необходимо посетить, например, в целях доставки грузов.

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