Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
t t ≥ 2 2 t t < k k t t < s s t t ≥ Рис. 4.17. Принцип метода ветвей и границ Очевидно, что если для какого-то состояния i все достижи- мые из этого состояния решения обладают стоимостью, не мень- шей, чем некоторое уже известное решение, т.е. t i ≤ t i , то рас- сматривать эти решения не имеет смысла, и все потомки состо- яния i могут быть отброшены. Этот принцип проиллюстрирован на рис. 4.17. Применение этого метода продемонстрируем на уже рассмат- ривавшейся в подразд. 2.1 задаче коммивояжера (задача 2.1 ). Задача 4.6 (задача коммивояжера). Коммивояжеру для со- вершения торговых сделок требуется объехать n городов и вер- нуться в свой родной город, при этом в каждом городе он может побывать только один раз. Среди множества возможных марш- рутов требуется найти тот, который позволит минимизировать затраты на поездку. Стоимость маршрутов задана матрицей сто- имости C C = 1 2 3 4 5 1 −∞ 25 40 31 27 2 5 −∞ 17 30 25 3 19 15 −∞ 6 1 4 9 50 24 −∞ 6 5 22 8 7 10 −∞ 141 Решение (метод ближайшего соседа). Напомним, что в под- разд. 2.1 уже строили математическую модель для этой задачи в виде графа с матрицей стоимости C, и предложили метод реше- ния этой задачи путем полного перебора всех маршрутов, оценив сложность такого решения как O(n!). Прежде чем рассмотреть ре- шение этой задачи методом ветвей и границ, дадим простой метод нахождения пути, который не всегда дает оптимальное решение, но интуитивно должен давать, как правило, не худшее решение (такие алгоритмы часто называются эвристическими и подопти- мальными). Этот метод называется «методом ближайшего сосе- да» и заключается в том, что в каждый момент времени движемся в ближайший еще не посещенный город. Для этого нужно n раз выбрать минимум в строке матрицы стоимости C, что дает слож- ность порядка O(n 2 ). В этом случае применение метода ближай- шего соседа дает объезд π = (123541) со стоимостью C(π) = 62. 1 2 3 4 5 3 4 5 4 5 5 1 4 1 25 42 48 54 76 43 53 62 3 5 79 61 55 3 68 60 3 4 57 4 3 50 63 84 Рис. 4.18. Дерево поиска для задачи коммивояжера 142 Решение (метод ветвей и границ I ). Попробуем теперь при- менить к задаче коммивояжера метод ветвей и границ. Для этого нужно определить, как будем строить дерево поиска и как будем вычислять нижние и верхние границы для каждого узла дере- ва поиска. Наиболее очевидно реализовать перебор следующим образом (рис. 4.18). В начальный момент времени двигаемся из города 1 и имеем четыре варианта движения. После переезда во второй город остается три варианта для дальнейшего движения, потом два, и наконец, единственный оставшийся непосещенный город плюс стоимость возврата из него в город 1. В качестве верхней границы, т.е. стоимости некоторого извест- ного, но не обязательно оптимального пути, можно выбрать путь, полученный методом ближайшего соседа. В дальнейшем, по мере обхода дерева и получения стоимостей других путей (не обяза- тельно оптимальных) оценка t может улучшаться (чтобы отсече- ние ветвей дерева было максимально эффективным, значение t должно быть как можно меньшим). На рис. 4.18 показан обход по одной ветви дерева поиска, че- рез вершину 2. Нижние границы для вершин указаны в квадра- тах. Действуя аналогично по всей оставшейся части дерева, мож- но найти оптимальный объезд. Из рассмотренного примера довольно быстро становится яс- но, что применение метода ветвей и границ не очень эффективно. Дерево поиска сокращается, но это сокращение незначительно, и происходит оно ближе к нижним уровням дерева. Действительно, в качестве нижней границы используется стоимость части пути, в то время как верхней границей является стоимость полного пути. Очевидно, что в среднем для случайной матрицы C превышение стоимости части пути над верхней границей будет происходить ближе к листьям дерева, с ростом количества уже пройденных городов. Попробуем повысить эффективность сокращения пере- бора путем видоизменения структуры дерева поиска и подходов к вычислению нижней границы обновленного дерева. Решение (метод ветвей и границ II ). Рассмотрим другой спо- соб построения дерева поиска для задачи о коммивояжере. Чтобы 143 {В } { , } i j { , } i j Рис. 4.19. Другое дерево поиска для задачи коммивояжера производить отсечения ветвей в дереве поиска вне зависимости от глубины дерева нужно, чтобы нижняя граница для каждого узла дерева оценивала не часть маршрута, а весь объезд городов це- ликом. Будем строить дерево поиска как показано на рис. 4.19. Узлами в этом дереве будут подмножества всего множества объ- ездов. Корнем дерева является все множество объездов. Далее выбирается некоторое ребро (i, j), ведущее из города i в город j, и множество объездов делится на два непересекающихся множе- ства: всех маршрутов, содержащих ребро (i, j) (на рис. 4.19 по- мечено как {i, j}) и всех маршрутов, не содержащих ребро (i, j) (на рис. 4.19 помечено как {i, j}). Для такого дерева поиска эф- фективность отсечения ветвей будет определяться выбором ребра (i, j) для каждого узла дерева, а также способом задания верх- ней и нижней границы. Как и раньше, в качестве верхней оцен- ки может рассматриваться наименьшая стоимость какого-то уже известного пути. Как можно для узлов такого дерева поиска по- строить нижнюю оценку? Рассмотрим матрицу стоимости из задачи 4.6 . C = 1 2 3 4 5 1 −∞ 25 40 31 27 2 5 −∞ 17 30 25 3 19 15 −∞ 6 1 4 9 50 24 −∞ 6 5 22 8 7 10 −∞ 144 Выполним приведение первой строки матрицы C, т.е. вычтем из каждой ячейки первой строки минимальную (неотрицатель- ную) стоимость, в данном случае это 25, и получим матрицу C C = 1 2 3 4 5 1 −∞ 0 15 6 2 −25 2 5 −∞ 17 30 25 3 19 15 −∞ 6 1 4 9 50 24 −∞ 6 5 22 8 7 10 −∞ Так как любой объезд для задачи коммивояжера содержит выезд из города 1, то легко заметить, что выполненная операция приведения по строке уменьшает стоимость всех объездов на 25, но не изменяет соотношения «более длинный»–«более короткий» путь (меняя стоимость объезда, не меняет самого порядка посе- щения городов в оптимальном маршруте). Но тогда аналогичную операцию приведения можно выполнить для всех строк матрицы C C = 1 2 3 4 5 1 −∞ 0 15 6 2 −25 2 0 −∞ 12 25 20 −5 3 18 14 −∞ 5 0 −1 4 3 44 18 −∞ 0 −6 5 15 1 0 3 −∞ −7 Более того, так как любой объезд содержит и въезд в любой го- род, аналогичную операцию приведения можно выполнить и для столбцов. Конечный вариант приведенной матрицы C выглядит так: C = 1 2 3 4 5 1 −∞ 0 15 3 2 −25 2 0 −∞ 12 22 20 −5 3 18 14 −∞ 2 0 −1 4 3 44 18 −∞ 0 −6 5 15 1 0 0 −∞ −7 −3 (4.14) 145 Итак, стоимость C(π) любого объезда π уменьшили на сумму вычтенных величин H: H = 25 + 5 + 1 + 6 + 7 + 3 = 47. Если C (π) — стоимость объезда π по матрице стоимости C , то C(π) = C (π) + H, т.е. никакой объезд не может иметь стоимость меньшую, чем H, а следовательно, можно принять величину H за нижнюю границу для множества всех объездов t = H. Заметим, что в соответствии с определением нижней границы, это не означает, что маршрут со стоимостью H существует. Теперь, определив нижнюю границу стоимости, сформулиру- ем критерии выбора ребра, по которому будет производиться раз- биение множества объездов. Очевидно, что в качестве кандидатов надо рассматривать те ребра, стоимость которых в матрице C (π) минимальна и равна нулю. Это связано с тем, что для уменьше- ния стоимости объезда хотелось бы как выезжать из любого горо- да по ребру с наименьшей возможной стоимостью, так и въезжать в любой город по ребру с наименьшей возможной стоимостью. Однако в матрице C из (4.14) есть шесть возможных ребер со стоимостью 0. Чтобы понять, какого критерия придерживать- ся при выборе из этих ребер, рассмотрим вначале пример. Допу- стим, что выбираем для разбиения ребро (2, 1). Тогда разбиваем все множество объездов на объезды, содержащие ребро (2, 1) (обо- значим это множество через π {2,1} ), и не содержащие этого ребра (обозначим как π {2,1} ). Рассмотрим вначале множество π {2,1} . Так как любой объезд в этом множестве содержит ребро (2, 1), то это означает, что уже нельзя выехать из города 2 ни в какой другой город, кроме 1, и не можем въехать в город 1 ни из какого города, кроме 2, т.е. можно 146 i s i m i n i p (i m , i n ) Рис. 4.20. Запрещение ребер в задаче коммивояжера исключить вторую строку и первый столбец из матрицы C C {2,1} = 2 3 4 5 1 0 15 3 2 3 14 −∞ 2 0 4 44 18 −∞ 0 5 1 0 0 −∞ Заметим, что обязательное наличие в объезде ребра (2, 1) запре- щает использование ребра (1, 2), так как это привело бы к циклу внутри маршрута, что запрещено по условию задачи, поскольку в каждом городе можно побывать лишь один раз. Обобщим это условие следующим образом. Пусть на некотором шаге рассмат- риваем множество объездов, как показано на рис. 4.20, т.е. в этом множестве существуют участки пути, из города i s в город i m , и из города i n в город i p . Далее предполагаем рассмотреть множе- ство объездов, в которых присутствует ребро (i m , i n ). Тогда для предотвращения образования цикла следовало бы исключить реб- ро (i n , i m ). Однако из города i n уже есть выезд в какой-то другой город, а это значит, что на более раннем шаге уже исключали все выезды из i n , и ребро (i n , i m ) и так уже исключено. Более того, при выборе ребра (i m , i n ) уже исключены все выезды из всех горо- дов, кроме i p , и все въезды во все города, кроме i s . Тем не менее, все же присутствует ребро, которое необходимо исключить — это ребро (i p , i s ), так как очевидно, оно образовывало бы цикл. 147 Запрещение ребра (1, 2) приводит нас к матрице C {2,1} = 2 3 4 5 1 −∞ 15 3 2 3 14 −∞ 2 0 4 44 18 −∞ 0 5 1 0 0 −∞ Матрицу C {2,1} можно привести аналогично матрице C, что дает C {2,1} = 2 3 4 5 1 −∞ 13 1 0 −2 3 13 −∞ 2 0 4 43 18 −∞ 0 5 0 0 0 −∞ −1 (4.15) Тогда можно сопоставить множеству π {2,1} матрицу C {2,1} и уточ- нить нижнюю границу, которая для множества π {2,1} равна t = 47 + 2 + 1 = 50. Теперь рассмотрим множество π {2,1} . Запрещение ребра (2, 1) видоизменяет матрицу C следующим образом: C {2,1} = 1 2 3 4 5 1 −∞ 0 15 3 2 2 −∞ −∞ 12 22 20 3 18 14 −∞ 2 0 4 3 44 18 −∞ 0 5 15 1 0 0 −∞ Эту матрицу также можно привести C {2,1} = 1 2 3 4 5 1 −∞ 0 15 3 2 2 −∞ −∞ 0 10 8 −12 3 15 14 −∞ 2 0 4 0 44 18 −∞ 0 5 12 1 0 0 −∞ −3 148 Изменение нижней границы в этом случае составит t = 47 + 12 + 3 = 62. Итак, разбиение множества объездов на два множества ведет к изменению матрицы стоимости для каждого подмножества, и обновлению нижней границы. Выбор ребра, по которому произво- дится разбиение, может быть сделан с учетом изменений нижней границы. Ясно, что для более эффективной работы метода ветвей и гра- ниц нужно, чтобы нижняя граница росла быстрее — это увели- чивает возможность превышения ее значением верхней границы, и следовательно, отсечения ветви дерева поиска. Однако кроме этого, в данном случае имеет значение стараемся ли отсечь вет- ви, являющиеся левыми или правыми потомками текущего узла. Действительно, левым потомком в соответствии с рис. 4.19 явля- ется подмножество со включенным ребром, а правым потомком — подмножество с исключенным ребром. Как видно на примере ребра (2, 1), включение ребра ведет к уменьшению размерности матрицы стоимости, в то время как исключение ребра сохраняет размерность матрицы. С точки зрения сложности, конечно, более выгодно рассматривать матрицы меньшей размерности, а следо- вательно, при прочих равных условиях более предпочтительно от- сечение ветвей, которые требуют обработки матриц большей раз- мерности. Другими словами, более эффективно отсекать ветви «справа», т.е. подмножества с исключаемыми ребрами. Для этого нужно максимизировать рост нижней границы для правых по- томков текущего узла, а это, в свою очередь, может быть сделано с помощью выбора ребра, по которому производится разбиение. Напомним, что было шесть кандидатов на разбиение, это реб- ра (1, 2), (2, 1), (3, 5), (4, 5), (5, 3) и (5, 4). Попробуем оценить рост нижней оценки «правой» ветви для каждого из этих ребер. Как уже знаем, для ребра (2, 1) этот рост составит 15. При исключе- нии ребра (1, 2) этот рост составит всего 1 + 2 = 3. Продолжим и получим табл. 4.5. Как видно из табл. 4.5, максимальный прирост нижней границы дает исключение ребра (2, 1). 149 Таблица 4.5. Прирост нижней границы Ребро Прирост t (1, 2) −→ 3 (2, 1) −→ 15 (3, 5) −→ 2 (4, 5) −→ 3 (5, 3) −→ 12 (5, 4) −→ 2 Продолжим построение дерева поиска (рис. 4.21). Выбрав на первом шаге ребро (2, 1) для разбиения всего множества, рассмот- рим теперь все множества объездов, включающих в себя ребро (2, 1). Матрица стоимостей для таких объездов задана в (4.15), а нижняя граница равна 50. Выберем ребро для дальнейшего раз- биения. Оценим прирост нижней границы при исключении ребер, соответствующих нулевым стоимостям в матрице C {(2,1)} . Таких ребер шесть: (1, 5) −→ 1 (3, 5) −→ 2 (4, 5) −→ 18 (5, 2) −→ 13 (5, 3) −→ 13 (5, 4) −→ 1 Таким образом, максимальный прирост дает исключение ребра (4, 5). Минимальная граница при этом достигает t = 50 + 18 = 68, что больше текущей верхней границы t = 62, и следовательно, соответствующую ветвь дерева поиска можно исключить. Теперь рассмотрим множество со включенным ребром (4, 5). В соответствии с рис. 4.20, дополнительно требуется исключить ребро (5, 4). Матрица стоимости примет вид 150 {В } {2, 1} {2, 1} 50 62 {4, 5} {4, 5} 53 68 {1, 4} {1, 4} 64 65 Рис. 4.21. Метод ветвей и границ для задачи коммивояжера C {4,5} = 2 3 4 1 −∞ 12 0 −1 3 11 −∞ 0 −2 5 0 0 −∞ , а нижняя граница равна t = 50 + 3 = 53. На следующем шаге имеем четыре кандидата на разбиение: (1, 4) −→ 12 (3, 4) −→ 11 (5, 2) −→ 11 (5, 3) −→ 12 Для разбиения выберем ребро (1, 4), исключение этого ребра дает прирост нижней границы t = 53+12 = 65, и эта ветвь далее может не рассматриваться. При включении ребра (1, 4) в соответствии с рис. 4.20, исклю- чаем ребро (5, 2). Обновленная матрица стоимости: C {1,4} = 2 3 3 0 −∞ −11 5 −∞ 0 , а нижняя граница равна t = 53 + 11 = 64. 151 Имея верхнюю границу, равную 62, полученную методом бли- жайшего соседа, дальнейший поиск можно прекратить, так как левое поддерево множества всех объездов дает решения стоимо- сти, большей 62 (см. рис. 4.21). Рассмотрение правой ветви так- же может быть опущено, так как никакие решения этой ветви не дадут меньшей стоимости. Таким образом, уже после рассмот- рения трех разбиений найдена оптимальная стоимость. Конечно, для определения всех решений со стоимостью 62 (которых может быть несколько) требуется достроить правую ветвь дерева поиска. Тем не менее, применение метода ветвей и границ в среднем не снижает сложность решения задачи коммивояжера до уровня ниже экспоненциальной. Известно, что для случайной (n × n)- матрицы стоимости эта сложность составляет O(1, 26 n ). 4.4. Методы решета В этом подразделе рассмотрим еще один метод исчерпываю- щего поиска, основывающийся на исключении из рассмотрения объектов, чьи параметры по тем или иным признакам не удовле- творяют критериям поиска. Этот метод называется методом ре- шета, так как в процессе поиска постепенно отсеиваются исклю- чаемые варианты. Проиллюстрируем этот принцип на примере. Задача 4.7 (поиск простых чисел). Для заданного числа n выписать простые числа, лежащие в интервале от n до n 2 Решение (решето Эратосфена). Напомним, что простыми на- зываются целые числа, не имеющие других делителей, кроме еди- ницы и самих себя (подразумевается деление нацело). Рассмотрим числовой ряд n, n + 1, n + 2, . . . , n 2 − 1, n 2 Будем вычеркивать из этой последовательности сначала все чис- ла, кратные двум, затем кратные трем, и т.д. Заметим, что чи- сел, кратных четырем, шести, восьми после этих двух «просе- иваний» не останется. Вообще, просеиванию будут подвергаться числа, кратные простым. Таким образом, после просеивания для 152 наибольшего простого числа, меньшего n, в искомом интервале не останется составных чисел. Применение принципа решета изобра- жено на рис. 4.22. Пример 4.4 Применим решето Эратосфена для n = 6. Выпишем последо- вательность 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. Просеивая эту последовательность решетом с шагом m 1 = 2, m 2 = 3, m 3 = 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, m 1 = 2, 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, m 2 = 3, 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, m 3 = 5. В результате получим, что простыми числами в данном интервале являются оставшиеся невычеркнутыми 7, 11, 13, 17, 19, 23, 29, 31. Рассмотренный способ решения можно определить с помощью обобщенного модульного решета. Рассмотрим множество m 1 , m 2 , . . ., m t целых чисел (модулей). Для каждого модуля m i определим n i чисел a ij , и зададим арифметические прогрессии вида m i k + a ij , j = 1, . . . , n i , 9 7 10 8 11 12 4 6 К а К а К а 2 3 4 5 6 8 9 10 12 13 П Рис. 4.22. Решето Эратосфена 153 где k — натуральное число. Задачей поиска является отыскание чисел в заданном интервале, принадлежащих одной из прогрессий для каждого модуля m i В решете Эратосфена модули m i представляют собой простые числа, не превышающие n (в примере 4.4 это 2, 3 и 5), для каждого модуля задается n i = m i − 1 прогрессий, где a ij = j. Для применения решета необходимо сформулировать: признак вычеркивания; технику вычеркивания. Признак позволяет определить, какие числа нужно отбрасы- вать, техника — каким образом это отбрасывание реализовать. Это обобщенное модульное решето является нерекурсивным — в нем модули m i известны заранее. Можно рассматривать также и рекурсивное решето — в нем значение модуля m i зависит от чисел, оставшихся в последовательности после просеивания по предыду- щим модулям. Решето Эратосфена может быть сформулировано как рекурсивное решето, если предположить, что простые чис- ла, не превышающие n, также неизвестны — тогда они, в свою очередь, могут быть найдены с помощью решета Эратосфена. Рассмотрим еще один пример эффективного применения ре- шета для сокращения поиска. Для этого нам понадобится несколь- ко дополнительных понятий. Утверждение 4.1 (деление нацело). Можно доказать, что для любых целых чисел a и b существуют единственные целые числа q (частное) и r (остаток ): a = qb + r, 0 ≤ q < b. (4.16) Определение 4.1 Операция нахождения остатка r в выражении (4.16) по задан- ным a и b называется взятием числа a по модулю b, и обознача- ется r = a mod b. Определение 4.2 Целые числа a и b называются сравнимыми по модулю неко- торого числа m, если они имеют одинаковые остатки при делении 154 нацело на m. Это обозначается как a ≡ b mod m. Для операции сравнения, задаваемой определением 4.2 , легко доказать следующие свойства: (a + b) mod m ≡ (a mod m + b mod m) mod m, (4.17) (a · b) mod m ≡ (a mod m · b mod m) mod m. (4.18) Определение 4.3 Число a называется квадратичным вычетом по модулю про- стого числа p, НОД(a, p) = 1, если существует решение уравнения x 2 ≡ a mod p. (4.19) Число a называется квадратичным невычетом по модулю про- стого числа p, если решения уравнения (4.19) не существует. Т е о р е м а 4.1 Число квадратичных вычетов по модулю простого числа p равно числу квадратичных невычетов, т.е. (p − 1)/2. Доказательство. При выполнении операций по модулю чис- ла p можем ограничиться рассмотрением только целых чисел из множества A p = {1, . . . , p − 1}, так как в силу свойств (4.17) и (4.18) все операции по модулю с целыми числами эквивалентны операциям по модулю с числами из A p . Имеем (p − i) 2 = p 2 − 2pi + i 2 ≡ i 2 mod p. (4.20) Если число a является квадратичным вычетом по модулю p, то для некоторого i ∈ A p выполняется сравнение i 2 ≡ a mod p. Но тогда в силу (4.20) число (p − i) 2 также является квад- ратичным вычетом, причем других решений уравнения (4.19) не существует, так как это уравнение второй степени. Тогда, если 155 i пробегает все значения из A p , все величины i 2 mod p различ- ны для i = 1, . . . , (p − 1)/2 и совпадают с уже полученными для i = (p − 1)/2, . . . , p − 1. Таким образом, имеем (p − 1)/2 различных квадратичных вычетов по модулю p и в множестве A p остается еще (p − 1)/2 квадратичных невычетов. Пример 4.5 Найдем квадратичные вычеты по модулю 7. Пусть величина i пробегает значения из A 7 : 1 2 ≡ 1 mod 7, 2 2 ≡ 4 mod 7, 3 2 ≡ 2 mod 7, 4 2 ≡ 2 mod 7, 5 2 ≡ 4 mod 7, 6 2 ≡ 1 mod 7. Таким образом, квадратичными вычетами являются 1, 2, 4. Квад- ратичными невычетами являются 3, 5, 6. Теперь можно рассмотреть следующую задачу. Задача 4.8 . Среди первого миллиона чисел в последователь- ности Фибоначчи найти числа, являющиеся квадратами. Решение. Последовательность Фибоначчи рассматривалась в примере 3.4. Это рекуррентная последовательность, задаваемая с помощью уравнения (3.12) F (n + 2) = F (n + 1) + F (n), с начальными условиями F (0) = 0, F (1) = 1. Решением этой по- следовательности является выражение (3.14) F (n) = 1 √ 5 1 + √ 5 2 n − 1 − √ 5 2 n , которое приблизительно можно оценить F (n) ≈ (1, 6) n > 2 n/2 156 При n = 1000000 получаем числа порядка 2 500000 , разложение на множители которых, и следовательно, поиск среди них квад- ратов «лобовым» методом, конечно же, нереализуемо. Попробуем применить метод решета. Рассмотрим последовательность P (n), полученную из последовательности Фибоначчи взятием по моду- лю простого числа p P (n) = F (n) mod p. Пользуясь свойством (4.17), можем записать P (n) P (n + 2) = P (n + 1) + P (n) mod p. (4.21) Эта последовательность является периодической, причем период начинается с P (0) = 0. Докажем это. Действительно, представим последовательность P (n) в виде пар (P (0), P (1)), (P (1), P (2)), . . . , (P (p 2 ), P (p 2 + 1)), . . . . Всего может существовать p 2 различных пар (P (i − 1), P (i)), сле- довательно, самое позднее, p 2 + 1-я пара будет совпадать с одной из предыдущих. Так как пара (P (i − 1), P (i)) полностью и одно- значно определяет следующую пару (P (i), P (i + 1)), последова- тельность P (n) является периодической. Более того, пара (P (i − 1), P (i)) полностью и однозначно определяет и предыдущую пару (P (i − 2), P (i − 1)), а следовательно, если совпали i- и j-я пары для некоторых i = j, то совпадут также (i − 1)- и (j − 1)-я па- ры. Это означает, что первой повторившейся парой в P (n) будет (P (0), P (1)), что и требовалось доказать. Другими словами, ес- ли период последовательности P (n) равен T p , то для любого n P (n) = P (i + kT p ), где i ∈ [0, T p − 1]. К примеру, рассмотрим первые элементы последовательность Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, . . . . Взяв эту последовательность по модулю p = 7, получим (0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1), 0, 1, 1, 2, . . . . 157 Начиная с P (16), последовательность начинает повторяться, сле- довательно, имеем T 7 = 16. Очевидно, если число a является квад- ратом, то оно будет квадратичным вычетом по любому простому модулю p. Обратное неверно, например число 15 является квад- ратичным вычетом по модулю 7, так как 1 2 ≡ 6 2 ≡ 15 mod 7, но очевидно — не квадрат. Однако это означает, что если число a является квадратичным невычетом по какому-либо модулю, то оно не может являться квадратом. Таким образом, сформулиро- вали признак вычеркивания — для исключения чисел, заведомо не являющихся квадратами, можно вычеркивать квадратичные невычеты из последовательностей P (n) по различным модулям. Теперь сформулируем технику вычеркивания. Так как дока- зали, что последовательность P (n) по модулю p является периоди- ческой с периодом T p , найдем квадратичные невычеты по модулю p в первых T p элементах P (n). Если к примеру элемент P (i) яв- ляется таким квадратичным невычетом, то исключению должны подвергнуться также все элементы P (i + kT p ). Заметим, что для выписывания последовательности P (n) не нужно строить последовательность F (n), это можно делать с по- мощью (4.21). Определение квадратичной вычетности по модулю простого числа выполняется для чисел, не превышающих неболь- ших значений p, для этого известен эффективный алгоритм. Для вычеркивания нужно работать не с самими числами Фибоначии, а с индексами в последовательности, для восстановления самих чи- сел при необходимости можно воспользоваться формулой (3.14). Для рассматриваемого примера уже после отсеивания квадра- тичных невычетов по первым 32 простым числам единственными кандидатами в квадраты остаются F (0), F (1), F (2) и F (12), рав- ные соответственно 0, 1, 1, 144. Доказано, что других квадратов среди чисел в последовательности Фибоначчи нет. 4.5. Приближение исчерпывающего поиска В подразделе рассмотрим методы решения задач, не всегда дающие оптимальный результат, однако позволяющие найти, как правило, неплохое к оптимальному приближение. 158 Пусть есть n объектов σ 1 , σ 2 , . . . , σ n , характеризующихся па- раметрами x 1 , x 2 , . . . , x n . Далее, пусть требуется найти объект σ i с минимальным значением параметра x i , σ i : x i = min j∈{1,...,n} {x j }. (4.22) Предположим, что есть алгоритм A O , дающий оптимальное решение (путем исчерпывающего поиска), значение которого рав- но x O . Кроме этого, пусть есть некоторый алгоритм A T , дающий некое решение x T , очевидно, что x T ≥ x O Определение 4.4 Алгоритм A T (при поиске минимума) дает приближение к исчерпывающему поиску с точностью M , если для любого набора входных данных x T x O ≤ M. Если в (4.22) требуется решать задачу поиска максимума, вве- денные обозначения модифицируются естественным образом. Рас- смотрим приближение к исчерпывающему поиску на примере за- дачи коммивояжера. Задача 4.9 (задача коммивояжера с ограничениями). Комми- вояжеру для совершения торговых сделок требуется объехать n городов и вернуться в свой родной город, при этом в каждом го- роде он может побывать только один раз. Среди множества воз- можных маршрутов требуется найти тот, который позволит ми- нимизировать затраты на поездку. Стоимость маршрутов задана матрицей стоимости C, симмет- ричной относительно главной диагонали, т.е. c ij = c ji , i, j ∈ {1, . . ., n}. Кроме этого, для стоимостей переездов выполняется неравен- ство треугольника, т.е. c ik +c kj ≥ c ij для любых i, j, k ∈ {1, . . . , n}. Решение (алгоритм включения ближайшего города в объезд ). Здесь рассмотрим задачу коммивояжера с некоторыми допол- нительными ограничениями: на симметричность задачи и на вы- полнение неравенства треугольника. На каждом этапе будем счи- тать, что уже есть объезд для k городов, k < n. Далее среди 159 1 1 2 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 Рис. 4.23. Алгоритм включения ближайшего города в объезд оставшихся не включенных в объезд городов будем находить го- род в некотором смысле ближайший к текущему объезду. После включения n городов получим искомый объезд для всех городов. На первом шаге предполагаем, что объезд состоит из единственно- го города. Далее включаем в объезд еще один город, ближайший к первому. На следующем шаге включается город, ближайший к одному из двух, уже включенных городов, и т.д. Этот процесс изображен на рис. 4.23. Пунктирными кругами помечены города, еще не включенные в объезд. Сформулируем более строго понятие города, ближайшего к объезду. Пусть π = (j 1 , . . . , j k ) — объезд, 160 включающий в себя k городов. Под расстоянием d(i, π) от города i до объезда π будем понимать величину d(i, π) = min j∈π {c ij }. При включении города в объезд выбирается город i ∗ с минималь- ным расстоянием до объезда i ∗ : d(i ∗ , j) = min i∈π,j∈π {d(i, j)}. Этот алгоритм можно реализовать со сложностью O(n 2 ), что су- щественно эффективнее экспоненциальных переборных алгорит- мов. Более того, для рассмотренного алгоритма оказывается воз- можным оценить, насколько хуже могут быть выдаваемые им ре- шения в сравнении с оптимальным алгоритмом. Т е о р е м а 4.2 Пусть T (n) — стоимость объезда, даваемая алгоритмом включения ближайшего города для n городов; O(n) — стоимость оптимального объезда. Для любой симметричной задачи комми- вояжера, удовлетворяющей неравенству треугольника T (n) O(n) ≤ 2. Доказательство. Попробуем оценить эффективность описан- ного алгоритма включения ближайшего города следующим обра- зом. Будем строить маршрут в соответствии с этим алгоритмом в предположении, что заранее знаем оптимальный объезд. При включении каждого следующего города будем оценивать возмож- ный проигрыш по сравнению с оптимальным объездом и отсюда получим оценку эффективности M . Итак, допустим, что есть оптимальный объезд (рис. 4.24). Этот объезд является замкнутым, и на первом шаге уберем одно из ребер с некоторой стоимостью c 0 , получив незамкнутую цепоч- ку городов. Из всех городов выберем некоторый начальный, на рис. 4.24, а начальный город b помечен жирной линией. На втором 161 |