Основные понятия. Справочный материал. Алгоритмы

Теория сложностей вычислительных процессов и структур Конспект лекций Оглавление 1 ОСНОВНЫЕ ПОНЯТИЯ. СПРАВОЧНЫЙ МАТЕРИАЛ 1.1 Основные понятия Центральным понятием курса будет трудоемкость алгоритма. Рассмотрим это понятие подробнее. Пусть на входе некоторого алгоритма имеется информация объема n (например, n – длина массива, размер матрицы СЛАУ, длина перемножаемых чисел и т.п.), а на выходе ответ – результат обработки входной информации. Определение: Трудоемкость алгоритма Т(n) – максимально возможное количество действий для решения данной задачи среди всех возможных входов длины n. Замечание: Иногда под сложностью алгоритма подразумевают не максимальное количество операций, а среднюю трудоемкость. Порядок средней и максимальной трудоемкостей, как правило, одинаков. Характеристики алгоритма: Т(n) – (от англ. Time) – количество операций, необходимых для обработки информации объема n. S(n)– (от англ. Spaсe) – объём необходимой памяти для обработки информации. Алгоритмы решения задачи могут быть написаны на разных языках: машинные: – высокого уровня; – низкого уровня; – машинные коды; математические: – математические реализации (машины Тьюринга); – конечные автоматы; – рекурсивные функции; Все эти языки эквивалентны с точки зрения набора решаемых задач (любая задача, реализованная на одном языке, может быть переписана на другой), но они неэквивалентны с точки зрения трудоемкости. Трудоемкость алгоритма, реализованного на одном языке, может существенно отличаться от того же алгоритма, записанного на другом языке. 2 НОВЫЕ БЫСТРЫЕ ВЕРСИИ СТАРЫХ АЛГОРИТМОВ 2.1 Сортировка массивов Справка:Пусть дан массив , состоящий из n элементов. Для всех элементов определены отношения <, >, =. Тогда сортировка – это процесс, в ходе которого элементы массива переставляются таким образом, что выполняется одно из следующих неравенств: – массив отсортирован по возрастанию (в прямом порядке) или – массив отсортирован по убыванию (в обратном порядке). 2.1.1 Пузырьковая сортировка (BubbleSort) Пузырьковая сортировка – пример простейшего метода сортировки, обладающего квадратичной трудоёмкостью. Алгоритм: Двигаясь от конца массива к его началу, сравниваем между собой соседние элементы. Если правый элемент меньше, чем левый, то меняем их местами. Таким образом, при первом проходе массива самый маленький элемент переместится на первое место, и его можно не учитывать при сортировке оставшейся части массива. При втором проходе (его можно начинать не с первого, а со второго элемента массива), наименьший из оставшихся элементов переместится на второе место. Затем начинаем двигаться с третьего элемента, и так далее. Необходимо предусмотреть возможность выхода из алгоритма в случае, если мы прошли весь массив и не сделали ни одной перестановки. Для сортировки всего массива понадобится не более, чем (n­1) проходов. Пузырьковая сортировка сильно зависит от упорядоченности массива. Трудоемкость алгоритма (максимальная): . В случае если исходный массив отсортирован по возрастанию, трудоемкость алгоритма составляет (n­1) сравнений. 2.1.2 Метод прямого выбора (SelectSort) Метод прямого выбора – пример простейшего метода сортировки,обладающего квадратичной трудоёмкостью. Алгоритм: Просматриваем весь массив, находим минимальный элемент, ставим его на первое место. Потребуется n–1 сравнений и одна перестановка. При втором проходе просматриваем массив, начиная со второго элемента, находим минимум среди просматриваемой ( не отсортированной) части и ставим его на второе место, и т.д. Потребуется n–2 сравнений и одна перестановка. Для полного упорядочивания придется совершить n–1 проходов не отсортированной части. Трудоемкость алгоритма: . 2.1.3 Быстрая сортировка методом двоичных вставок (MergeSort) Рассмотрим случай, когда количество элементов массива равно степени двойки n=2k Алгоритм: 1. Разобьем массив на пары и упорядочим каждую. Получаем серии длины 2. 2. При втором проходе сливаем полученные на первом этапе пары в упорядоченные четверки. Получаем серии длины 4. 3. При третьем проходе получаем упорядоченные восьмерки, и т.д., пока длина серии не станет равной количеству элементов массива (на k­том проходе). Оценим трудоемкость алгоритма: Сначала оценим трудоемкость слияния двух упорядоченных массивов из k и l элементов (считаем только сравнения): k: 2 3 8 10 14 3 5 6 10 11 l: Минимальная трудоемкость – меньшее из k и l – min(k, l). Максимальная трудоемкость: k + l – 1 (единицу вычитаем потому, что сравниваем все элементы, а самый последний просто дописываем к упорядоченной группе). В MergeSort при получении упорядоченных пар потребуется действий. При получении упорядоченных четверок действий. Здесь есть количество четверок в массиве, а 3 – это максимальная трудоемкость получения упорядоченных четверок (считая только сравнения) . Таким образом суммарная трудоемкость сортировки составит: Таким образом, трудоемкость MergeSort составляет . Теорема: Сортировка на порядок быстрее, чем невозможна. Доказательство: Заметим, что сортировка с помощью некоторого алгоритма эквивалентна блужданию по двоичному дереву, где в узлах этого дерева находятся операторы сравнения. После операции сравнения маршрут двоится. Напомним, что двоичное дерево – граф, у которого ветвление в каждой вершине не больше, чем на две ветви. Тогда развилками дерева будут сравнения двух элементов массива; а листьями – все возможные варианты перестановки элементов массива (у массива длины n их будет n!). В этом случае трудоемкость алгоритма – высота дерева, другими словами, максимальный путь от вершины до листа дерева. Дерево с k листьями имеет высоту не меньше, чем log2k (т.к. дерево высоты h имеет не более, чем 2n листьев). Итак, трудоемкость произвольной сортировки будет не меньше, чем log2(n!). Т(n)≥ log2(n!) Воспользовавшись формулой Стирлинга, имеем: Т(n)≥ log2(n!) ≥ поэтому их во внимание не принимаем данные величины пренебрежимо малы по сравнению с Теорема доказана. 2.4 Быстрое умножение 2.4.1 Быстрое умножение чисел При обычном умножении столбиком нам потребуется n2 операций, где n – количество разрядов чисел. Попробуем произвести умножение чисел быстрее. Для этого поступим следующим образом: Пусть и – два n­разрядных числа (n=2k). Разобьем их двоичную запись пополам, т.е. на два отрезка длины k: , где Рассмотрим умножение по обычным формулам: (2.7) При перемножении по (2.7) получаем рекуррентную формулу, для вычисления трудоёмкости: . Таким образом, в (2.7) четыре произведения и одно сложение. Попробуем обойтись меньшим количеством произведений для умножения двух чисел по формуле (2.7). Рассмотрим модификацию формулы (2.7) – формулу (2.8). Тогда (2.8) При перемножении чисел по (2.8) нам потребуется 3 умножения и 4 действия сложения и вычитания. Итого получаем трудоемкость: Т(n)= 3 T(n/2)+4n (2.9) Временно забудем, что числа (a+b) и (c+d) могут быть не k­разрядные, а k+1­разрядные. Организуем процесс умножения двух n­разрядных чисел по формуле (2.8) следующим образом: на входе имеем два длинных числа. Каждое из них разобьем пополам, и получается, что нам нужно 3 раза перемножить числа вдвое меньшей разрядности. Каждое из этих чисел снова делим пополам и перемножаем по формуле (2.8). Подобная процедура дробления осуществляется до тех пор, пока в результате очередного разделения не получатся одноразрядные числа, которые перемножаем по обычной таблице умножения. Оценим трудоемкость подобных вычислений по формуле (2.8). Она оценивается по рекуррентной формуле(2.9). Теорема 2.2: Если трудоемкость некоторого алгоритма задается формулой где: k – целое число, k>1 β < log kα, β >0 α – ξбычно целое ( хотя это необязательно), то существует следующая оценка трудоемкости данного алгоритма: Без доказательства. Комментарии: Что делать, если происходит переполнение разрядов при вычислении по формуле (2.8)? Предположим, что при сложении (при вычислении u) у нас получились не k, а (k+1)­ разрядные числа, т.е. а и b имеют k+1 разряд. Выделим старший разряд: а1, b1 = 0 или 1,но один из них обязательно равен 1. Тогда произведение можно осуществить следующим образом: (2.10) В случае, когда возникает переполнение, перемножение k+1 разрядных чисел выполняется по формуле 2.10. В ней по­ прежнему одно умножение (а2b2) и одно сложение, которое может и не понадобиться. На трудоемкости (рекуррентная формула 2.9) это существенно не отражается: Т(n)= 3 T(n/2)+4n (2.9′) или Т(n)= 3 T(n/2)+5n Согласно Теореме 2.2, на трудоемкости перемножения по формуле 2.8 (формула быстрого умножения) это не сказывается. Получаем: T(n) ≈ nlog 3 ≈ n1,58 << n2 3 ЗАДАЧИ НА ГРАФАХ 3.1 Справочный материал Кратко напомним определения, известные из курса дискретной математики. Определеия: Граф – пара E={ (V1i,V2i)}. , где V={ V1, V2,…, Vn } – множество вершин графа G, E – множество дуг (рёбер) графа: Рёбра можно задавать разными способами, например матрицей инцидентности или списком рёбер. Неориентированный граф – граф, удовлетворяющий условию, что если , то и , т.е. порядок расположения концов дуг графа не существенен. Матрица инцидентности такого графа симметрична. Взвешенный граф – граф, каждой дуге которого приписан её вес. Цикл в графе – маршрут, заданный последовательностью вершин, каждая вершина посещается по одному разу, и начальная вершина совпадает с конечной. Граф без циклов – куст. Связный граф – граф, из любой вершины которого можно дойти до любой другой. Связный куст – дерево. Компонента связности – совокупность вершин, для каждой из которых существует путь в любую другую вершину этой совокупности. 3.2 Поиск минимального остова в связном неориентированном взвешенном графе Задача: Дан граф G=(V,E) – связный, неориентированный, взвешенный. Нам нужно выделить в нем минимальный (по суммарному весу ребер) связный граф с теми же вершинами – остов ( остовное дерево), т.е. исключить из графа часть ребер таким образом, чтобы сумма весов оставшихся была минимальна, и получившийся граф по­ прежнему был связным. Идея решения: Для решения этой задачи обычно применяется алгоритм Краскала (классический пример т.н. “жадного алгоритма”). Алгоритм Краскала: 1. Сначала упорядочиваем все ребра по возрастанию весов. 2. Заводим таблицу: в левой колонке список ребер, в правой компоненты связности. 3. В первой строчке список ребер пустой и все компоненты связности одновершинные. Берем минимальное по стоимости (по весу) ребро и включаем его в список ребер. Соответствующие две вершины объединяем в одну компоненту связности. 4. Берем следующее по стоимости ( весу) ребро, добавляем к содержимому предыдущей строчки левого столбца; объединяем компоненты связности. Если концы ребра уже принадлежат одной и той же компоненте связности, то данное ребро в состав минимального остова не включается. 5. Повторяем эти операции до тех пор, пока все вершины не окажутся в одной единственной компоненте связности (для этого потребуется включить в состав остова ровно n–1 ребро). Пример: Пусть имеется граф, изображённый на рисунке 3.1. Рисунок 3.1 Исходный граф Решение: Составим таблицу, в которой будем отражать порядок выбора ребер для минимального остова. Подграф (ребра) пустой Связи (компоненты связности) 1,2,3,4,5,6,7 (1,7) – минимально по цене. (1,7),2,3,4,5,6 (1,7)+(3,4) (1,7),2,(3,4),5,6 (1,7)(3,4)+(2,7)< (1,2,7),(3,4),5,6 (1,7)(3,4)(2,7)+(2,3) (1,2,3,4,7),5,6 (1,7)(3,4)(2,7)(2,3) +(3,7) ◊ (1,2,3,4,7),5,6> (1,7)(3,4)(2,7)(2,3) +(4,7) ◊◊ (1,2,3,4,7),5,6 (1,7)(3,4)(2,7)(2,3)+(4,5) (1,2,3,4,5,7),6 (1,7)(3,4)(2,7)(2,3)(4,5) +(1,2) ◊◊◊ (1,2,3,4,5,7),6 (1,7)(3,4)(2,7)(2,3)(4,5)+(1,6)> (1,2,3,4,5,6,7) Пояснения: ◊ – вершины 3 и 7 уже находятся в одной компоненте связности на момент включения в остов ребра (3,7); ◊◊ – следующее по весу ребро – (4, 7), однако вершины 4 и 7 уже находятся в одной компоненте связности на момент включения в остов ребра (4,7); ◊◊◊ – аналогично. Теорема 3.1: Алгоритм Краскала всегда выдает минимальный по стоимости остов. Доказательство: Заметим, что в результате работы алгоритма Краскала мы всегда получаем дерево (так как мы не включаем ребра, вершины которых лежат в одной компоненте связности, следовательно, возникновение циклов невозможно). Предположим, что получившееся в результате работы алгоритма Краскала дерево не минимально по своей стоимости и существует другое, предположительно “оптимальное” дерево. Например, такое, как на рисунке 3.2. Цифрами в кружочках обозначены ребра в порядке их добавления в дерево. Рисунок 3.2 Рассмотрим подробно тот этап работы алгоритма Краскала, на котором мы впервые добавили в остов “неправильное” ребро, т.е. то, которого нет в “оптимальном” дереве. Первые два по порядку добавления ребра (3,6) и (6,5) присутствуют в “оптимальном” дереве. Расхождение начинается после добавления ребра (7,8). Добавим ребро (7,8) к “оптимальному” дереву (см. рис 3.3): Рисунок 3.3 При этом в “оптимальном” дереве возникает цикл, и мы можем убрать из него любое ребро, например, (1,2), участвующее в цикле, и при этом граф останется связанным. Заметим, что при этом общий вес полученного дерева будет меньше веса “оптимального” дерева, т.к. ребро (7,8) самое меньшее по весу в этом цикле (т.к. в алгоритме Краскала мы по очереди добавляем все ребра, начиная с самого минимального по весу, меньше ребра (7,8) по весу только ребра (3,6) и (6,5), а они в этот цикл не входят). В этом примере мы можем построить меньший, чем предполагаемый “оптимальный”, по суммарному весу остов: Рисунок 3.4 Минимальный остов Он отличается от “оптимального” заменой ребра (1,2) на меньшее по весу ребро (7,8). Данные рассуждения можно обобщить для случая произвольного графа. Теорема доказана. Оценим трудоемкость работы алгоритма Краскала: Пусть в графе было n вершин и k ребер . При быстрой сортировке на первый этап работы алгоритма затрачиваем k log k действий. Далее нам потребуется ровно (n–1) результативных этапов (результативным будем считать этап работы алгоритма, в результате которого осуществляется добавление ребра к минимальному остову и слияние компонент связности), и не больше, чем k–(n–1) нерезультативных этапов. Нерезультативный этап состоит из одного сравнения – проверки принадлежности вершин добавляемого ребра на нахождение в одной компоненте связности. В случае же результативного этапа мы должны переприсвоить номера компонент связности всем n вершинам – итого n действий. Таким образом, трудоемкость алгоритма Краскала: Следовательно, алгоритм Краскала – полиномиальный. 3.3 Нахождение кратчайшего расстояния Дан связный неориентированный взвешенный граф G. Если существует ребро с вершинами vi и vj , то стоимость перехода из vi в vj составит . Если же ребра vi– vj нет, то полагаем . На входе в данном графе выделяется вершина v0. Надо найти кратчайшее расстояние от v0 до всех остальных вершин. Для решения задачи поиска кратчайшего расстояния используется (кроме прямого перебора) два алгоритма: Форда – Беллмана и Дейкстры. Рассмотрим простейший алгоритм поиска кратчайшего расстояния – алгоритм Форда­Беллмана. Этот алгоритм является классическим примером алгоритма на поиск транзитивного замыкания. Общая идея работы всех алгоритмов на поиск транзитивного замыкания: Пересчитываем что­либо (в нашем случае, стоимости вершин) до тех пор, пока это что­то не стабилизируется. Как только произойдёт стабилизация, необходимо остановиться. Ответ получен. 3.3.1 Алгоритм Форда – Беллмана Формируем массив – минимально возможная стоимость переезда (перехода, перевозки) из вершины v0 в vi на каждом этапе работы нашего алгоритма. Первоначально он задается как . Затем пересчитываем стоимости всех вершин по формуле (3.1) до тех пор, пока система не стабилизуется (так называемое транзитивное замыкание). В результате мы получим стоимости переезда из каждой вершины графа до заданной v0 и эти стоимости будут минимально возможными. Пример: Дан граф (рис. 3.5). Найти расстояние от нулевой вершины до всех остальных. Рисунок 3.5 Исходный граф Решение: Рисунок 3.6 Стоимости переездов из вершины v0 Первоначальный массив стоимостей переходов выглядит так: D(0)=(0, ). Сосчитаем стоимость вершины i на k­том шаге. В вершину i мы могли попасть из нулевой вершины, из первой вершины и т.д. Тогда: D(k+1)(i)= (D(k)(0) + (0,i),D(k)(1) +(1,i),…………. ) стоимость перехода из стоимость вершины 0 на предыдущем шаге + вершины 0 в вершину i. стоимость переезда из нулевой вершины в i­ую. Стоимость вершины i на каждом шаге считаем по формуле (3.1): . Вычислим стоимости вершин данного графа на первом шаге: ; ; ; . Вычислим стоимости вершин данного графа на втором шаге: ; ; ; – наблюдается стабилизация. Вычислим стоимости вершин данного графа на третьем шаге: ; ; – стабилизация; – стабилизация. Вычислим стоимости вершин данного графа на четвёртом шаге: ; – стабилизация; – стабилизация; – стабилизация. Вычислим стоимости вершин данного графа на пятом шаге: – стабилизация; – стабилизация; – стабилизация; – стабилизация. Массив стоимостей вершин перестал изменяться. Таким образом, мы получили кратчайшие расстояния от всех вершин данного графа до нулевой вершины. Оценим трудоемкость алгоритма Форда­Беллмана: В нем участвуют три цикла: внешний типа While выполняется до тех пор, пока не произошла стабилизация. Следующий по вложенности цикл – по вершинам графа. Самый внутренний цикл (нахождение минимума) – по переменной j. Итого, T(n) = l∙n∙n, где l – количество проходов внешнего цикла While. Так как l ≤ n (потому что самый длинный оптимальный маршрут включает в себя прохождение n–1 вершин, плюс делаем еще один проход, чтобы убедиться в стабилизации) , то 2n2 ≤ T(n) ≤ n3 3.3.2 Алгоритм Дейкстры Описание алгоритма Дейкстры: Ищем расстояние от нулевой вершины. S = {o} D[i] = C(0,i) i = 0……n While S ≠ V do 1. выбираем вершину w, которая принадлежит множеству вершин V\S (V без S) с минимальной стоимостью D(w) 2. S:=S+ w (добавляем вершину w к множеству S ) 3. для всех вершин v V\S do D(v):=min( D(v), D(w)+С(w, v) ) пересчитываем стоимости всех остальных вершин Пример: Рассмотрим работу алгоритма на уже знакомом графе: Рисунок 3.7 Исходный граф Решение: Составим таблицу: S w D(w) Не определены D(1) D(2) D(3) D(4) 25 15 7 2 (0,4) 4 2 25 ◊ 15 5 ─ ◊◊ (0,4,3) 3 5 25 9 ◊◊◊ ─ ─ (0,4,3,2) 2 9 15 ─ ─ ─ (0,4,3,2,1) 1 15 ─ ─ ─ ─ Пояснения: ◊ – 25 = min(25, 2+ ), где C(4,1)= соединены ребром; – стоимость перехода напрямую от 4 вершины к первой, так как эти вершины не ◊◊ – стоимость маршрута от нулевой до четвертой вершины не пересчитывается, так как четвертая вершина уже вошла во множество S. Прочерки в остальных ячейках таблицы также означают отсутствие пересчета маршрутов для соответствующих вершин; ◊◊◊ – 9 = min(11, 5+4), где 4 – вес пути из 3 вершины во вторую. Комментарии: В алгоритме Дейкстры на каждом шаге S – растущее множество вершин, для которых уже найдены их подлинные стоимости; w – добавляемая к множеству S вершина; D[j] – минимально возможная стоимость маршрута следующего вида: Рисунок 3.8 Замечание: Алгоритм Дейкстры работает корректно, так как на каждом шаге стоимость каждой вершины пересчитывается по формуле (3.1), что соответствует выбору из двух маршрутов – старого ( ) и нового ( ). Оценим трудоемкость данного алгоритма: В процессе реализации алгоритма Дейкстры n раз выполняется цикл While. Внутри цикла While имеется цикл For, в котором нам приходится пересчитывать n–1, n–2, n–3,…,1 значений. Каждое из них – минимум из двух чисел, одно из которых – сумма двух слагаемых. Следовательно, получаем квадратичную трудоёмкость: . То есть алгоритм Дейкстры в целом работает на порядок быстрее, чем алгоритм Форда­Беллмана. Замечание: Алгоритм Дейкстры может работать только с графами, для которых стоимости переезда Форда­Беллмана справляется с графами и с отрицательными стоимостями переезда, но работает дольше. . Алгоритм 3.4 Нахождение диаметра, радиуса и центра графа Определения: Диаметром графа (взвешенного) называется максимально возможное расстояние между вершинами. – максимальная стоимость маршрута . Радиусом графа называется минимально возможный радиус круга (центр круга выбирается среди всех вершин), внутри которого помещается весь граф. , где Центр графа – та вершина , для которой достигается минимально возможный радиус круга: При применении алгоритма Дейкстры и диаметр, и радиус графа можно найти за трудоёмкость однократного применения алгоритма Дейкстры. : . операций, где n2 Алгоритм Дейкстры мы запускаем n раз: сначала от v0, потом от v1 и т.д. перебирая все возможные вершины квадратную матрицу . – минимально возможный радиус круга (в который входит весь граф) с центром в вершине , по которой мы за n2 . Получаем операций находим диаметр и радиус графа. 3.5 Задача об изоморфизме графов Определение: Два взвешенных графа G1 и G2 называются изоморфными, если существует взаимнооднозначное отображение вершин, сохраняющих расстояние, т.е. после перенумерации вершин графа G1 получаем ровно граф G2. Оценим трудоемкость этой задачи методом прямого перебора: На входе имеем два графа из n вершин. Существует всего n! различных перестановок ( перенумераций ) для n­элементного массива и при каждой перенумерации необходимо проверить n2 – попарных расстояний. Таким образом, трудоемкость этих операций составит . Нетрудно заметить, что этот алгоритм не полиномиальный и его трудоемкость велика. На данный момент не известны алгоритмы решения данной задачи для графов произвольного вида за полиномиальное время, но и не доказано, что такого алгоритма не существует. В тоже время для графов некоторых специальных видов (для деревьев) данные алгоритмы существуют. 3.6 Задача коммивояжера. Ее решение методом ветвей и границ Задача: Имеется взвешенный неориентированный связный граф. Необходимо найти гамильтонов цикл наименьшей длины, т.е. нужно обойти все вершины графа, побывав в каждой из них по одному разу, затратив как можно меньше денег. Оценим трудоемкость методом прямого перебора. Имеем n! всевозможных маршрутов. Стоимость каждого маршрута – сумма n ребер. Следовательно, n! можно заменить (n–1)!, т.к. маршрут проходит через все вершины, и поэтому в качестве стартовой мы можем взять вершину v1, располагая оставшиеся вершины (n–1) произвольным образом. – неполиномиальная. Для более быстрого решения нашей задачи существует метод ветвей и границ. На самом деле это целая группа методов, они используются для решения множества задач. Их объединяет общая идея, но в каждом случае реализация метода ветвей и границ своя. Впервые этот метод был придуман для решения задачи коммивояжера. Идея метода ветвей и границ: Пусть нам необходимо найти минимум некоторой функции у нас есть: . Предположим, что а) Алгоритм дробления множества D на всё уменьшающиеся части (вплоть до одноэлементных множеств). б) Для каждой части , полученной в результате дробления, имеется некоторая оценка величина оценивает значение функции f на интервале совпадает со значениями функции f. . Эта снизу, причем на одноэлементных множествах эта оценка Тогда для нахождения минимума поступаем следующим образом: Возьмем точку x из множества D (желательно, чтобы f(x) была как можно меньше). Объявим f(x) рекордом r . Делим множество D на части: D D(1)1 D(1)2 D(1)3 D(1)4 H(D(1)1)r H(D(1)3)=r H(D(1)4) r, тогда для всех y D(1)2 выполняется f(y) ≥ H(D(1)2) > r, следовательно, на этом множестве мы минимума не достигнем, поэтому данное множество отбрасываем. Таким образом, ветвь мы отрубаем тогда и только тогда, когда функция­оценка минимума на этом множестве больше либо равна рекорда. Далее работаем с множествами D(1)1 и D(1)4 , и, не смотря на то, что множество D(1)1 кажется более перспективным, может случиться так, что реальное значение минимума будет достигнуто на D(1)4 (так как мы не требовали, чтобы выполнялось H(D(i)k ) = min f(x) , а H(D(i)k является лишь некоторой оценкой этого минимума снизу). H(D(i)k) ≤ min f(x) , x D(i)k Множество D(1)3 мы можем в процессе работы не рассматривать, если нам достаточно найти хотя бы одну точку, в которой достигается минимум, если же нам необходимо найти все точки, то множество D(1)3 считаем перспективным. Замечание: Подобное дробление множества D продолжаем до тех пор, пока не доберемся до одноэлементных множеств (нижнего этажа дерева). Рисунок 3.9 Дробление множества, где перспективное множество неперспективное множество При этом возможны два варианта дробления: Схема одновременного ветвления: На каждом шаге мы работаем со всеми перспективными множествами: нижний этаж – одноэлементные множества Рисунок 3.10 Одновременное дробление Схема одностороннего ветвления: Отличие этой схемы от предыдущей заключается в том, что на каждом шаге мы работаем только с одним перспективным множеством, а не со всеми сразу, как в схеме одновременного ветвления (см. рис.3.11). Здесь: перспективное множество неперспективное множество отложенное перспективное множество ветвь, ставшая неперспективной после обновления рекорда Рисунок 3.11 Одностороннее дробление По ходу дробления на каждом шаге из всех множеств выбирается самое перспективное – то, на котором меньше всего оценка f. С ним и будем работать дальше. Рассмотрение остальных перспективных множеств пока отложим. Эта схема предпочтительнее, т.к. при ее применении мы быстрее доберемся до нижнего этажа, где сможем обновить рекорд, а после его обновления многие множества, ранее перспективные, при новом рекорде могут перейти в разряд неперспективных, и их мы рассматривать вообще не будем. Таким образом, трудоемкость схемы одностороннего ветвления существенно меньше схемы одновременного ветвления. Алгоритм одностороннего ветвления: На каждом шаге оставляем в работе только одно, самое перспективное множество. Таким образом доходим до нижнего этажа дерева, при этом все находящиеся на нем множества станут одноэлементными. Обновляем рекорд. Выкидываем уже неперспективные отложенные ветви. Среди оставшихся перспективных ветвей выбираем самую перспективную (либо по оценке f, либо по уровню, на котором она расположена в дереве – чем ближе к нижнему этажу, тем перспективнее отложенная ветвь). Подобную процедуру подъема и спуска продолжаем до тех пор, пока не останется ни одной перспективной ветви. Применение метода ветвей и границ для решения задачи коммивояжера. В нашем случае исходное множество D – множество всевозможных маршрутов, проходящих по всем вершинам графа (так называемых гамильтоновых циклов), для определенности стартующих из точки 0. Напомним, что гамильтонов цикл должен содержать все вершины графа, причем, переходя по его ребрам, можно обойти все вершины, побывав в каждой только по одному разу. В предложенной схеме дробления будут возникать подмножества D следующего вида: Множество состоит из всевозможных маршрутов, у которых переход из вершины – первоначальный участок, а следующий мы можем совершить в любую вершину, кроме указанных в фигурных скобках вершин Также мы не можем идти в вершины Составим оценку f для множества , так как тогда маршрут будет уже не гамильтонов. следующего вида: где – стоимость выхода (выезда) из вершины (т.е. минимально возможная цена, за которую мы можем выехать в . какую­либо другую допустимую вершину), – минимально возможная стоимость въезда в вершину после уже уплаченных стоимостей выездов. Пример: Пусть у нас имеется гамильтонов цикл в ориентированном графе (для орграфа матрица стоимости ребер не симметрична относительно своей главной диагонали). По главной диагонали расположены бесконечности, а не нули, потому что в гамильтоновом цикле петли запрещены. Имеем первоначальный маршрут: D = [ (2,5,0),{1} ]. Таким образом, из вершины 0 мы можем идти в любую, кроме 1(так как она запрещенная), 2 и 5 (так как их уже прошли). Вычисляем оценку Н. Для этого: 1. Вычеркиваем из имеющейся матрицы 2 и 5 строки, так как стоимости ребер, по которым можно попасть во 2 и 5 вершины, нам не понадобятся, в эти вершины мы уже въезжали и больше туда не собираемся. 2. Вычеркиваем 5 и 0 столбцы, так как уже въезжали в вершины 5 и 0. 3. Получилась матрица: Стоимость переезда из 0 в 1 полагаем равной бесконечности, так как он запрещен. В каждой строке находим минимальный элемент (минимальную стоимость выезда из вершин 0,1,3 и 4), т.е. находим α: “Уплачиваем” найденные стоимости выездов, т.е. вычитаем из каждого элемента строки минимальный элемент данной строки. Стоимости выездов “уплачены”, однако мы еще должны заехать в вершины 1, 2, 3, 4. находим для них оценку . Итак, оценка из первоначальной матрицы = 3+3+( 6+3+4+2 )+( 0+0+1+0 ) = 22. То есть, проехав по любому маршруту из множества , мы не можем потратить менее 22 долларов. Осталось записать схему возможных вариантов дробления маршрутов D. Рассмотрим два варианта этой схемы на примере пятиэлементного множества: Первый вариант: Рисунок 3.12 Тут не возникает запретных вершин. Второй вариант: При этой схеме дробления на каждом этапе ветка делится на две новые ветви, но также возникают и запретные вершины. Рисунок 3.13 и т.д. Замечание: Обычно метод ветвей и границ позволяет существенно уменьшить объем перебора. Однако это справедливо не для каждой задачи, например для задачи коммивояжера до сих пор неизвестен алгоритм, который гарантированно бы решал ее за полиномиальное время. Впрочем, для большинства графов он дает существенный выигрыш по сравнению с прямым перебором. Домашнее задание №1 (А, Б, В): А) Найти остов минимального веса для связного взвешенного неориентированного графа, заданного матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет). Б) Найти кратчайшие расстояния от второй до всех остальных вершин графа (нумерация вершин начинается с 0), для связного взвешенного графа, заданного матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет) Б1) с помощью алгоритма Форд­Беллмана; Б2) с помощью алгоритма Дейкстры. Матрица стоимостей: В) Определить нижнюю оценку стоимости любого маршрута из множества D =[(4,0,3),{1,5}] для задачи коммивояжера. Матрица стоимостей переездов: 4 ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 4.1 Задача динамического программирования. Её решение методом динамического программирования Определение: Задача динамического программирования (ДП) – это задача оптимального управления некоторым многошаговым процессом. Подобных задач, равно как и методов их решения, существует великое множество. Изобретаются они в каждом конкретном случае индивидуально, но все объединены общей идеей решения – так называемого метода решения задачи про чайник: чтобы вскипятить воду, нужно налить её в чайник, поставить его на плиту, включить плиту и т.д. Если же вода в чайник уже налита, то нужно её вылить. А что делать дальше, мы уже знаем. Таким образом, в процессе решения мы сводим задачу к той, решать которую уже научились на предыдущем шаге. Рассуждения при этом проводятся примерно следующие: Нам необходимо найти оптимальное значение в конце маршрута. Если бы мы знали оптимальное решение для всех предыдущих этапов, то нашли бы решение для последнего. Чтобы найти решение для предпоследнего этапа, мы должны знать решение для второго с конца этапа, и т.д. То есть разрабатывается метод динамического программирования с конца. Реализуется же он сначала: высчитываем оптимальные значения с самого начала и находим оптимальную стоимость. После этого необходимо найти собственно оптимальный маршрут. Его находим с конца. Задача: Рассмотрим задачу оптимального управления многошаговым процессом. Над ребрами данного графа проставлены стоимости переходов из одной вершины в другую. Необходимо найти путь, по которому с минимальными затратами можно попасть из S(0) в S(5) (см. рисунок 4.1). Рисунок 4.1 Исходный граф Идея решения: В принципе мы умеем решать подобные задачи по алгоритму Дейкстры и Форда­Беллмана. Попробуем теперь решить эту задачу методом динамического программирования. Он изобретается с конца. Нам необходимо найти минимально возможную сумму, имея которую, мы можем добраться до S(5) . Рассуждаем так: если бы мы знали “стоимости” всех вершин, из которых мы можем попасть в S(5) (то есть вершин ), то мы бы нашли стоимости всех вершин S(5) (для этого к стоимости вершин из S(4) прибавляем стоимости переездов и выбираем минимум из получившихся сумм). Чтобы найти стоимости S(4) мы должны знать стоимости S(3) и т.д. Так спускаемся до вершины S(0), стоимость которой равно нулю. Итак, здесь – минимально возможная сумма денег, имея которую мы можем добраться от до . Имеем: Рисунок 4.2 Здесь – полученные стоимости вершин. Реализация метода ДП происходит от начала к концу (то есть слева направо в нашем случае). Самый внешний цикл – по i; в нём в прямом порядке перебираем уровни вершин. Следующий по вложенности цикл – по j; в нём перебираем вершины одного уровня. Самый внутренний цикл – по k. Изменение направления прохода двух вложенных циклов не повлияет на конечный результат. Последний этап – восстановление оптимального пути – реализуется из конца в начало. Для этого смотрим, из какой вершины предыдущего уровня была достигнута стоимость нашей вершины, постепенно продвигаясь справа налево. Рисунок 4.3 Восстановление оптимального пути 4.2 Задача об оптимальном наборе самолетом скорости и высоты Задача: Необходимо, имея стартовую нулевую скорость v и стартовую нулевую высоту h, набрать некоторую скорость V и высоту H, минимизировав при этом суммарные затраты топлива. Если в какой­то момент времени t мы увеличиваем скорость на dv, а высоту на dh, то затраты горючего на это изменение могут быть определены по формуле: где v(t) и h(t) – скорость и высота в момент времени t. и – коэффициенты пропорциональности затрат топлива. Идея решения: Нам необходимо минимизировать интеграл, выбирая оптимальный вариант набора скорости и высоты (ищем оптимальное управление): Дискретизируем эту задачу. Для этого разобьем весь участок приращения скорости и высоты на несколько меньших интервалов: Рисунок 4.4 Дискретизация исходной задачи Заполняем стоимости, начиная с левого нижнего угла, и записываем их в левый сектор круга. Аналогично считаем стоимости вершин с правого верхнего угла и записываем их в правый сектор. Глядя на полученные стоимости, восстанавливаем оптимальный путь: 87 получили из 79 + 8; 79 из 70 + 9 и т.д. Комментарии: ● В принципе, при восстановлении оптимального пути, возможно ветвление маршрута (когда минимум получен на пути не из одной, а из большего количества вершин). ● Все вершины графа разбиваются на группы состояний по диагоналям. Но в группу S(i) мы попадаем не только из S(i– 1), но и из S(i–2). ● При проходе слева направо и справа налево, как и следовало ожидать, стоимость пути одинакова и равна 87. В каждом кружке сумма чисел больше либо равна 87. Причем сумма равна 87 в кружках, лежащих на оптимальном пути, а для остальных она превышает 87. В каждом кружке – левое число – стоимость маршрута из левого нижнего угла до данного кружка. Правое число – стоимость маршрута из правого верхнего угла до данного кружка. 4.3 Задача грабителя (задача о рюкзаке) Задача: Имеется склад, на котором есть некоторый ассортимент товаров. Запас каждого товара считается неограниченным. Товары имеют две характеристики: mi – масса, ci – стоимость; . Необходимо выбрать набор товаров так, чтобы его суммарная масса не превосходила заранее фиксированную массу М (т.е. ), и стоимость набора была как можно больше ( Идея решения: Считаем, что все массы mi целочисленные. программирования. Изобретаем метод, т.е. формулу: ). Решим эту задачу методом динамического Нам необходимо найти , т.е. максимально возможную сумму при заданном М. Предположим, что к этому моменту мы знаем, как решать эту задачу для всех меньших значений грузоподъемности. Тогда смотрим, какой товар мы положили в рюкзак последним. Если это был первый товар стоимостью с1, то мы должны оптимизировать стоимость рюкзака при грузоподъемности . Если это был второй товар стоимостью с2 , то оптимизация при грузоподъемности , и т.д. Среди всех этих величин выбираем максимальную. Таким образом, получаем формулу: Пример: Рассмотрим решение этой задачи при следующем наборе товаров: m: 3 5 8 – массы товаров, c: 8 14 23 – стоимости товаров. Решение: Вычислим последовательно: f(0)=0; f(1)=0; f(2)=0; f(3)=8; f(4)=8; f(5)= 14 = max( f(5–3)+8; f(5–5)+14; f(5–8)+23);–не рассматриваем при поиске максимума, так как f(–3) не определена. f(6)=16; f(7)=16; f(8)= 23; f(9)= 24 =max( f(9–3)+8; f(9–5)+14; f(9–8)+23 ); f(10)=28; f(11)=31; f(12)=32; f(13)= 37 =max( f(13–3)+8; f(13–5)+14; f(13–8)+23 ) Оценим трудоемкость решения задачи о рюкзаке методом ДП: Для применения метода ДП все массы должны быть целочисленные ( а стоимости – необязательно). Тогда, если k – количество видов товаров, m – грузоподъемность, то имеем m шагов внешнего цикла (по грузоподъемности) и на каждом шаге находим максимум среди k чисел, каждое из которых является суммой двух слагаемых. В итоге получаем трудоемкость: T = m·k. 4.4 Задача о перемножении матриц Как известно из высшей математики, умножение матриц ассоциативно, то есть результат перемножения зависит только от порядка матриц и не зависит от расстановки скобок: (A*B)*C = A*(B*C). Результат перемножения от расстановки скобок не зависит, зато трудоемкость этого перемножения при разных расстановках скобок может отличаться существенно. Оценим трудоемкость умножения двух матриц A(p×q) и B(q×>r): C(p×r)=A(p×q)*B(q×r), каждый элемент матрицы С(p×r) есть сумма q попарных произведений. Трудоемкость перемножения двух матриц: Т = p∙q∙r. Пример: Рассмотрим пример перемножения матриц разными способами: Пусть имеется четыре матрицы разных размерностей: M1[10×20] , M2[20×50] M3[50×1], M4[1×100]. Решение: Рассмотрим умножение матриц в следующем порядке: М1 ∙ (М2 ∙ (М3 ∙ М4) ) [50×1] ∙ [1×100]=[50>×100] трудоёмкость 50∙1∙100 = 5000 [20>×>50] ∙ [50×100]=[20×100] трудоёмкость 20∙100∙50 = 100 000 125 000 [10×20] ∙ [20>×100]=[10×100] òрудоёмкость 10∙20∙100 = 20 000 операций Рассмотрим другой вариант умножения матриц (М1 ∙ (М2 ∙ М3) ) ∙ М4 [20×50] ∙ [50>×1]=[20>×>1] трудоёмкость. 20∙50∙1=1000 [10×20] ∙ [20×1]=[10×1] трудоёмкость 10∙20∙1=200 2200 операций [10×1] ∙ [1×100]=[10×100] трудоёмкость 10∙1∙100=1000 При умножении вторым способом действий потребовалось значительно меньше (2200 против 125 000). Придумаем формулу метода ДП применительно к данной задаче: Допустим, нам необходимо оптимальным образом перемножить 5 матриц, i­тая матрица имеет размерность [ri–1×ri]. Смотрим, где стояла последняя пара скобок : существует 4 варианта: (М1)× (М2∙М3∙М4∙М5) (1) [r0×r1] [r1>×>r5] (М1∙М2)× (М3∙М4∙М5) (2) [r0×>r2] [r2×r5] (М1∙М2∙М3)× (М4∙М5) (3) [r0×>r3] [r3×r5] (М1∙М2∙М3∙М4)× (М5) (4) [r0×r4] [r4×r5] При первом варианте расстановки скобок нам потребуется f(1,1) + f(2,5) + r0r1r5 операций. Здесь f(k,l) – минимальное количество действий, за которое можно вычислить произведение матриц с k­той по l­тую. Для последующих трех вариантов: операций соответственно. Здесь f(k,p) – минимальное количество действий, за которое можно вычислить произведение матриц с k­той по p­тую. Выбираем минимум среди всех этих чисел и получаем общую формулу: Замечание: В отличие от задачи о рюкзаке, где была динамика по одному параметру (грузоподъемности), здесь динамика по двум параметрам: начало и конец блока перемножаемых матриц. Итак, в окончательном виде эта задача решается с помощью следующего алгоритма: 1) Заполняем трудоемкости матриц: Трудоемкости на главной диагонали равны 0: for i:=1 to n do f(i,i):=0; 2) Внешний цикл по t – длине перемножаемого блока; Средний цикл по k – местоположению блока; Внутренний – поиск минимума по j. for t:=1 to n–1 do for k:=1 to n–t do . Для матриц М1, М2, М3, М4 из рассмотренного выше примера расставим скобки оптимальным образом. f(1,1) f(1,2) f(1,3) f(1,4) f(2,2) f(2,3) f(2,4) f(3,3) f(3,4) f(4,4) Итак, заполняем такую матрицу в следующем порядке: После вычисления оптимальных трудоемкостей восстанавливаем оптимальную расстановку скобок; Смотрим, где достигнут минимум в будут (М1 М2 М3) (М4). Далее смотрим, где достигнут минимум в (М1 (М2 М3)) М4. . Он достигнут в . Он достигнут в . Следовательно, последними скобками . Т.е. следующими скобками будут Т.к. у нас 3 вложенных цикла, длина каждого порядка n (n – количество перемножаемых матриц), то трудоемкость решаемой задачи методом ДП При решении этой задачи методом прямого перебора получаем не полиномиальную трудоемкость, а намного большую. То же самое получаем и для задачи о рюкзаке: её решение методом динамического программирования имеет полиномиальную трудоемкость (2 вложенных цикла), а методом прямого перебора получаем неполиномиальную трудоемкость. Домашнее задание №2 (А, Б) А) Задача грабителя (о рюкзаке). Имеется склад, на котором присутствует ассортимент товаров (каждого товара неограниченный запас). У каждого товара своя стоимость Ci и масса mi . Выбрать набор товаров так, чтобы его суммарный вес не превышал заданную грузоподъемность М, и суммарная стоимость этого набора товаров была бы максимальной. Номер товара, i mi Ci 1 5 9 2 7 13 3 11 21 Максимальная грузоподъемность: М=23; 24. Решение: Вычислим f(М) – максимально возможную стоимость товаров при грузоподъемности М: f(0)=0; f(1)=0; f(2)=0; f(3)=0; f(4)=0; f(5)=max(f(5–5)+9, f(5–7)+13, f(5–11)+21)= max(0+9)=9; f(6)=max(f(6–5)+9, f(6–7)+13, f(6–11)+21)= max(0+9)=9; f(7)=max(f(7–5)+9, f(7–7)+13, f(7–11)+21)= max(0+9, 0+13)=13; f(8)=max(f(8–5)+9, f(8–7)+13, f(8–11)+21)= max(0+9, 0+13)=13; f(9)=max(f(9–5)+9, f(9–7)+13, f(9–11)+21)= max(0+9, 0+13)=13; f(10)=max(f(10–5)+9, f(10–7)+13, f(10–11)+21)= max(9+9, 0+13)=18; f(11)=max(f(11–5)+9, f(11–7)+13, f(11–11)+21)= max(9+9, 0+13, 0+21)=21; f(12)=max(f(12–5)+9, f(12–7)+13, f(12–11)+21)= max(13+9, 9+13, 0+21)=22; f(13)=max(f(13–5)+9, f(13–7)+13, f(13–11)+21)= max(13+9, 9+13, 0+21)=22; f(14)=ma(f(14–5)+9, f(14–7)+13, f(14–11)+21)= max(13+9, 13+13, 0+21)=26; f(15)=max(f(15–5)+9, f(15–7)+13, f(15–11)+21)= max(18+9, 13+13, 0+21)=27; f(16)=max(f(16–5)+9, f(16–7)+13, f(16–11)+21)= max(21+9, 13+13, 9+21)=30; f(17)=max(f(17–5)+9, f(17–7)+13, f(17–11)+21)= max(22+9, 18+13, 9+21)=31; f(18)=max(f(18–5)+9, f(18–7)+13, f(18–11)+21)= max(22+9, 21+13, 13+21)=34; f(19)=max(f(19–5)+9, f(19–7)+13, f(19–11)+21)= max(26+9, 22+13, 13+21)=35; f(20)=max(f(20–5)+9, f(20–7)+13, f(20–11)+21)= max(27+9, 22+13, 13+21)=36; f(21)=max(f(21–5)+9, f(21–7)+13, f(21–11)+21)= max(30+9, 26+13, 18+21)=9; f(22)=max(f(22)+9, f(22)+13, f(22–11)+21)= max(31+9, 27+13, 21+21)=42; f(23)=max(f(23–5)+9, f(23–7)+13, f(23–11)+21)= max(34+9,30+13, 22+21)=43; f(24)=max(f(24–5)+9, f(24–7)+13, f(24–11)+21)= max(35+9, 31+15, 22+21)=44. Определим оптимальный набор товаров при М=23: f(23)=43; f(23–5)+9=f(18)+9=34+9=43; Рекомендуемая литература: 1. 2. 3. 4. 5. 6. Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ алгоритмов. – М. Мир, 1987, стр. 520. Томас Кормен. Алгоритмы. Построение и анализ. Второе издание. Москва–Санкт­Петербург– Киев, 2005, стр. 1296. H. S. Wilf. Algorithms and complexity. Internet Edition, 1994, стр. 136. M. Гэри, Д. Джонсон. Вычислительные машины и трудно решаемые задачи. Москва “Мир”, 1982, стр. 416. Носов Н. Н. Теория алгоритмов и анализа их сложности. http://intsys.msu.ru/stuff/vnosov/theoralg.htm Кузюрин Н. Н. Курс лекций “Сложность комбинаторных алгоритмов” http://disсopal.ispras.ru/ru.lectures.htm Экзаменационные билеты Билет №1 (Все задачи решаются “вручную”) 1. По алгоритму Краскала найти остов минимального веса для связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин 2. Оптимальным образом расставить скобки при перемножении матриц М1[7x3], M2[3x8], M3[8x3], М4[3x5], M5[5x2] Билет №2 (Все задачи решаются “вручную”) 1. С помощью алгоритма Форда­Беллмана найти кратчайшие расстояния от вершины 2 (нумерация вершин начинается с 0) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 3 8 2 8 22 3 10 28 M 24 Билет №3 (Все задачи решаются “вручную”) 1. По алгоритму Дейкстры найти кратчайшее расстояние от вершины 4 до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин (нумерация вершин начинается с 0). Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Оптимальным образом расставить скобки при перемножении матриц М1[2x5], M2[5x7], M3[7x3], М4[3x8], M5[8x4] Билет №4 (Все задачи решаются “вручную”) 1. По алгоритму Краскала найти остов минимального веса для связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 10 28 2 14 40 3 8 22 M 23 Билет №5 (Все задачи решаются “вручную”) 1. С помощью алгоритма Форда­Беллмана найти кратчайшие расстояния от вершины 3 (нумерация вершин начинается с 0) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Оптимальным образом расставить скобки при перемножении матриц М1[5x4], M2[4x2], M3[2x6], М4[6x9], M5[9x3] Билет №6 (Все задачи решаются “вручную”) 1. По алгоритму Дейкстры найти кратчайшее расстояние от вершины 3 до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин (нумерация вершин начинается с 0). Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 4 11 2 5 13 3 10 28 M 24 Билет №7 (Все задачи решаются “вручную”) 1. По алгоритму Краскала найти остов минимального веса для связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин 2. Оптимальным образом расставить скобки при перемножении матриц М1[8x3], M2[3x5], M3[5x9], М4[9x2], M5[2x4] Билет №8 (Все задачи решаются “вручную”) 1. С помощью алгоритма Форда­Беллмана найти кратчайшие расстояния от вершины 3 (нумерация вершин начинается с 0) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 5 13 2 8 22 3 14 40 M 24 Билет №9 (Все задачи решаются “вручную”) 1. По алгоритму Дейкстры найти кратчайшее расстояние от вершины 2 до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин (нумерация вершин начинается с 0). Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Оптимальным образом расставить скобки при перемножении матриц М1[6x3], M2[3x9], M3[9x2], М4[2x5], M5[5x7] Билет №10 (Все задачи решаются “вручную”) 1. По алгоритму Краскала найти остов минимального веса для связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 13 36 2 5 13 3 4 11 M 23 Билет №11 (Все задачи решаются “вручную”) 1. С помощью алгоритма Форда­Беллмана найти кратчайшие расстояния от вершины 2 (нумерация вершин начинается с 0) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Оптимальным образом расставить скобки при перемножении матриц М1[4x7], M2[7x3], M3[3x9], М4[9x6], M5[6x3] Билет №12 (Все задачи решаются “вручную”) 1. По алгоритму Дейкстры найти кратчайшее расстояние от вершины 1 до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин (нумерация вершин начинается с 0). Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 8 22 M 2 4 11 3 14 40 26 Билет №13 (Все задачи решаются “вручную”) 1. По алгоритму Краскала найти остов минимального веса для связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин 2. Оптимальным образом расставить скобки при перемножении матриц М1[4x7], M2[7x3], M3[3x9], М4[9x6], M5[6x3] Билет №14 (Все задачи решаются “вручную”) 1. С помощью алгоритма Форда­Беллмана найти кратчайшие расстояния от вершины 4 (нумерация вершин начинается с 0) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. Номер товара, i mi Ci 1 13 36 2 5 11 3 8 22 M 23 Билет №15 (Все задачи решаются “вручную”) 1. По алгоритму Дейкстры найти кратчайшее расстояние от вершины 0 до всех остальных вершин связного взвешенного неориентированного графа, имеющего 5 вершин (нумерация вершин начинается с 0). Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин. 2. Оптимальным образом расставить скобки при перемножении матриц М1[3x5], M2[5x2], M3[2x9], М4[9x3], M5[3x6] назад