Введение 5

А б

Рис. 10.4. (а) Приведенная матрица стоимостей после вычеркивания строки 3 и столбца 5 и установления с₅₃₌∞; (б) приведение матрицы стоимостей,
изображенной в части (а).

Нижняя граница для множества {3, 5} получается несколько иным способом. Ребро (3, 5) не может находиться в этом множестве, поэтому полагаем
c₃₅ = ∞ в матрице, изображенной на рис.10.3. В любой тур из {3,5} будет входить какое-то ребро из города 3 и какое-то ребро к городу 5. Самое дешевое ребро из города 3, исключая старое значение (3,5), имеет стоимость 2, а самое дешевое ребро к городу 5 имеет стоимость 0. Следовательно, нижняя граница любого тура в множестве {3,5} равна 47+2+0=49 (рис.10.2).

На данной стадии нам удалось сократить размер матрицы стои­мостей, рассматриваемой в вершине {3, 5}. Кроме того, если мы смо­жем найти тур из множества {3, 5} со стоимостью, меньшей или рав­ной 62, тогда не нужно проводить дальше ветвления и вычисления границ в вершине {3, 5}. В этом случае будем говорить, что вершина {3, 5} в дереве отработана. Тогда следующей целью может быть ветвление из вершины {3, 5} в надежде найти тур со стоимостью в пределах 49≤с≤62.

В основных чертах блок-схема этого алгоритма ветвей и границ показана на рис.10.5. Здесь используются следующие обозначения. Буква X обо­значает текущую вершину на дереве поиска, a w(X) — соответствую­щую нижнюю границу. Вершины, следующие непосредственно за X, назовем Y и `Y; они выбираются ветвлением по некоторому ребру (k, l). Символ z₀ обозначает стоимость самого дешевого тура, извест­ного на данный момент. В начальный момент z₀ = ∞_.

Раскроем более детально содержание некоторых блоков этой схемы.

Блок 1. Установление начальных значений переменных, или ини­циализация, не представляет труда.

Блок 2. Первое приведение — это непосредственная реализация описанной ранее процедуры; детали оставляем в качестве упражнения.

Блок 3. Выбор следующего ребра ветвления (k, l) определяет множества Y и ` Y, непосредственно следующие за текущим X. Ребро (k, l) нужно выбирать так, чтобы попытаться получить большую по величине нижнюю границу на множестве ` Y = { k, l }, что облегчит проведение оценки для множества Y. Обычно предпочтительнее про­вести оценку для Y, так как размер этого множества и соответству­ющая ему матрица стоимостей обычно больше, чем у ` Y (из матрицы для Y вычеркнуты строка k и столбец I). Можно надеяться также, что Y с большей вероятностью содержит оптимальный тур.

Как применить эти идеи к выбору конкретного ребра ветвления (k, l)?В приведенной матрице стоимостей С ’, связанной с X, каждая строка и столбец имеют хотя бы по одному нулевому элементу (если нет, то С ’не полностью приведена). Можно предположить, что ребра, соответствующие этим нулевым стоимостям, будут с большей веро­ятностью входить в оптимальный тур, чем ребра с

большими стои­мостями. Поэтому мы выберем одно из них. Но какое? Пусть ребро (i, j) имеет с_ij = 0в С. Мы хотим, чтобы у ` Y ={ i, j } была как можно большая нижняя граница. Вспоминая метод вычисления нижней границы для {3, 5} в нашем примере, мы видим, что для Y эта граница задается в виде

w (` Y) =w (X) + (наименьшая стоимость в строке i, не включая с_ij) +
+ (наименьшая стоимость в столбце i, не включая с_ij).

Следовательно, из всех ребер (i, j) с с_ij = 0 в текущей матрице С’ мы выбираем то, которое дает наибольшее значение для w (` Y). Пусть это будет ребро (k, I).

Поэтому более подробное описание выбора, представленного бли­ком 3, имеет следующий вид:

Шаг 1. Пусть S — множество ребер (i, j), таких, что с_ij = 0 в те­кущей матрице стоимостей С.

Шаг 2. Положим D_ij - равным наименьшей стоимости в строке i, исключая с_ij, плюс наименьшая стоимость в столбце j, исключая с_ij. Вычисляем D_ij для всех (i, j) Î S.

Шаг 3. Выбираем следующее ребро ветвления (k, l) из условия

Блок 4. Определяем вершину ` Y, следующую за X, точно так же, как делали раньше.

В рассматриваемом примере X = R и ` Y ={2, 1}, т, е. это множество всех туров, не содержащих ребро (2, 1). Вычисляем нижнюю границу w (` Y) так же, как в блоке 3, т. е.

