Главная Промышленная автоматика.


Легко убедиться в том, что ддя фиксированного к кодиче-ство различных преобразований при fe-выборе, которые необходимо рассмотреть при наличии п вершин, равно 0(га*). Например, при к = 2 точное количество таких преобразований равно п(п - 3)/2. Однако время, которое требуется ддя получения какого-либо из локально-оптимальных маршрутов, может оказаться значительно больше этой величины, поскольку ддя получения этого локально-оптимального маршрута надо выполнить довольно много локальных преобразований, а калсдое удучшаюшее преобразование связано с вве-Рис. 10.22. Выбор эле- дением новых ребер, которые могут участвовать в ментов маршрута последующих преобразованиях и еще больше улучшают дан-после удаления трех ный маршрут. В работе [68] показано, что с практической ребер точки зрения "выбор с переменной глубиной" (т.е. выбор с

разными значениями к на разных этапах) является чрезвычайно эффективным методом и с большой вероятностью обеспечивает получение оптимального маршрута для задач коммивояжера с 40-100 городами.

Размещение блоков

Задачу одномерного размещения блоков можно сформулировать следующим образом. Есть неориентированный граф, вершины которого называются "блоками". Ребра графа помечаются "весами", причем вес м>(а, Ь) ребра (а, Ь) представляет собой количество "проводов" между блоками а и Ь. Задача состоит в том, чтобы упорядочить вершинырь Рг Рл таким образом, чтобы сумма величин i - j\ w(Pi,Pj) по всем парам и j была минимальной, т.е. надо минимизировать сумму длин проводов, необходимых ддя соединения всех блоков требуемым количеством проводов.

У задачи размещения блоков есть ряд приложений. Например, "блоки" могут представлять собой логические платы в стойке; весом соединения между платами в этом случае является количество соединяющих их проводников. Аналогичная задача возникает и в случае проектирования интегральных схем на основе набора стандартных модулей и взаимосвязей между ними. Более общий случай задачи одномерного размещения блоков допускает размещение "блоков", имеющих определенную высоту и ширину, в двумерной области с минимизацией суммы длин проводов, соединяющих эти "блоки". Эта задача, имеющая множество различных приложений, применяется и в проектировании интегральных схем.

Ддя нахождения локальных оптимальных решений задач одномерного размещения блоков можно применять ряд локальных преобразований. Вот некоторые из них.

1. Произвести взаимную перестановку смежных блоков pi и p,+i, если результирующий порядок имеет меньшую стоимость. Пусть L(j)- сумма весов ребер,

расположенных слева от блока ру, т.е. Yju(p ,р,,)- Аналогично обозначим через

R(j) сумму V ii,(pp весов ребер, расположенных справа от блока pj. Улучше-

ние можно выполнить, если L(i) - R(i) + R(i + 1) - L(i + 1) + 2w(pi,Pi+i) является отрицательным числом. Читатель может убедиться в справедливости этой формулы, вычислив соответствуюшие стоимости до и после взаимной перестановки и оценив разность между этими стоимостями.

2. Взять пакет А- и вставить его между ру и py+i при некоторых значениях i и j.

3. Выполнить взаимную перестановку двух блоков р,- иpj.

Пример 10.13. Возьмем в качестве примера размещения блоков граф, показанный на рис. 10.16. Ограничимся простой совокупностью преобразований (1). Начальное размещение блоков а. Ъ, с, d, е показано на рис. 10.23,а, его стоимость равна 97. Обратите внимание, что функция стоимости определяет вес ребра в со-



ответствии с количеством промежуточных ребер между блоками в выбранном размещении блоков, соединенных этим ребром, поэтому "вклад" ребра (а, е) в общую стоимость составляет 4 х 7 = 28. Рассмотрим взаимную перестановку блоков due. Сейчас L(d) = 13, R(d) = 6, L(e) = 24 и R(e) = 0. Таким образом, L(d) - R(d) + R(e) - L(e) + 2w(d, e) = -5, поэтому следует произвести перестановку блоков due, получив улучшенное размещение а, Ь, с, е, d, стоимость которого, как следует из рис.- 10.23,6, равна 92.

На рис. 10.23,6 можно произвести выгодную взаимную перестановку блоков сие, получив таким образом размещение блоков, показанное на рис. 10.23,в; стоимость этого размещения равна 91. Размещение на рис. 10.23,в является локально-оптимальным для совокупности преобразований (1). Однако оно не является глобально-оптимальным, поскольку для размещения а, с, е, d, b стоимость равна 84. □



э13-ь llcLS 6 с


Рис. 10.23. Локальные оптимизации

Как и в задаче коммивояжера, мы не в состоянии точно оценить время, необходимое для достижения локального оптимума. Можно лишь констатировать факт, что для совокупности преобразований (1) надо рассмотреть только п - 1 преобразований. Далее, после того как мы однажды вычислили L(i) и R(i), нам придется лишь заменять их при выполнении взаимной перестановки с pii или pi+i. Более того, подобный пересчет не представляет особого труда. Если, например, выполняется взаимная перестановка блоков pi и pi+i, тогда новыми значениями ДО и R(i) будут соответственно величины L(i+1) - w(Pi,Pi+i) и R(i+1) + w(pi,pi+i). Таким образом, времени порядка 0(га) будет достаточно, чтобы проверить, является ли выполняемое преобразование улучшающим, и повторно вычислить все Щ) и R(i). Кроме того, на начальное вычисление всех значений Щ) и R(i) также понадобится лишь 0(п) времени, если мы воспользуемся рекуррентными соотношениями

