Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
F n-i- 1 F i Рис. 3.6. Разбиение бинарного дерева на поддеревья C помощью производящей функции иногда бывает удобно за- давать последовательность, не выписывая ее, и совершать дей- ствия над последовательностями. В следующем примере рассмат- ривается задача о числе бинарных деревьев. Под бинарным дере- вом будем понимать дерево, содержащее не более двух непосред- ственных потомков. Задача 3.3 (задача о числе бинарных деревьев). Найти число F n бинарных деревьев, состоящих из n вершин. Решение. В тривиальном случае, когда V = ∅, имеем F 0 = 1. Далее, пусть дерево содержит хотя бы одну вершину. В соответ- ствии с определением дерева, любое подмножество вершин и ре- бер исходного дерева также будет являться деревом и, так как рассматриваемое нами дерево бинарное, разобьем его на два под- дерева, как показано на рис. 3.6. Если исходное дерево содержит n вершин, а одно из получившихся поддеревьев — i вершин, то второе из поддеревьев будет содержать n − i − 1 вершину. Ясно, что величина i может варьироваться от 0 до n−1. Таким образом, получим, что F n = n−1 i=0 F i F n−i−1 (3.50) Или, что то же самое, F n = F 0 F n−1 + F 1 F n−2 + . . . + F n−2 F 1 + F n−1 F 0 (3.51) Введем в рассмотрение производящую функцию F (x) = ∞ n=0 F n x n (3.52) 106 Далее определим два многочлена A(x) = ∞ i=0 a i x i , B(x) = ∞ i=0 b i x i Тогда свертка этих многочленов будет A(x)B(x) = C(x) = ∞ i=0 c i x i , (3.53) где коэффициенты c i определяются как c i = i j=0 a j b i−j = a 0 b i + . . . + a i b 0 (3.54) Приняв A(x) = B(x) = F (x), и с учетом (3.50) и (3.51), из (3.53) и (3.54) получим F 2 (x) = ∞ n=0 (F 0 F n + . . . + F n F 0 )x n = ∞ n=0 F n+1 x n Домножив обе части на x, имеем xF 2 (x) = ∞ n=0 F n+1 x n+1 + F 0 − F 0 = F (x) − F 0 = F (x) − 1. Отсюда xF 2 (x) − F (x) + 1 = 0 и введя замену переменной y = F (x), получим квадратное урав- нение xy 2 − y + 1 = 0, 107 которое имеет решения y 1,2 = 1 ± √ 1 − 4x 2x Имеем F 0 = F (0) = 1. Попробовав подставить F (0) вместо y 1 , получим F (0) = y 1 = 1 + √ 1 − 4x 2x = 1 0 = ∞. Подстановкой F (0) = y 2 получим F (0) = y 2 = 1 − √ 1 − 4x 2x = 0 0 Следовательно, F (x) = y 2 = 1 − √ 1 − 4x 2x (3.55) В соответствии с биномом Ньютона для ненатуральных степе- ней n (a + b) n = ∞ i=0 C i n a i b n−i , где C i n = n(n − 1) · . . . · (n − i + 1) i! Тогда C i 1/2 = 1/2 · (1/2 − 1) · . . . · (1/2 − i + 1) i! = = 1 2 i · 1 · (−1) · (−3) · . . . · (−(2i − 3)) i! = = (−1) i−1 2 i · 1 · 3 · . . . · (2i − 3) i! · 2 · 4 · . . . · (2i − 2) 2 · 4 · . . . · (2i − 2) = = (−1) i−1 2 2i−1 · (2i − 2)! (i − 1)!(i − 1)!i = = (−1) i−1 2 2i−1 i C i−1 2i−2 108 С учетом этого 1 − √ 1 − 4x = 1 − 1 − ∞ i=1 C i 1/2 (−4) i x i = = − ∞ i=1 (−1) i−1 (−1) i 4 i x i 2 2i−1 i C i−1 2i−2 = = − ∞ i=1 − 2 i C i−1 2i−2 x i Подставив полученный результат в (3.55), получим F (x) = 1 − √ 1 − 4x 2x = ∞ i=1 2 x C i−1 2i−2 x i 2i = ∞ i=1 1 i C i−1 2i−2 x i−1 (3.56) Из (3.52) и (3.56) имеем F n = 1 n + 1 C n 2n (3.57) Полученная последовательность называется числами Катала- на и будем еще сталкиваться с ней. Скорость роста чисел в после- довательности (3.57) можно оценить следующим образом. Поль- зуясь формулой Стирлинга n! ≈ √ 2πn n e n ≈ n e n , имеем F n = 1 n + 1 C n 2n = 1 n + 1 (2n)! n!n! ≈ 1 n + 1 (2n) 2n n n n n = 1 n + 1 4 n ≈ 4 n Таким образом, получили, что количество бинарных деревьев с n вершинами экспоненциально растет с ростом n, и может оцени- ваться как O(4 n ). 109 3.3. Контрольные задачи 1. Найти общее решение уравнения F (n + 3) + (1/2)F (n + 2) + (1/2)F (n + 1) − (1/2)F (n) = n. 2. Найти решение уравнения при начальных условиях F (n + 2) − 2F (n + 1) + F (n) = n + 4, F (0) = 1, F (1) = 3. 3. Найти общее решение уравнения 15F (n+4)−4F (n+3)−6F (n+2)−4F (n+1)−F (n) = 3n−7. 4. Найти решение уравнения при начальных условиях F (n + 2) − 6F (n + 1) + 9F (n) = 4 · 3 n , F (0) = 1, F (n) = 4. 5. Найти общее решение уравнения F (n + 4) − 22F (n + 2) − 5F (n + 1) + 2F (n) = 3n 2 − n + 6. 6. Найти решение уравнения при начальных условиях F (n + 2) − 2F (n + 1) − 48F (n) = 3 · 2 3n−2 , F (0) = 1, F (1) = 3. 7. Найти общее решение уравнения F (n + 4) − 5F (n + 2) − 4F (n + 1) + 13F (n) = (1/2)n + 3. 8. Найти решение уравнения при начальных условиях 10F (n + 2) + 22F (n + 1) − 84F (n) = −6 · 4 n+1 , F (0) = 2, F (1) = 4. 110 9. Найти общее решение уравнения F (n+4)−F (n+3)−10F (n+2)+2F (n+1)+4F (n) = 11n 2 −3. 10. Найти решение уравнения при начальных условиях F (n + 2) − 2 √ 2F (n + 1) + 2F (n) = 4 · 2 n/2 , F (0) = 1, F (1) = 6. 11. Найти общее решение уравнения F (n + 3) − F (n + 1) − √ 2F (n) = (1/ √ 2)n 2 − n + 1. 12. Найти решение уравнения при начальных условиях 17F (n + 2) − 102F (n + 1) + 85F (n) = n, F (n) = 1, F (n) = 3. 13. Найти общее решение уравнения F (n+4)+4F (n+3)−2F (n+2)−12F (n+1)+9F (n) = 16n+13. 14. Найти решение уравнения при начальных условиях F (n + 4) − 7F (n + 3) + 14F (n + 2) − 7F (n + 1) − F (n) = 9, F (0) = 1, F (1) = 2, F (2) = 3, F (3) = 4. 15. Найти общее решение уравнения 4F (n+4)+20F (n+3)+15F (n+2)−45F (n+1)−54F (n) = 19. 16. Найти решение уравнения при начальных условиях 3F (n + 3) + 2F (n + 2) + 2F (n + 1) + 3F (n) = 6(−1) n , F (0) = 1, F (1) = −1, F (2) = 1. 111 17. Найти общее решение уравнения F (n + 4) − 8F (n + 1) + 63F (n) = −n + 6. 18. Найти решение уравнения при начальных условиях F (n + 4) − 8F (n + 2) + 16F (n) = 3 · 2 n−2 , F (0) = 1, F (1) = 3, F (2) = 3, F (3) = 3. 19. Найти общее решение уравнения F (n + 4) + 3F (n + 3) − 44F (n + 2)+ + 15F (n + 1) + 25F (n) = (1/2)n + 3. 20. Найти решение уравнения при начальных условиях F (n + 4) − F (n + 2) + 6F (n + 1) − 8F (n) = 3, F (0) = 2, F (1) = 4, F (2) = F (3) = 2. 21. Найти общее решение уравнения 2F (n + 4) − F (n + 3) + 3F (n + 2) − F (n + 1) + F (n) = n. 22. Найти решение уравнения при начальных условиях F (n + 2) − (7/3)F (n + 1) + (4/3)F (n) = 4n + 9, F (0) = 1, F (1) = 2. 23. Найти общее решение уравнения F (n+5)+F (n+4)+F (n+3)+F (n+2)+F (n+1)+F (n) = −n+2. 24. Найти решение уравнения при начальных условиях F (n + 2) − (7/3)F (n + 1) + (4/3)F (n) = (4/3) n−9 , F (0) = 1, F (1) = 3. 112 25. Найти общее решение уравнения F (n + 3) − 3F (n + 1) − (27 + 1/27)F (n) = 13. 26. Найти решение уравнения при начальных условиях F (n + 2) + 16F (n + 1) + 64F (n) = 7 · 4 n , F (0) = 2, F (1) = −1, 27. Найти общее решение уравнения F (n + 4) + 3F (n + 3) − 10F (n + 2) + F (n + 1) + F (n) = n − 15. 28. Найти решение уравнения при начальных условиях F (n + 2) − (6/9)F (n + 1) − (1/3)F (n) = n 2 + 9, F (0) = 1, F (1) = 2. 29. Найти общее решение уравнения F (n + 2) − (2 + 2 2)F (n + 1) + 2 √ 2F (n) = = (6 + 2( √ 2 + √ 3 + √ 6)) n/2 30. Найти решение уравнения при начальных условиях F (n + 4) + F (n + 3) − 10F (n + 2 + F (n + 1) + F (n) = 7, F (0) = 0, F (1) = F (2) = 1, F (3) = 2. 31. Найти общее решение уравнения F (n + 2) − 20F (n + 1) + 64F (n) = 2 · 4 n+3 32. Найти решение уравнения при начальных условиях F (n + 3) − F (n + 1) − √ 2F (n) = 1/ √ 2n 2 − n + 1, F (0) = 0, F (1) = F (2) = 1. 113 33. Найти общее решение уравнения F (n + 2) − 5F (n + 1) + 6F (n) = 3 · 2 n 34. Найти решение уравнения при начальных условиях F (n + 4) − F (n + 3) − 10F (n + 2) + 2F (n + 1) + 4F (n) = = 11n 2 − 3, F (0) = 0, F (1) = F (2) = F (3) = 1. 35. Найти общее решение уравнения F (n + 2) − 5F (n + 1) + 6F (n) = 3 · 2 n 36. Найти решение уравнения при начальных условиях F (n + 3) + (1/2)F (n + 2) + (1/2)F (n + 1) − (1/2)F (n) = n, F (0) = 1, F (1) = F (2) = 1. 114 4 . методы исчерпывающего поиска 4.1. Исчерпывающий поиск В этой главе рассмотрим задачи, для которых множество ре- шений конечно, и, следовательно, ответ может быть найден пе- ребором по всему множеству решений. Часто, однако, задача об- ладает некоторыми дополнительными ограничениями, что сужа- ет область возможных решений либо же эта область может быть сужена в процессе перебора, и некоторые, не удовлетворяющие ограничениям, множества решений могут быть отброшены (важ- но, что это может быть сделано не для конкретных решений, а для их множеств). В этом случае важно организовать перебор так, чтобы не рассматривать те решения (множества решений), которые заведомо не удовлетворяют ограничениям нашей задачи. Это позволяет сократить количество рассматриваемых решений, и, следовательно, сократить время, требуемое на поиск [5, 6, 8, 9]. Предположим, что решение задачи может быть описано набо- ром величин A = (a 1 , a 2 , . . . , a n ), при этом каждое a i принадлежит некоторому конечному множеству A i . Ясно, что множество A ко- нечно, и будем называть полным перебором способ нахождения решения, при котором рассматриваем каждый вектор из A, ясно, что в этом случае необходимо проанализировать |A 1 |·|A 2 |·. . .·|A n | векторов. Допустим теперь, что на некоторые из величин a i наложе- ны ограничения. Исчерпывающим поиском будем называть такой способ нахождения решения, при котором рассматриваются все решения из A, удовлетворяющие наложенным ограничениям. К примеру, ясно, что если для некоторого j соответствующая вели- чина a j не удовлетворяет наложенному на нее ограничению, то нет смысла для этого значения a j перебирать значения других величин a i , i = j. Продемонстрируем данный принцип на приме- рах. Задача 4.1 (задача о лабиринте). Лабиринт состоит из набора комнат, соединенных между собой дверями. Требуется найти путь из одной заданной комнаты лабиринта в другую. 115 N S W E 1 2 3 4 1 2 3 4 5 Рис. 4.1. Задача о лабиринте Решение. Для простоты предположим, что каждая комната в лабиринте имеет четыре стены (рис. 4.1). Для удобства перену- меруем комнаты, задав их координаты по горизонтали и по вер- тикали. Пометим стены как N (север), W (запад), S (юг) и E (восток). Таким образом, решением задачи можно считать после- довательность (a 1 , a 2 , . . . , a n ), где каждое из a i принимает значе- ния из множества {N, W, S, E}, а n — длина пути, вообще говоря, заранее неизвестная. На рис. 4.1 показан путь из левого нижнего угла лабиринта (комната с координатами 4,1 ) в правый верхний (комната с координатами 1,5 ). Это решение может быть записано как N EEN EN E. Заметим, что для выбранных начальной и конечной комнат это решение не единственно. Например, можно еще указать решения N ESEN N EN E или N EEN ESSEN N W N E. Наконец, заметим, что в некоторых стенах нет дверей — и это накладывает ограничения на нашу задачу. К примеру, каким бы ни было решение (a 1 , a 2 . . . , a n ) задачи, для указанных начальной и конечной комнат будем всегда иметь a 1 = N . Могут быть также наложены дополнительные ограничения — на длину пути, на чис- ло поворотов, количество посещений одной и той же комнаты и т.п. Предположив, что n — конечное число, во всех этих случаях 116 С а N S W E N W S E N W S E N W S E N W S E N N W S E N W S E N N W S E N N W S E N a 1 a 2 a 3 a n a n-1 Рис. 4.2. Общее дерево поиска для задачи о лабиринте решение может быть найдено перебором по всем возможным 4 n векторам (a 1 , a 2 , . . . , a n ). Для организации перебора представим возможные пути в ла- биринте на рис. 4.1 в виде дерева (рис. 4.2). Вершины этого дерева соответствуют некоторой комнате, ребра — переходу из комнаты в комнату через одну из дверей. В каждый момент времени, нахо- дясь в какой-то комнате, потенциально можем двигаться в четы- рех направлениях. Каждый следующий шаг дает следующее зна- чение a i . Таким образом, получаем четверичное дерево, и через n шагов имеем 4 n возможных путей в лабиринте. Однако заметим, что можно исключить из рассмотрения некоторые ребра, исхо- дящие из данной вершины, и следовательно — все поддеревья, являющиеся их потомками. Исключаемые ребра на рис. 4.2 пере- черкнуты, а поддеревья помечены пунктирными линиями. Далее, если вошли в комнату через некоторую дверь, то очевидно, что можно не рассматривать эту дверь как потенциальный выход — ребро для этого перехода уже существует в дереве. Наконец, заме- тим, что в какие-то моменты времени, следуя по разным путям, 117 41 31 32 22 21 11 12 42 43 33 23 13 24 14 15 25 35 34 44 45 Рис. 4.3. Граф поиска для задачи о лабиринте можно оказываться в одной и той же комнате. Таким образом, вершины нашего общего дерева, соответствующие одной комна- те, «склеиваются», образуя циклы, таким образом, вместо дерева можно рассматривать граф с меньшим числом вершин. Граф поиска для рассмотренного на рис. 4.1 примера изобра- жен на рис. 4.3. Индексы, которыми помечены вершины графа, соответствуют номеру комнаты (первая цифра — номер комна- ты по горизонтали, вторая — по вертикали). Рассматриваемый граф представляет все комнаты лабиринта, и все переходы меж- ду ними. Таким образом, задача поиска пути в лабиринте для любых начальной и конечной комнат может быть решена обхо- дом по этому графу (например, с помощью поиска в глубину или в ширину). Каждая комната представлена на графе ровно один раз, число дверей соответствует числу ребер. Циклы на графе со- ответствуют замкнутым путям по лабиринту, и могут быть учте- ны для предотвращения бесконечных блужданий в лабиринте «по кругу». Таким образом, вместо дерева с числом вершин, растущих как степень 4 с ростом длины пути, получаем некоторую замкнутую структуру, пользуясь которой, все равно нужно делать обход по ее вершинам, но число переходов при этом может быть сокращено. В рассмотренном примере для осуществления перебора по- строили дерево поиска, и затем применили к этому дереву два 118 важных приема: ограничение, слияние. Таким образом, сократили обход по дереву путем отбрасыва- ния некоторых поддеревьев, и объединения некоторых вершин. В задаче о лабиринте эти две операции носили очевидный и до- вольно естественный характер, в других задачах проблемой мо- жет быть само построение дерева поиска таким образом, чтобы операции ограничения и слияния давали наилучший эффект, од- нако общий принцип в решении таких задач остается прежним. Рассмотрим еще один пример. Задача 4.2 (задача о ферзях ). На шахматной доске размера n × n разместить как можно больше ферзей, не атакующих друг друга. Решение. Вспомним, что ферзь атакует все клетки на одной с ним горизонтали, вертикали и диагонали (рис. 4.4). Это означает, что число ферзей не может превышать n. Количество способов расстановки n ферзей по n 2 клеткам доски составляет C n n 2 . Для случая n = 8 это дает 4426165368 возможных решений, что со- ставляет примерно 4 · 10 9 Далее учтем, что в каждом столбце может стоять не более одного ферзя. Поэтому будем представлять вектор решений (a 1 , . . ., a n ) следующим образом: величина a i будет задавать номер клетки по горизонтали в i-й вертикали. Таким образом, i = 1, n, и a i ∈ {1, 2, . . . , n}. Это дает нам n n возможных решений. Для 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Рис. 4.4. Задача о ферзях 119 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Рис. 4.5. Решения задачи о ферзях случая n = 8 это число равно 16777216 или приблизительно 10 7 , т.е. приняв во внимание одно ограничение из условия задачи, на два порядка снижаем количество решений, которые необходимо рассмотреть. Аналогично, в каждой строке доски может стоять не более одного ферзя. Это означает, что вектор (a 1 , . . . , a n ) не может со- держать одинаковых значений, a i = a j при i = j, и следовательно, всякое допустимое решение является перестановкой чисел от 1 до n. В этом случае необходимо рассмотреть n! решений, что при n = 8 дает 40320 ≈ 4 · 10 4 Наконец, более одного ферзя не может стоять на одной диа- гонали, это обеспечивается ограничением |a i − a j | = |i − j|, для всяких i = j. Это ограничение сужает область поиска до 2056 вариантов для n = 8. Рассмотренные ограничения позволяют исключить из рассмот- рения подавляющее большинство вершин в дереве поиска. Однако 120 можно еще более сузить множество перебираемых решений, при- менив принцип слияния. Слияние вершин в дереве поиска озна- чает решения, некоторым образом эквивалентные между собой. В данном случае такими эквивалентными решениями можно счи- тать те, которые получаются друг из друга поворотами шахмат- ной доски, или ее отображением относительно какой-либо оси сим- метрии. Например, рассмотрим решения с a 1 = 1 (ферзь находит- ся в левом верхнем углу доски). Очевидно, в данном случае ферзь бьет все остальные углы, и они должны быть пустыми. Другими словами, ферзь может занимать не более одной угловой клетки. Это означает, что, какое бы решение ни получили, его всегда мож- но с помощью поворота доски привести к случаю, когда a 1 = 1, т.е. случай a 1 = 1 можно исключить из рассмотрения, введя до- полнительное ограничение a 1 ≥ 2. Далее можно заметить, что для любого решения с a 1 > n/2 можно получить эквивалентное ему решение с a 1 ≤ n/2 с помо- щью отражения доски относительно горизонтальной линии сим- метрии. Это сужает область выбора a 1 до диапазона a 1 ∈ {2, . . ., n/2 }. Для случая n = 8, с учетом всех рассмотренных ранее ограничений, это сокращает область перебора до 801 варианта. Таким образом, применением к полному дереву поиска прин- ципов ограничения и склеивания удалось снизить множество рас- сматриваемых вариантов с величины девятого порядка (для доски размером 8 × 8) до менее чем тысячи. С помощью вычислитель- ной машины перебор нескольких сотен вариантов может быть вы- полнен за доли секунды. Несколько примеров решения задачи о ферзях приведены на рис. 4.5. 4.2. Динамическое программирование В этом подразделе опишем один из подходов к реализации ис- черпывающего поиска, заключающийся в декомпозиции исходной задачи на несколько подзадач и называемый динамическим про- граммированием. Метод динамического программирования при- меняется в задачах оптимизации, где есть некая целевая функция и нужно найти ее минимум или максимум. Идею подхода мож- 121 но описать как разбиение задачи на этапы, подзадачи меньшей размерности, и следовательно, меньшей сложности. Это разбие- ние должно быть проведено таким образом, чтобы оптимизация каждого этапа вела к оптимизации задачи в целом. Далее жела- тельным является нахождение таких подзадач, которые могли бы использоваться несколько раз при решении общей задачи, решив какую-либо подзадачу, полученное решение может использовать- ся в дальнейшем как уже решенная часть некоторой другой под- задачи [1, 2]. Принцип динамического программирования часто представ- ляют с помощью следующей графической интерпретации. Пусть есть граф, в котором нужно найти кратчайший путь между двумя вершинами A и B. Далее, пусть все пути между этими двумя вер- шинами проходят через некоторую промежуточную вершину C. Подобный граф изображен на рис. 4.6. Предположив, что каждо- му ребру приписана некоторая стоимость, под кратчайшим путем будем понимать путь с наименьшей стоимостью. Как видно из рис. 4.6, есть 7 путей, ведущих из вершины A в вершину C, и 5 путей, ведущих из C в B. Таким образом, попытка решить задачу полным перебором приведет к рассмотрению 7 · 5 = 35 путей из A в B. В то же время, очевидно, что оптимальный путь из A в B может быть получен с помощью нахождения оптимального пути из A в C (перебор по 7 путям), и оптимального пути из C в B (пе- ребор по 5 путям), что дает нам в общем рассмотрение 7 + 5 = 12 путей. В более общем случае принцип динамического программиро- вания можно также представить рис. 4.7. Выделение узлов C, D, E, F как раз и соответствует разбиению общей задачи (по- |