w (` Y) = w (X)+ D_k ^* _l

и

w ({2, 1}) = 47+ 15 = 62.

Блок 5. Вершине Y, следующей за X, соответствует подмножество туров из X, содержащих то ребро (k, /), которое выбрано в блоке 3. При вычислении w(Y) необ­ходима известная осторожность.

Блок 6. В конце концов, мы должны прийти к множествам, содержа­щим так мало туров, что мы можем рассмотреть каждый из них и провести оценку для этой вершины без дальнейшего ветвления. Блок 6 проверяет, не пришли ли мы уже к таким множествам. Каждое ребро, про которое мы знаем, что оно содержится во всех турах из Y, сокра­щает размер С на одну строку и один столбец. Если в исходной задаче было N городов, а текущая матрица С имеет размер 2x2, то выбрано уже N —2 ребер каждого тура Y. Поэтому множество Y содержит самое большее два тура (почему?). Вопрос о том, как их распознать, оставим в качестве упражнения. Таким образом, блок 6 проверяет, является ли С матрицей размера 2x2. Заметим, что это, по существу, дает ответ на вопрос, поставленный в конце шага 2 при обсуждении блока 5.

Блоки 7 и 8. Блок 7 работает, только если С — матрица размеров 2x2. В этом блоке отыскивается самый дешевый тур в Y и его вес обозначается через w(Y). В блоке 8 проверяется, лучше ли данный тур, чем текущий лучший из известных туров. Если нет, то новый тур отбрасывается. Если да, то текущим лучшим туром становится новый тур, и мы полагаем z ₀= w (Y).

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

Блок 10. Наше обсуждение помогает решить, что делать с этим бес­покоящим вопросительным знаком, поставленным в блоке 10. Вы, должно быть, заметили, что алгоритм, представленный блок-схемой на рис. 10.5, не имеет окончания. Блок 10 показывает, должны ли мы остановиться. Если текущая граница для нашего лучшего тура z ₀ меньше или равна w(X) — наименьшей из неисследованных нижних границ,— тогда никакая из вершин, следующих за X, не может содержать лучшего тура. Благодаря способу выбора X в блоке 9 лучший тур не может также содержаться ни в какой другой из не­оцененных конечных вершин. Теперь все дерево поиска оценено, и мы останавливаемся. Если w (Х)< z ₀, поиск должен быть продолжен.

Блок 11. В этой части алгоритма получается откорректированная матрица стоимостей С для текущей вершины X.

На рис.10.6 приведено дерево поиска для задачи рис.10.1.

Обо всех более или менее эффективных алгоритмах ветвей и гра­ниц известно или имеются предположения, что их трудоемкость в худшем случае является экспоненциальной. Анализ ожидаемой тру­доемкости очень сложен и часто выходит за рамки наших аналити­ческих возможностей. Все, что известно о большинстве алгоритмов ветвей и границ, описанных в литературе, это лишь некоторые экс­периментальные статистические данные.

Вопросы к зачету

Понятие трудоемкости алгоритма в формальном базисе.

Обобщенный критерий оценки качества алгоритма.

Система обозначений в анализе алгоритмов - худший, лучший и средний случаи.

Классификация алгоритмов по виду функции трудоемкости.

Примеры количественных и параметрически–зависимых алгоритмов.

Обозначения в асимптотическом анализе функций.

Трудоемкость рекурсивных алгоритмов.

Алгоритм последовательного поиска. Оценка худшего, лучшего и среднего случая.

Алгоритм двоичного поиска. Оценка среднего случая.

Выборка k-го по величине значения.

Рекурсивный алгоритм выборки k-го по величине значения.

Алгоритмы сортировки 3-х чисел.

Сортировка вставками. Оценка наихудшего и среднего случая.

Пузырьковая сортировка. Оценка наихудшего случая.

Сортировка Шелла.

Корневая сортировка: достоинства и недостатки.

Сортировка методом индексов.

Быстрая сортировка. Анализ наихудшего случая.

Структуры данных для представления графов.

Алгоритмы обхода графа в глубину; в ширину.

Поиск минимального остовного дерева методом Дейкстры-Прима.

Поиск минимального остовного дерева методом Крускала.

Поиск кратчайшего пути.

Вычисление значений многочленов стандартным способом.

Вычисление значений многочленов по схеме Горнера.

Стандартный алгоритм умножения матриц.

Особенности умножения матриц по Винограду.

Основная идея алгоритма Штрассена для умножения матриц.

Варианты представления точки на плоскости.

Понятие ориентированной площади.

Определение выпуклости многоугольника.

Построение выпуклой оболочки алгоритмом Грэхема.

Построение выпуклой оболочки алгоритмом Джарвиса.

Рекурсивный алгоритм построения выпуклой оболочки.

Определение классов Р, NP, NP–полных классов задач.

Примеры NP–полных задач.

Эвристические алгоритмы раскладки по ящикам.

Приближения в задаче об упаковке рюкзака.

Динамическое программирование

Метод ветвей и границ.

Литература

Т.Кормен, Ч. Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. - М.: МЦИМО, 1999.- 960с.

Дж. Макконнелл. Анализ алгоритмов. Вводный курс. - М.: Техносфера, 2002. –304с.

С.Гудман, С.Хидетниеми Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368с.

Альфред Вахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы.: Пер. с англ.: М.: Издательский дом «Вильямс», 2003. – 384с.

Окулов С.М. Программирование в алгоритмах. - М.: Бином. Лаборатория знаний, 2002. –341 с.

Беллман Р., Дрейфус Р. Прикладные задачи динамического программирования: Пер. с англ. – М.: Наука, 1965– 457 с.

1. ОСНОВЫ ТЕОРИИ ДЕТОНАЦИИ И СВОЙСТВА

ПРОМЫШЛЕННЫХ ВВ 6

1.1 Природа взрыва 6

1.2. Параметры взрыва промышленных ВВ 6

1.3. Основные сведения о промышленных ВВ 7

1.4. Формы превращения ВВ, кислородный баланс и химические

реакции при взрыве 8

1.5. Ядовитые газы взрыва 9

1.6. Теплота и температура взрыва. Объем и давление газообразных

продуктов взрыва 10

1.7. Детонация взрывчатых веществ 13

1.8. Факторы, влияющие на детонацию зарядов промышленных ВВ 14

2. ОЦЕНКА ЭФФЕКТИВНОСТИ И КАЧЕСТВА

ПРОМЫШЛЕННЫХ ВВ 16

2.1. Методы испытаний промышленных ВВ 16

2.2. Методы определения взрывчатых свойств ВВ 17

2.3. Методы проверки качества ВВ 22

2.4. Методы оценки чувствительности и опасности ВВ в обращении 23

3. ПРОМЫШЛЕННЫЕ ВЗРЫВЧАТЫЕ ВЕЩЕСТВА 24

3.1. Классификации взрывчатых веществ 24

3.2. Компоненты промышленных ВВ 25

3.3. Взрывчатые вещества для взрывных работ только на земной

поверхности 29

3.4. Взрывчатые вещества для взрывных работ на земной поверхности

и в шахтах не опасных по газу и пыли 32

3.5. Предохранительыне ВВ 37

3.6. Промышленные ВВ на основе утилизируемых боеприпасов 38

4. СРЕДСТВА И СПОСОБЫ ИНИЦИИРОВАНИЯ ЗАРЯДОВ 39

4.1. Классификация способов взрывания зарядов 39

4.2. Устройство и характеристики средств огневого способа взрывания 40

4.3. Конструкции средств электрического способа взрывания 42

4.4. Конструкции средств бескапсюльного способа взрывания 43

4.5. Неэлектрические системы взрывания 45

5. ХРАНЕНИЕ ВЗРЫВЧАТЫХ МАТЕРИАЛОВ 46

5.1. Общие положения 46

5.2. Поверхностные и полууглубленные постоянные склады ВМ 47

5.3. Поверхностные и полууглубленные временные и кратковременные

склады ВМ 48

5.4 Размещение ВМ в хранилищах 49

6. ПЕРЕВОЗКА ВЗРЫВЧАТЫХ МАТЕРИАЛОВ 50

6.1. Общие положения 50

6.2. Подготовка ВМ к перевозке, маршрут, организация движения,

технические состояние транспортных средств 51

6.3. Требования к водителям, охрана и сопровождение транспортных

средств, система информации об опасности (СИО) 53

ЛИТЕРАТУРА 60

Дата добавления: 2015-06-27