Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
A C B П а а а 1 П а а а 2 Рис. 4.6. Принцип динамического программирования 122 A C B D E ... ... F Рис. 4.7. Принцип динамического программирования на общем графе иск кратчайшего пути) на подзадачи, оптимизируя каждую из которых, получим оптимальное решение задачи. В дальнейшем рассмотрим несколько задач, которые могут быть решены с помощью динамического программирования. Алгоритмы нахождения кратчайшего пути Рассмотрим граф G(V, E), где V — множество из n вершин, E — множество из e ребер. Пусть каждому ребру графа (i → j) приписана некоторая стоимость (число) f (i → j), тогда можно составить функцию стоимости c ij следующим образом: c ij = ∞, ∃(i → j), 0, i = j, f (i → j), ∃(i → j). Взвешенные графы могут быть представлены с помощью (n × n)-матрицы стоимости C = [c ij ]. Стандартной задачей для взвешенного графа является зада- ча нахождения кратчайшего пути от заданной вершины до всех остальных. Далее рассмотрим способы решения этой задачи для разных графов, применив метод динамического программирова- ния. 123 Задача 4.3 (кратчайшие пути в графе). Пусть задан взвешен- ный граф G(V, E) с матрицей стоимости C. Пусть далее некото- рая вершина v 0 ∈ V задана как начальная вершина. Требуется найти минимальную стоимость пути от вершины v 0 до остальных вершин графа. Решение (алгоритм Дейкстры). Вначале рассмотрим реше- ние для задачи о поиске кратчайших путей в графе, предположив, что все стоимости ребер неотрицательны c ij ≥ 0. Для этого случая известен способ решения, предложенный Дейкстрой и основанный на принципе динамического программирования. Сначала сформу- лируем сам алгоритм, затем проанализируем его корректность и сложность. Обозначим через σ i стоимость оптимального пути из вершины v 0 в вершину i. Далее через D i обозначим верхнюю границу для стоимости оптимального пути в вершину i, D i ≥ σ i , т.е. D i будет хранить стоимость некоторого, уже известного (и возможно, уже оптимального) пути до вершины i, и эта величина может улуч- шаться в течение работы алгоритма. В начале работы алгоритма величины D i инициализируются как D i = c v 0 i . После окончания работы алгоритма, для всех i ∈ V будет выполнено равенство D i = σ i На каждом шаге алгоритм Дейкстры рассматривает два под- множества всего множества вершин V . В первое подмножество S входят те вершины, к которым кратчайший путь из v 0 уже найден. На первом шаге это множество состоит из единственной вершины v 0 . Второе подмножество T = V \S содержит те вершины, для ко- торых их значения D i еще могут быть изменены. На каждом шаге алгоритма из вершин t ∈ T выбирается та, для которой значение D t минимально i : D i = min t∈T {D t }. (4.1) При таком выборе вершины i для нее будет обеспечиваться равенство σ i = D i , и следовательно, вершина i присоединяется к множеству S. Для всех оставшихся в множестве T вершин j 124 обновляются их оценки D j D j = min j∈T {D j , D i + c ij }. (4.2) Эта процедура повторяется до тех пор, пока все вершины гра- фа не будут включены в множество V . Корректность алгорит- ма можно доказать по индукции. На первом шаге рассматриваем все ребра, идущие из вершины v 0 , выбираем ребро с минималь- ным весом, ведущее в некоторую вершину i, и считаем, что нашли кратчайший путь в эту вершину. Так как веса ребер графа неот- рицательны, то наше предположение верно — найденный путь из одного ребра действительно кратчайший. Далее предположим, что на некотором шаге у нас уже есть несколько вершин, составляющих множество S, и для этих вер- шин найденные пути оптимальны. Рассмотрим случай, изобра- женный на рис. 4.8. Множество S включает в себя вершины v 0 , w, p, k и знаем для этих вершин оптимальные стоимости путей σ w , σ p , σ k . В соответствии с (4.1), мы выбираем вершину i ∈ S, для которой значение D i минимально среди всех вершин, не входящих в S. Пусть вершины p и k имеют ребра, ведущие в вершину i, сто- имость этих ребер, соответственно, равна c pi и c ki . Далее пусть есть еще путь из v 0 в i, в котором есть хотя бы одна вершина, не v 0 w p k i m S c ki c pi c wm x k σ p σ w σ min( , ) i p pi k ki D c c σ σ = + + m D Рис. 4.8. Выбор оптимального пути в алгоритме Дейкстры 125 принадлежащая множеству S. Выделим в этом пути ребро, кото- рое соединяет вершину из множества S с вершиной из множества T . На рис. 4.8 это ребро соединяет вершины w и m, и имеет стои- мость c wm . Стоимость пути из m в i составляет x, и в частности, этот путь может также содержать вершины из S, это не влияет на рассмотрение. В соответствии с (4.2), при включении в множество S вершин p и k была вычислена оценка стоимости D i в вершину i. Предпо- ложив, что в S нет других вершин, смежных с i, получим D i = min(σ p + c pi , σ k + c ki ). (4.3) Для определенности предположим, что σ p + c pi ≥ σ k + c ki , тогда D i = σ k + c ki (4.4) Докажем, что σ i = D i . Из (4.3) и (4.4) очевидно, что путь в i че- рез вершину p не может иметь меньшую стоимость. То же самое справедливо и для любых других вершин, смежных с i и лежащих в S. Путь через вершины w и m также не может быть оптималь- ным. В самом деле имеем D m ≤ σ w +c wm , D i ≤ D m , x ≥ 0, отсюда D i ≤ D m + x ≤ σ w + c wm + x, что и требовалось доказать. Теперь оценим сложность алгоритма. На первом шаге множе- ство T состоит из n − 1 вершин (все, кроме v 0 ), на каждом шаге одну вершину присоединяем к множеству S, таким образом, ал- горитм делает n − 1 шаг, или O(n). На каждом шаге выбираем минимум из O(n) значений D i , затем обновляем эти значения, по одному сложению и сравнению на каждую из O(n) величин. Та- ким образом, общая сложность алгоритма составляет O(n 2 ). Пример 4.1 Для графа, задаваемого матрицей стоимости C = 0 10 5 ∞ ∞ ∞ 0 2 1 ∞ ∞ 3 0 9 2 ∞ ∞ ∞ 0 4 7 ∞ ∞ 6 0 , 126 0 ∞ ∞ ∞ ∞ 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 10 5 ∞ ∞ 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 8 5 14 7 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 8 5 13 7 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 8 5 9 7 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 8 5 9 7 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 Рис. 4.9. Пример работы алгоритма Дейкстры найти кратчайшие пути из начальной вершины во все остальные. Так как веса в матрице стоимости графа C неотрицатель- ны, для нахождения путей можно воспользоваться алгоритмом Дейкстры. Шаги алгоритма показаны на рис. 4.9. В качестве на- чальной вершины выберем вершину v 1 . Черным цветом помечены вершины, для которых кратчайшие пути уже найдены, т.е. при- надлежащие множеству S. Жирные ребра соответствуют текуще- му приближению кратчайшего пути, и самим кратчайшим путям — после окончания работы алгоритма. Числа в вершинах графа соответствуют значениям D i . Наконец, на каждом шаге серым помечена вершина, включаемая в множество S. Более формально шаги алгоритма приведены в табл. 4.1. 127 Таблица 4.1. Шаги алгоритма Дейкстры № S v D 1 2 3 4 5 1 ∅ 1 i 0 ∞ ∞ ∞ ∞ 2 {1} 3 10 i 5 ∞ ∞ 3 {1, 3} 5 8 14 i 7 4 {1, 3, 5} 2 i 8 13 5 {1, 2, 3, 5} 4 i 9 {1, 2, 3, 4, 5} 0 8 5 9 7 Решение (алгоритм Беллмана–Форда). Теперь рассмотрим ре- шение задачи 4.3 при предположении, что в графе могут присут- ствовать ребра с отрицательным весом, но нет отрицательных циклов (таких циклов, для которых сумма весов входящих в них ребер была бы отрицательной). Очевидно, что если граф содер- жит отрицательный цикл, то для любой вершины, достижимой из вершин этого цикла, стоимость минимального пути будет равна −∞. v 0 s p k i c ki c pi c si ( 1) k s W − ( ) ( 1) ( 1) min( , ) k k k i i j ji j V W W W c − − ∈ = + ( 1) k p W − ( 1) k i W − ( 1) k k W − Рис. 4.10. Принцип работы алгоритма Беллмана–Форда 128 Принцип, лежащий в основе алгоритма Беллмана–Форда, яв- ляется прямым применением динамического программирования, и изображен на рис. 4.10. Снова предположим, что ищем пути из вершины v 0 во все остальные вершины графа. Обозначим через W (k) i стоимость минимального пути из вершины v 0 в вершину i, состоящего не более, чем из k ребер. Очевидно, W (1) i = c v 0 i . Тогда принцип оптимальности задается функциональными уравнения- ми Беллмана W (k) i = min j∈V {W (k−1) i , W (k−1) j + c ji }. (4.5) Здесь V — множество всех вершин графа. Заметим, что на протя- жении всей работы алгоритма значение W (k) i может не являться весом искомого оптимального пути, и следовательно, может быть изменено. Алгоритм может закончить работу либо при условии k = n − 1 (так как в рассматриваемых условиях длина пути не может превосходить числа вершин в графе), либо в случае, когда при следующем k ни одна величина W (k) i не изменяется ∀i ∈ V : W (k) i = W (k−1) i (4.6) Оценим сложность данного алгоритма. На каждом шаге k, для каждой вершины i в (4.5) минимум ищется среди всех вершин графа. Вершин в графе n, и как уже отметили, нужно сделать в худшем случае порядка n шагов, что дает сложность алгоритма, оцениваемую как O(n 3 ). Пример 4.2 Для графа, задаваемого матрицей стоимости из примера 4.1, найти кратчайшие пути найти кратчайшие пути из начальной вер- шины во все остальные, пользуясь алгоритмом Беллмана–Форда. Работа алгоритма изображена на рис. 4.11. Жирные ребра со- ответствуют ребрам, входящим в оптимальные пути длины, не превышающей k. Рядом с каждой вершиной в скобках указан те- кущий оптимальный путь до этой вершины. Табл. 4.2 представ- ляет шаги алгоритма. Как видно, уже при k = 3 и k = 4 строки 129 0 10 5 ∞ ∞ 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 8 5 11 7 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 0 8 5 9 7 10 2 3 5 2 1 9 7 4 6 v 1 v 2 v 3 v 4 v 5 (1-2) (1-3) (1-3-2) (1-3) (1-3-5) (1-2-4) (1-3-2) (1-3-2-4) (1-3-5) (1-3) Рис. 4.11. Пример работы алгоритма Беллмана–Форда 130 Таблица 4.2. Шаги алгоритма Беллмана–Форда k W (k) 1 2 3 4 5 1 0 10 5 ∞ ∞ 2 0 8 5 11 7 3 0 8 5 9 7 4 0 8 5 9 7 таблицы совпадают, и алгоритм заканчивает свою работу в соот- ветствии с условием (4.6). Умножение последовательности матриц В этом разделе рассмотрим еще одну задачу, в которой мо- жет быть применен принцип динамического программирования. Рассмотрим две матрицы A и B размерности (p × r) и (r × q) соответственно. Напомним, что операция умножения матрицы A на матрицу B определена, если количество столбцов в матрице A равно количеству строк в матрице B. Результатом умножения является матрица C размерности (p × q), A p×r × B r×q = C p×q , где элементы c ij матрицы C определяются по правилу c ij = r k=1 a ik b kj , i = 1, p, j = 1, q. (4.7) Очевидно, для вычисления (4.7) требуется prq скалярных умно- жений и чуть меньшее количество сложений, однако будем учи- тывать только умножения, как более трудоемкую операцию. Для различия матричных и скалярных умножений в дальнейшем бу- дем называть операции в (4.7) элементарными умножениями. 131 Теперь, рассмотрим выражение A = A 1 × A 2 × . . . × A n , (4.8) где A i — матрица размера m i−1 × m i . В общем случае, опера- ция умножения матриц не коммутативна, т.е. для вычисления A не можем менять порядок следования матриц в (4.8). Однако эта операция ассоциативна, т.е. можно варьировать порядок выпол- нения умножений. Более того, оказывается, что меняя этот по- рядок (расставляя скобки), можно значительно изменять количе- ство требуемых для вычисления A умножений. Таким образом, можно сформулировать задачу поиска опти- мальной расстановки скобок, дающей минимальное суммарное число операций. Для решения этой задачи попробуем применить принцип динамического программирования. Задача 4.4 (задача о порядке умножения матриц). Для вы- ражения (4.8) найти оптимальный порядок расстановки скобок, дающий минимальное число элементарных умножений. Решение. Вначале оценим сложность нахождения оптималь- ного решения с помощью полного перебора. Для двух целых чисел i и j, 1 ≤ i ≤ j ≤ n введем обозначение A (i,j) = A i × A i+1 × . . . × A j−1 × A j (4.9) Тогда в выражении (4.8) A = A (1,n) . Заметим, что размерность матрицы A (i,j) составляет (m i−1 × m j ). Каким бы ни был порядок выполнения операций, при выпол- нении последнего умножения все множество матриц A 1 , . . . , A n разбивается на два подмножества: A = (A 1 × . . . × A k ) × (A k+1 × . . . × A n ), для некоторого k, 1 ≤ k < n или с учетом (4.9) A (1,n) = A (1,k) × A (k+1,n) (4.10) 132 A 1 A 2 A 3 A 4 ( ( ) ) A 1 A 4 A 2 A 3 A 1 A 2 A 3 A 4 ( ) ) A 1 A 4 A 2 A 3 ( Рис. 4.12. Примеры расстановки скобок с помощью бинарных деревьев Пусть P n — число вариантов расстановки скобок в произведении из n матриц. Имеем P 1 = 1, а с учетом (4.10) получаем P n = n−1 k=1 P k P n−k Решением этого уравнения является последовательность P n = F n−1 , где F (n) = 1 n + 1 C n 2n = O(4 n ). Связь количества бинарных деревьев F n и количества способов расстановок скобок P n не случайна. Действительно, каждой рас- становке скобок можно однозначно поставить в соответствие би- нарное дерево (рис. 4.12) для случая n = 4. Таким образом, слож- ность поиска оптимальной расстановки скобок полным перебором экспоненциальна. Выражение (4.10) может быть положено в основу применения динамического программирования. Напомним, для этого необхо- димо выделить подзадачи, нахождение оптимальных решений ко- 133 торых ведет к общему оптимальному решению. Очевидно, для на- хождения оптимального способа вычисления A (1,n) необходимы оптимальные способы вычисления A (1,k) и A (k+1,n) . Кроме того, необходимо найти такое k, при котором оптимально будет и само разбиение на подзадачи. Обозначим через N (i,j) минимальное количество элементар- ных умножений, которые необходимо выполнить для вычисления A (i,j) , 1 ≤ i ≤ j ≤ n. Рассуждая аналогично (4.10), для этого нужно найти такое k ∈ [i, j − 1], для которого разбиение A (i,j) = A (i,k) × A (k+1,j) (4.11) оптимально. Так как при заданных i и j величина k может при- нимать всего j − i различных значений, то оптимальное k может быть найдено перебором с учетом принципа оптимальности N (i,j) = min i≤k (i,k) + N (k+1,j) + m i−1 m k m j ). (4.12) Заметим, что N (i,i) = 0, так как в этом случае последователь- ность состоит из единственной матрицы и умножений не требу- 1 2 n 1 2 n i j 0 0 0 - - - j i 0 - - - - - - - 0 ( , ) i j N (1, ) n N Рис. 4.13. Реализация поиска минимального количества эле- ментарных умножений 134 ется. Выражение (4.12) может быть использовано как для оценки сложности оптимального вычисления (4.11), так и собственно для нахождения оптимальной последовательности операций — эта по- следовательность задается значениями k. Тем не менее, само по себе выражение (4.12) не дает никако- го выигрыша: его прямое вычисление «в лоб» приведет к перво- начальной экспоненциальной сложности. Применение принципа динамического программирования заключается в том, чтобы из- бежать многократного вычисления N (i,j) на разных этапах поиска и хранить эти значения для использования в дальнейшем. Для организации поиска определим таблицу, в которой будут храниться значения N (i,j) . Так как i ≤ j, фактически понадобится только верхняя правая часть таблицы (рис. 4.13). Целью вычисле- ния является нахождение N (1,n) , для этого необходимо будет вы- числить все N (i,j) для 1 ≤ i ≤ j ≤ n. Таблица инициализируется нулями по главной диагонали, так как N (i,i) = 0, далее ячейки за- полняются в соответствии с рекуррентной формулой (4.12). Для нахождения не только минимального количества элементарных умножений, но и самой оптимальной последовательности доста- точно дополнительно хранить таблицу значений k для каждого найденного N (i,j) Оценим сложность алгоритма, полученного с помощью дина- мического программирования. Нам необходимо заполнить поряд- ка n 2 ячеек таблицы, при этом вычисление минимума в каждой ячейке требует порядка n операций. Вместе это дает сложность поиска оптимальной расстановки скобок, равную O(n 3 ). Пример 4.3 Пусть задана последовательность произведений матриц A = A 1 × A 2 × A 3 × A 4 (4.13) и размерности матриц составляют соответственно (5×100), (100× 20), (20 × 40) и (40 × 60). Найти оптимальный порядок вычисле- ния матрицы A и количество требуемых для этого элементарных умножений. 135 A 1 A 2 A 3 A 4 ( ) A 1 A 4 A 2 A 3 A 1 A 2 A 3 A 4 ( ) ) A 1 A 4 A 2 A 3 ( ) ( 10000 48000 6000 48000 120000 30000 64000 198000 Рис. 4.14. Примеры расстановки скобок при умножении мат- риц Прежде всего, запишем размерности матриц в виде вектора (m 0 , m 1 , m 2 , m 3 , m 4 ) = (5, 100, 20, 40, 60). Покажем, что порядок выполнения матричных умножений влия- ет на сложность вычисления всего выражения. На рис. 4.14 пред- ставлены два способа вычисления (4.13). Первый способ использует расстановку скобок A = (A 1 × A 2 ) × (A 3 × A 4 ). Вычисление (A 1 × A 2 ) требует 5 · 100 · 20 = 10000 элементарных умножений, (A 3 × A 4 ) требует 20 · 40 · 60 = 48000 умножений, и наконец, получение конечного результата требует 5 · 20 · 60 = 6000 умножений. Всего это дает 64000 элементарных умножений. Аналогично, второй способ использует расстановку A = A 1 × (A 2 × (A 3 × A 4 )), что требует значительно большего числа умножений, 198000. 136 Таблица 4.3. Заполнение таблицы значений N (i,j) 1 2 3 4 1 0 m 0 m 1 m 2 min k=1,2 (N (1,k) + N (k+1,3) + m 0 m k m 3 ) min k=1,2,3 (N (1,k) + N (k+1,4) + m 0 m k m 4 ) 2 0 m 1 m 2 m 3 min k=2,3 (N (2,k) + N (k+1,4) + m 1 m k m 4 ) 3 0 m 2 m 3 m 4 4 0 Таблица 4.4. Итоговые значения N (i,j) и k N (i,j) = 1 2 3 4 1 0 10000 14000 26000 2 0 80000 168000 3 0 48000 4 0 k = 1 2 3 4 1 1 2 3 2 2 2 3 3 4 Для нахождения оптимальной расстановки скобок потребует- ся табл. 4.3. Ее ячейки будут хранить значения в соответствии с (4.12) и рис. 4.13. Ячейки, расположенные на главной диаго- нали, соответствуют последовательностям из одной матрицы, и инициализируются нулевыми значениями, так как никаких вы- числений в этом случае не требуется. Далее ищем N (i,i+1) — это соответствует последовательностям из двух матриц, и количество элементарных умножений в этом случае равно произведению раз- мерностей матриц. Дальше рассматриваются последовательности из трех матриц, и т.д. Итоговые значения N (i,j) и соответствующие им значения k приведены в табл. 4.4. Таким образом, получили, что вычисление 137 A 1 A 2 A 3 A 4 ( ) ) A 1 A 4 A 2 A 3 ( 26000 A 1 A 2 A 1 A 2 A 3 A 1 A 2 A 3 A 4 k = 1 k = 2 k = 3 (1 ,2 ) (1 ,3 ) (1 ,4 ) Рис. 4.15. Оптимальная расстановка скобок (4.13) может быть выполнено за N (1,4) = 26000 элементарных опе- раций. Саму последовательность вычислений можно получить с помощью таблицы значений k. При вычислении N (1,4) значение k равно 3, это значит, что последнее умножение было выполнено для матриц A = A (1,3) × A (4,4) = (A 1 × A 2 × A 3 ) × A 4 Матрица A (1,3) может быть вычислена за N (1,3) = 14000 элемен- тарных умножений, а соответствующее значение k равно 2, это дает A = (A (1,2) × A 3,3 ) × A 4 Аналогично раскрыв A (1,2) = A 1 × A 2 , получим окончательную расстановку A = ((A 1 × A 2 ) × A 3 ) × A 4 Бинарное дерево, соответствующее оптимальной расстановке ско- бок, изображено на рис. 4.15. 138 4.3. Метод ветвей и границ В этом подразделе рассмотрим другой способ организации ис- черпывающего поиска, называемый методом ветвей и границ. В подразд. 4.1 рассматривали организацию перебора возможных ре- шений задачи с помощью дерева поиска, и сформулировали под- ходы ограничения и слияния, с помощью которых данный перебор может быть сокращен. Можно сказать, что рассмотренный в под- разд. 4.2 метод динамического программирования представляет собой применение принципа слияния, так как позволяет избежать многократного вычисления одной и той же подзадачи. Метод вет- вей и границ реализует другой подход — ограничение дерева поис- ка, так как позволяет отбрасывать решения, заведомо не дающие оптимального результата. Рассмотрим это на примере. Задача 4.5 (задача о велосипедном замке). Кодовый замок для велосипеда состоит из n переключателей, каждый из кото- рых может находиться в двух состояниях, условно 0 и 1. Известно, что замок открывается комбинацией, в которой не менее полови- ны переключателей находятся в состоянии 0. Требуется найти эту комбинацию. Решение. Так как число переключателей и их состояний ко- нечно, то задачу можно решить простым перебором всех комбина- ций за 2 n попыток. Однако можно использовать дополнительную информацию о соотношении 0 и 1 в правильной комбинации, что- бы исключить лишние попытки. Чтобы реализовать поиск с уче- том этого ограничения, можно рассмотреть дерево поиска, как изображено на рис. 4.16, для случая n = 4. Перебор по вариантам комбинаций может быть осуществлен с помощью обхода по дере- ву поиска. При этом если какой-то узел уже содержит более, чем n/2 единиц, то все потомки этого узла могут быть исключены из рассмотрения. В рассмотренном примере ограничение, по которому произво- дилось отбрасывание узлов в дереве поиска, было явно сформули- ровано, а сама организация дерева поиска — довольно очевидной. Для применения метода ветвей и границ в общем случае нужно 139 0 1 00 000 0000 0001 0010 0011 0100 01 001 010 011 0101 0110 0111 1000 10 11 100 101 110 111 1001 1010 1011 1100 1101 1110 1111 Рис. 4.16. Дерево поиска для задачи о велосипедном замке сформулировать некие критерии, по которым будет производить- ся отсечение. Более того может оказаться, что деревья поиска мо- гут быть организованы различными способами и в зависимости от выбранных критериев сокращение полного перебора может быть более или менее эффективным. Для осуществления отсечения подмножеств решений в дереве поиска сформулируем понятия верхней и нижней границы. Пред- положим, что требуется решить некую оптимизационную задачу, где для данной целевой функции необходимо найти ее экстремум t, пусть для определенности это будет минимум t min Для каждой вершины i дерева поиска определим верхнюю границу t i , под которой будем понимать стоимость некоторого, уже существующего решения, не обязательно оптимального, т.е. t i ≥ t min Далее для каждой вершины i определим нижнюю границу t i , которая означает, что стоимость любого решения t i , достижимого из вершины i, не может быть меньше, чем t i , т.е. t i ≤ t i . Отметим, что решения со стоимостью, в точности равного t i , может и не существовать. 140 |