Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[171]

мы

Х\

- х2

4,

Х\

- х5

5,

х2

- Х4

-6

х3

- х2

1,

Х4

- Х\

з,

Х4

- х3

5,

Х4

- х5

10,

Х5

- х3

-4

Х5

- Х4

-8

25.5-3 Может ли в графе ограничений кратчайший путь из vq в какую-то вершину иметь положительный вес?

25.5-4 Сведите задачу о кратчайшем пути между парой вершин к задаче линейного программирования.

25.5-5 Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы при решении системы т ограничений на разности с п неизвестными он работал за время О (inn).

25.5-6 Как с помощью алгоритма, аналогичного алгоритму Беллмана-Форда, решить систему ограничений на разности, пользуясь графом ограничений без дополнительной вершины vq!

25.5-7* Покажите, что решение системы разностных ограничений с п неизвестными, находимое алгоритмом Беллмана-Форда, имеет (среди всех решений этой системы, в которых все переменные неположительны) максимальное значение суммы х\-\-х2-\-.. .+ хп.

25.5-8* Покажите, что решение системы разностных ограничений Ах Ь с п неизвестными, находимое алгоритмом Беллмана-Форда, имеет минимально возможное значение величины тах{жг} - тт{жг} среди всех оещений этой системы. Чем полезно это обстоятельство при планировании строительства?

25.5-9 Рассмотрим систему неравенств, в которой каждое неравенство является либо ограничением на разности, либо неравенством вида Xi а, либо неравенством вида Xj а. Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы он находил хотя бы одно решение или устанавливал несовместность таких систем.

25.5-10 Пусть к системе ограничений на разности добавлено некоторое количество уравнений вида жг- = Xj + b. Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы он мог находить решения таких систем.

25.5-11 Разработайте эффективный алгоритм для нахождения решения системы ограничений на разности, в котором все неизвестные являются целыми числами (константы в ограничениях не обязаны быть целыми, но их можно заменить на их целые части).


25.5-12* Разработайте эффективный алгоритм для нахождения решения системы ограничений на разности, если все переменные разбиты на две группы: целые (для которых допустимы только целые значения) и вещественные (для которых такого ограничения нет).

Задачи

25-1 Модификация алгоритма Беллмана-Форда по Иену Выберем порядок, в котором обрабатываются рёбра в алгоритме Беллмана-Форда, следующим образом. Пронумеруем каким-либо образом вершины графа и разобьем множество Е вершин графа на два подмножества: Ef, состоящее из стрелок, идущих из вершины с меньшим номером в вершину с большим номером, и Еь, состоящее из стрелок, идущих из вершины с большим номером в вершину с меньшим номером. Пусть Gf = (V,Ef) и Gj, = (V, Еь) (через V обозначено множество вершин графа). Начнём с такого очевидного наблюдения:

(а)Покажите, что графы Gf и Gb ацикличны, причём расположение вершин в порядке возрастания (убывания) номеров задает топологическое упорядочение на графе Gf (Gb)-

Будем теперь проводить релаксацию ребер при каждой итерации цикла в алгоритме Беллмана-Форда в следующем порядке: сначала перебираем вершины в порядке возрастания номеров и для каждой вершины подвергаем релаксации все выходящие из нее ребра графа Ef, затем перебираем все вершины в порядке убывания номеров и для каждой вершины подвергаем релаксации все выходящие из нее ребра графа Еь-

(б)Пусть G не содержит циклов отрицательного веса, достижимых из вершины s; докажите, что после [~У/2] итераций цикла равенства d[v] = S(s, v) будут выполняться для всех v £ V.

(в)Оцените время работы описанной модификации алгоритма Беллмана-Форда.

25-2 Вложенные ящики

Будем говорить, что d-мерный ящик размеров (х\, х2, , x,i) вкладывается (nests) в ящик размеров (у\,у2, -,y<l), если у множества { 1, 2,..., d } существует такая перестановка тг, что хж <

уъжтг(2) < У2, - ,2(0 < Ув,-

(а)Покажите, что отношение «вкладываться» транзитивно.

(б)Опишите эффективный способ проверить, вкладывается ли один d-мерный ящик в другой.

(в)Даны п различных d-мерных ящиков. Требуется узнать, какое максимальное число из них можно последовательно вложить друг в друга (первый во второй, второй в третий и т.д.). Укажите эффективный алгоритм для решения этой задачи и оцените время его работы.

25-3 Арбитражные операции

Арбитражными операциями (arbitrage) называется следующий


способ извлекать прибыль из несогласованности курсов обмена валют. Предположим, что один доллар можно обменять на 0,7 фунта стерлингов, один фунт стерлингов - на 9,5 франков, и один франк - на 0,16 доллара. Тогда, обменивая 1 доллар в указанной последовательности, в результате можно получить 1,064 доллара и тем самым остаться с прибылью 6,4%.

Пусть имеются га валют (пронумерованных от 1 до га) и массив R[l..n, 1..га], в котором записаны курсы обмена (единицу валюты г можно обменять на R[i,j] единиц валюты j).

(а)Разработайте эффективный алгоритм, позволяющий выяснить, существует ли такая последовательность (ii, г2, , гк), что

R[ii, i2\ R[i2, гз]R[ik-i, h] R[ik, ч] > 1-

Оцените время работы вашего алгоритма.

(б)Разработайте эффективный алгоритм, печатающий такую последовательность, если она существует. Оцените время его работы.

25-4 Алгоритм Габоу нахождения кратчайших путей с помощью масштабирования

Пусть нам дан взвешенный ориентированный граф G = (V,E), в котором веса всех ребер являются целыми неотрицательными числами, не превосходящими W. Покажем, как можно найти кратчайшие пути из одной вершины за время O(ElgW).

Пусть к = \lg(W + 1)1 - количество битов в двоичном представлении числа W. Для г = 1,2,..., к положим Wi(u,v) = \w(u,v)/2к~г\ (иными словами, Wi(u,v) получается из w(u, v) отбрасыванием к - г младших битов в двоичном представлении числа w(u,v)). Например, если к = 5 и w(u,v) = 25 = (11001), то ws(u,v) = (НО) = 6. В частности, w\ принимает только значения 0 и 1, определяемые старшим разрядом, a wk = w.

Пусть Si(u,v) - вес кратчайшего пути из и в v относительно весовой функции иц (в частности, 5k(u,v) = S(u,v)). Алгоритм, о котором пойдёт речь в этой задаче, найдёт сначала все Si (s, v) (s - исходная вершина), затем все (s, и), и так далее, пока не дойдёт до Sk(s,v) = S(s,v). Далее мы полагаем, что \Е\ \V\ - 1; как мы увидим, стоимость нахождения Si при известном <S4- i есть О(Е), так что алгоритм будет работать за время О(кЕ) = O(ElgW).

Такой план решения задачи - замена исходных данных их двоичными приближениями с последовательным уточнением - называется масштабированием (scaling)

(а)Пусть S(s,v) \Е\ для всех вершин v £ V (предполагается, что \Е\ \V\ - 1 и веса являются целыми неотрицательными числами). Покажите, что можно найти S(s, v) для всех v £ V за время О(Е).

(б)Покажите, что можно подсчитать Si(s,v) для всех v £ V за время 0(E).



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]