Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
1 2 3 4 5 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5 5 5 5 5 5 6 5 5 5 5 5 7 5 7 7 7 7 8 5 7 7 7 7 9 5 7 9 9 9 10 11 12 5 7 9 9 9 5 7 9 11 11 5 12 12 12 12 13 14 15 16 17 18 19 5 12 12 12 12 5 12 14 14 14 5 12 14 14 14 5 12 16 16 16 5 12 16 16 16 5 12 16 18 18 5 12 16 18 18 Для заполнения текущей строки достаточно знать только предыдущую строку (результат решения задачи меньшей на единицу размерности), а в элементе массива A[i,j] записывает- ся решение задачи о камнях при N—i и W=j. Программный код решения компактен и не требует пояснений. Procedure Solve; Var Begin For To N Do For To Do Begin If Then A[i,j]:= Max (A[i-l A[i-l,j-P[i]]+P[i]) Else End; End; Для ответа на вопрос, «из каких камней набирается вес», решение необходимо дополнить простой рекурсивной процеду- рой. В курсивом выделена часть элементов, задейство- ванных при работе процедуры, а жирным шрифтом те значе- ния i и при которых осуществляется вывод веса камня P[i]• Procedure Begin If And Then Exit Else If i=l Then Begin Way (i ) ; Else If Then Begin Way(i,j-P[i]) ;Write(P[i] ') ;End Else Way(i-l,j) ; End; Пример 6 — «Задача о рюкзаке (к весу камней добавляется и их стоимость)». Напомним формулировку задачи. В рюкзак загружаются предметы N различных типов (количество пред- метов каждого типа не ограничено). Вес рюкзака должен быть меньше или равен W. Каждый предмет типа i имеет вес и 102 3. Перебор и методы его сокращения 3. Перебор и методы его сокращения 103 стоимость (£=1,2, ..., N). Требуется определить максималь- ную стоимость груза, вес которого не превышает W. Рассмот- рим случай, когда вес рюкзака в точности равен W. Обозначим количество предметов типа i через тогда требуется максими- зировать при ограничениях где — целые квадратные скобки означают це- лую часть числа. Формализуем задачу следующим образом. Шаг i ставится в соответствие типу предмета Состояние на шаге i выражает суммарный вес предметов, решение о загрузке кото- рых принято на шагах При этом при i=l,2,...,N—l. на шаге описываются количеством предметов типа i, Уточним идею на конкретных данных. Пусть и дано четыре предмета: 1 2 3 4 2 3 1 4 50 90 30 140 Схема работы для данного примера приведена на рисунке. В кружочках выделены только достижимые состояния (суммар- ные веса для каждого шага в соответствии с приведенной выше 104 Перебор и методы его формализацией) на каждом шаге. В круглых скобках указаны стоимости соответствующих выборов, в квадратных скобках — максимальная стоимость данного заполнения рюкзака. «Жир- ными» линиями выделен способ наилучшей загрузки рюкзака. Текст решения. Const MaxN=???; МахК=???; Type End; Var .MaxN,0. Of Word; of Thing; Of N,W: Procedure Solve; Var Begin ,0) ; For k:=l To N Do Begin { *Цикл *} ,0); For i:=0 To N Do {*Цикл состояниям *} For j :=0 To i Div P[k] Do {*Цикл вариантам решения - количеству предметов каждого вида.*} If Begin NewA[i] :=j*P[k] [i-j *P [k] ; j количество End; End; End; Вывод наилучшего решения. Procedure Begin If k=0 Then Exit Else Begin ;{*A здесь вес. *} Write (A[k 1] ,' '); End; End; Первый вызов — Эту схему реализации при- нято называть «прямой прогонкой». Ее можно изменить. Пусть 3. Перебор и методы его сокращения 105 пункт два формализации задачи звучит следующим образом. Состояние на шаге выражает суммарный вес предметов, ре- шение о загрузке которых принято на шагах i, ..., N при этом при £=2,3, ...,N. В этой формулировке схему реализации называют «обратной прогонкой». 3.5. Метод ветвей и границ Идея метода ветвей и границ обычно излагается по работе Дж. Литтла. Не отступим и мы от этой традиции. Суть идеи проста. Все перебираемые варианты следует разбить на классы (блоки), сделать оценку снизу (при минимизации) для всех ре- шений из одного класса, и если она больше ранее полученной, то отбросить все варианты из этого класса. Весь вопрос в том, как разделять на классы. Пусть решается задача о коммивоя- жере (дана матрица расстояний — полный граф). Например, Если мы будем вычитать одно и то же число из всех элемен- тов строки или столбца, то суммарная стоимость пути комми- вояжера не изменится. При вычитании константы из элемен- Литтл Дж., Мурти К., Суини Д., Е. Я. Алгоритм решения задачи ком- мивояжера.//Экономика и математические методы. 1965. №1. 106 3. Перебор и методы его сокращения тов стоимость любого пути уменьшится на эту константу, ибо числа в строке соответствуют выезду из города, а выезд из этого города обязательно присутствует в пути. Точно так же и вычитание из элементов столбца — въезд в город. Вы- читаемая константа входит в оценку пути, но не рассматрива- ется дальше, после изменения матрицы. Найдем минимум в каждой строке и вычтем его. Получается матрица: Сумма вычитаемых констант равна 24. Аналогичную операцию выполним со столбцами: из элемен- тов первого вычитаем 2, а из элементов четвертого — 1. Итого- вая сумма — 27. Все пути коммивояжера уменьшились на это значение. Если получается выбор по одному нулю в каждом столбце и строке (они выделены курсивом в матрице), то тем самым мы получаем путь коммивояжера со стоимостью 27. Это путь С минимальной стоимостью, любой дру- гой путь имеет большую стоимость. Значение 27 — это оценка снизу всех маршрутов коммивояжера. В данном случае она до- стигается на конкретном маршруте. Очевидно, что мы просто очень удачно подобрали пример. Не обязательно после приведе- ния существование пути по ребрам с нулевой стоимостью. Про- должим рассмотрение. Пусть дана другая матрица расстояний. 3. Перебор и методы его сокращения 107 После приведения по строкам и столбцам (сумма констант приведения равна 14) получаем следующую матрицу: Выделенные курсивом нули дают путь, но это не путь коммивояжера. Его вид показан на рисунке. Наши да- льнейшие действия (шаг ветвления). Рассмотрим нули в приведенной мат- рице, именно нуль в позиции (1, 2). Он, естественно, означает, что стоимость переезда из первого во второй город равна нулю. Однако если исключить (запретить) переезд из первого во второй город, то въезжать во второй город все равно придется. Цены въезда указаны во втором столбце — въезжать из третьего города дешевле всего. Так как выезжать из первого города нам когда-либо придется, то дешевле всего выехать в третий город — нулевая стоимость. Вычисляем сумму этих минимумов, она равна 1+0=1. Суть этой единицы в том, если не ехать из первого города во второй, то придется за- платить не менее Эта оценка нуля указана в матрице верхним индексом. Сделаем оценки всех нулей и выберем элемент с мак- симальной оценкой. Если таких нулей несколько, то выбираем любой. Итак, в чем суть ветвления. Все маршруты коммивояже- ра разбиваются на два класса, содержащих ребро (1,2) и не со- держащих ребро (1,2). Для последнего класса оценка снизу уве- личивается на единицу, т. е. равна 15. Для маршрутов из первого класса продолжаем работать с матрицей. Исключаем (вычеркиваем) первую строку и второй столбец. Кроме того, в уменьшенной матрице на место (2,1) следует поставить прочерк, означающий невозможность соответствующего переезда. После этих манипуляций матрица примет следующий вид 108 3. Перебор и методы его сокращения Продолжим наши действия по оценке маршрутов из первого класса. Сокращенную матрицу, к сожалению, приводить нель- зя — минимальные элементы во всех строках и столбцах равны нулю. Таким образом, оценка снизу для класса маршрутов, со- держащих (1,2), остается равной 14. С сокращенной матрицей выполним аналогичные действия — оценим нули, выберем нуль, соответствующий переезду из третьего города в первый. Суть действий в разбивке этого класса маршрутов на подклас- сы по той же самой схеме — с (3,1) и без (3,1). Для второго под- класса оценка снизу 14+5=19. С пер- вым подклассом аналогичные действия — исключаем столбец и строку, на место (2,3) в таблице пи- шем запрет на перемещение. Матри- ца допускает операцию приведения. Вычитаем единицу из элементов пер- вой строки и первого столбца. Ниж- няя оценка маршрутов этого подкласса возрастает на два, итого 14+2=16. Следующий шаг приводит к матрице еще меньшего размера. Весь процесс работы по рассматрива- емой схеме представлен на рисунке. Вершины этого дерева представляют классы решений. Черта над цифрами означает, что соответствующий класс не содержит какой-то конкретный переезд из города в город. Числа у вершин дерева означают оценки снизу для маршрутов из данного класса. Итак, получе- на первая оценка — 16 для маршрута Все подклассы ре- шений, у которых оценка снизу больше или равна 16, исключаются из рассмотре- ния — очевидный факт после изложения схемы решения. Остался только подкласс без переезда из первого города во второй, его оценка равна 15. Однако после первого же ветвления полу- чаются подклассы с оценками 16 и 17. Обработку можно закан- чивать. Найден наилучший маршрут коммивояжера, стоимость проезда по этому маршруту равна 16. Программная реализация метода ветвей и границ — хоро- шая проверка техники программирования (структурного стиля самого процесса написания программы). Что лучше? Или рабо- тать с матрицами различной размерности, или вводить допол- 3. Перебор и методы его сокращения нительные структуры для хране- ния исключенных номеров строк и столбцов. Вопросы можно про- должить. Ответ даст эксперимент с различными версиями про- грамм реализации логики. В п. 3.2.2 рассмотрена одна схема решения задачи коммиво- яжера, в данном пункте — дру- гая. В чем их отличие для раз- личных значений размерности задачи N? По некоторым оцен- кам, с помощью метода ветвей и границ можно решать задачи с iV<100. 3.6. Метод «решета» Идея метода. Решето представляет собой метод комбинатор- ного программирования, который рассматривает конечное мно- жество и исключает все элементы этого множества, не пред- ставляющие интереса. Он является логическим дополнением к процессу поиска с возвратом (backtrack), в котором мы пытаем- ся постепенно перечислить все возможные варианты решения. В решете идут от обратного — от всего множества решений за- дачи. Решето Эратосфена. Эратосфен — греческий математик, 275-194 гг. до нашей эры. Классическая задача поиска простых чисел в интервале [2..N] — инструмент для обсуждения метода. Объяснение строится на основе следующего рисунка и фрагмен- та 2 3 4 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 2 3 4 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 Числа, выделенные «жирным» шрифтом, отбрасы- ваются. 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 Числа, выделенные курсивом, отбрасываются. Const N= ...; граница интервала чисел. *} Type Of 2. .N; {решето, N<256} Var 110 3. Перебор и методы его сокращения Procedure Search (Var Var Begin S: = [2. ; For i:=2 To N Div 2 Do If i In S Then Begin j : =i +i ; Do Begin ;j End; End; End; Логическим развитием задачи является ее решение при N больших 256. В этом случае необходимо ввести массив с мно- жественным типом данных элементов. «Быки и Компьютер и ребенок играют в следую- щую игру. Ребенок загадывает последовательность из четырех (не обязательно различных) цветов, выбранных из шести задан- ных. Для удобства будем обозначать цвета цифрами от 1 до 6. Компьютер должен отгадать последовательность, используя ин- формацию, которую он получает из ответов ребенка. Компьютер отображает на экране последовательность, а ре- бенок должен ответить (используя для ввода ответа клавиату- ру) на два вопроса: • сколько правильных цветов на неправильных местах; • сколько правильных цветов на правильных местах. Пример. Предположим, что ре- бенок загадал последовательность 4655. Один из возможных способов отгадать последовательность та- кой: Написать программу, которая всегда отгадывает последователь- ность не более чем за шесть вопро- сов, в худшем случае — за десять. Правильный выбор структур данных — это уже половина решения. Итак, структуры данных и процедура их инициали- зации. Const Type Var Of Post; Of Boolean; 1234 5156 6165 5625 5653 4655 Ответ ребенка 1 2 2 1 1 0 0 1 1 2 2 4 Модификация задачи Антона Александровича Суханова. 3. Перебор и методы его сокращения 111 числа ходов.*} - решение найдено. *} Procedure Var Begin For To 6 Do For To 6 Do For To 6 Do For To 6 Do A[ *36+(k-l) *6+l] ; = Chr (i +Chr (j ('' 0')) + ) ; For i:=l Do В [i ] End; Поясним на примере идею решета. Пусть длина последовате- льности равна двум, а количество цветов — четырем. Ребенок загадал 32, а компьютер спросил 24. Ответ ребенка 1 0, фикси- руем его в переменных (1) и А 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 В True True True True True True True True True True True True True True True True В (после анализа False False False False False False False В (после анализа kr) False False False False False Результат False True False False False False False False False True False False True False True False Итак, было 16 возможных вариантов, после первого оста- лось четыре — работа решета. Функция, реализующая анализ элемента массива А по значениям переменных kr и bk, имеет вид: 112 Перебор и методы его сокращения Function -.Boolean; Var Begin {*Проверка "быкам".*} For i:=l To 4 Do If Then Inc(x) ; If Then Begin {*Проверка "коровам". *} For i:=l To 4 Do If (a[i]ob[i]) And (Pos (b[i] <>0) Then Inc(x) ; If Then Begin Pr:=True; End; Логика — «сделать отсечение» значению хода h. Procedure Var Begin Inc(cnt) . ' If bk=4 Then Begin ok: результата>;End Else For To Do If B[i] And Not Pr(A[i] h,kr,bk) Then End; Общая логика. Begin ClrScr; While Not ok Do Begin \ выбор очередного хода из А Hod(h); End; End. Дальнейшая работа с задачей требует ответа на следующие вопросы: • Зависит ли значение cnt от выбора первого хода? Устано- вить экспериментальным путем. • Как логика выбора очередного хода влияет на результат игры? Исследовать. Например, выбрать тот элемент А (со- Перебор и методы его сокращения 113 ответствующий элемент должен быть равен True), в ко- тором количество несовпадающих цифр максимально. Примечание Рассмотренные задачи носят учебный характер. Обычно идеи мето- да решета используются в совокупности с другими методами. 3.7. Задачи Задача о парламенте*. На острове Новой Демократии каж- дый из жителей организовал партию, которую сам и возглавил. Любой из жителей острова может состоять не только в своей партии, но и в других партиях. К всеобщему удивлению, даже в самой малочисленной партии оказалось не менее двух чело- век. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предполагалось по Конститу- ции острова, президенты всех партий. Посовещавшись, остро- витяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите островитянам организовать такой, как можно бо- лее малочисленный парламент, в котором будут представлены все партии. Исходные данные: каждая партия и ее президент имеют один и тот же порядковый номер от 1 до N (4 Например, для четырех партий: Список членов парламента 2 состоит из одного жителя с номе- ром 2. Указание. Задача относится к классу iVP-полных задач. Ее решение — полный перебор всех вариантов. Начиная с подмно- жеств мощности 1, требуется генерировать все возможные под- множества множества жителей (до подмножеств мощности N Div 2) и заканчивать процесс в том случае, когда будет найдено решение для подмножеств определенной мощности. Покажем, что ряд эвристик позволяет сократить перебор для некоторых наборов исходных данных. Представим информацию о партиях и их членах с помощью следующего зрительного образа — таблицы. Номером строки Президенты 1 2 3 4 Члены партий 2,3,4 3 1,4,2 2 Межгосударственная олимпиада по информатике 1992 года, автор задачи Ю. 114 3. Перебор и методы его сокращения является номер партии, номером столбца — номер жителя. Для примера из формулировки задачи она имеет вид: Тогда задачу можно переформу- лировать следующим образом. Найти минимальное число столб- цов, таких, что множество единиц из них «покрывает» множество всех строк. Очевидно, что для при- мера это один столбец — второй. Рассмотрим еще один пример. Из первоначальной таблицы можно исключить третий столбец, соответствующий третьему жителю, — множество партий, в которых он состоит, содержится в множестве партий, в кото- рых состоит второй житель. После сокращения таблицы могут появиться строки с одной единицей (партия представлена од- ним жителем). Таких жителей необходимо включать в парла- мент. Включаем второго жителя. После этого останется пред- ставить в парламенте только четвертую партию. Итак: • во-первых, требуется проверять, есть ли житель, пред- ставляющий все множество не представленных в парла- менте партий; • во-вторых, исключать часть жителей из рассмотрения, если есть жители, представляющие большее количество партий, и это множество партий содержит партии исклю- чаемого жителя; • в-третьих, если в результате предыдущей операции появ- ляются партии, представленные одним жителем, то этих жителей обязательно требуется включать в парламент. Вывод: перебор следует выполнять не по всем жителям и не для всех партий. Второе и третье действия необходимо выпол- нить до момента начала перебора вариантов (предварительная обработка) и только затем выполнять схему перебора. Первое действие должно выполняться как на стадии предварительной обработки, так и в процессе перебора. Общая схема перебора реализуется как обычно. Приведем часть описания данных для того, чтобы она была понятна. |