Ь(1) = О ,

mL[i-i) + w{p ,,p,)

и аналогичными рекуррентными соотношениями для R.

Для сравнения: каждая из совокупностей преобразований (2) и (3) имеет О(л) членов. Таким образом, потребуется О(п) времени лишь для того, чтобы убедиться в том, что мы вышли на одно из локально-оптимальных решений. Однако, как и в случае совокупности преобразований (1), мы не в состоянии точно оценить обшее время, которое может потребоваться для выполнения ряда последовательных улучшений, поскольку каждое такое улучшение может создавать дополнительные возможности для дальнейших улучшений.



Упражнения

10.1. Сколько перемещений необходимо выполнить для перестановки п дисков в задаче о "Ханойских башнях"?

*10.2. Докажите, что рекурсивный алгоритм декомпозиции, используемый для решения задачи о "Ханойских башнях", и нерекурсивный алгоритм, описанный в начале раздела 10.1, выполняют одни и те же действия.

10.3. Используя алгоритм декомпозиции (листинг 10.1), выполните умножение чисел 1011 и 1101.

*10.4. Обобщите составление расписания теннисного турнира (см. раздел 10.1), если количество его участников не выражается степенью числа 2. Совет. Если я (количество участников турнира) нечетное, тогда каждый день один из участников должен полностью освобождаться от проведения матчей, а проведение турнира в целом займет я, а не я - 1 дней. Если, однако, сформировать две группы с нечетным количеством участников, тогда игроки, освобожденные от проведения матчей в каждой такой группе, могут провести матч друг с другом.

10.5. Существует следующее рекуррентное определение числа сочетаний из я элементов по т, обозначается как С™ , для л > 1 и О < m < га:

С™ = 1,если т = О или т = п,

С = C;j +„С; ,\если 0< т< п.

а) укажите рекурсивную функцию для вычисления чисел С™ ;

б) каким в наихудшем случае будет время вычисления этой функции в зависимости от га?

в) на основе метода динамического программирования разработайте алгоритм для вычисления чисел С™ . Совет. Этот алгоритм должен составлять таблицу, известную как треугольник Паскаля;

г) каким будет время выполнения этого алгоритма в зависимости от га?

10.6. Один из способов вычисления количества сочетаний из я элементов по т за-

ключается в вычислении выражения (л)(га - 1)(га - 2)...(га - т + 1)/(1)(2)...(/п).

а) каким в наихудшем случае будет время вычисления этого алгоритма в зависимости от п?

*б) возможно ли примерно таким же способом вычислить вероятности P(i,j) победы в турнирах (см. раздел 10.2)? Как быстро можно выполнить это вычисление?

10.7. а) перепишите программу вычисления вероятностей, показанную в лис-

тинге 10.2, если вероятность выигрыша первой командой любой игры равняется р;

б) если первая команда выиграла один матч, а вторая - два, и вероятность выигрыша 1-й командой любой игры равна 0,6, то у какой из команд больше шансов выиграть весь турнир?

10.8. Программе вычисления вероятностей (листинг 10.2) требуется объем памяти порядка 0{п ). Перепишите эту программу так, чтобы ей требовалось только 0(п) объема памяти.

*10.9. Докажите, что вычисление решения уравнения (10.4) требует ровно 2С -1

вычислений различных значений Р.

10.10. Найдите минимальную триангуляцию для правильного восьмиугольника в предположении, что расстояния вычисляются как евклидовые расстояния.





0 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

0.002