Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
x g x 1 x 2 x 3 x g k k k k m m m x x g -1 k а) ) kg m / Рис. 1.2. Представления вектора x в ячейках памяти 13 Выбор способа представления данных, однако, может осуществ- ляться не только в зависимости от того, что нам важнее в данной реализации: минимально используемая память или максимально короткое время выполнения. Этот выбор может зависеть и от то- го, какие именно операции нам необходимо совершать. Возможно эти операции можно эффективно выполнять и с данными, пред- ставленными в компактной форме, без извлечения их из общего массива m-ячеек. В качестве примера такой оптимизации опера- ций рассмотрим следующую задачу. Задача 1.2 . Пусть даны два вектора: x = (x 1 , . . . , x g ), y = (y 1 , . . . , y g ), где x i , y i ∈ {0, . . . , N − 1}. Необходимо определить, выполняется ли неравенство g i=1 |x i − y i | ≤ t, (1.5) где t — некоторое неотрицательное целое число. Выражение (1.5) может быть использовано, например для оцен- ки похожести наборов x и y. Вычисление суммы в (1.5) с уче- том размещения элементов x i и y i в отдельных ячейках состоит из g m-битных вычитаний, и временная сложность может быть оценена как O(mg) (битовых операций). В случае компактного представления векторов временная сложность будет выше за счет необходимости дополнительных битовых операций. Каким обра- зом можно уменьшить временную сложность вычисления (1.5) при компактном представлении? Для этого введем в рассмотрение понятие кодов, сохраняющих разности. Определение 1.3 Расстоянием Хэмминга d(x, y) между двумя векторами x = (x 1 , . . ., x n ) и y = (y 1 , . . . , y n ) назовем число позиций, в которых эти векторы не совпадают. Определение 1.4 Весом Хэмминга W (x) назовем число ненулевых позиций век- тора x. 14 Из определений 1.3 и 1.4 очевидно, что d(x, y) = W (x − y). (1.6) Определение 1.5 Назовем (N, n, t)-кодом, сохраняющим разности, такое отоб- ражение множества целых чисел i ∈ {0, . . . , N − 1} в двоичные векторы {a i } длины n, для которого 1. d(a i , a j ) = |i − j|, если |i − j| ≤ t, 2. d(a i , a j ) > t, если |i − j| > t. Пример (8,4,1)-кода, сохраняющего разности, приведен в сле- дующей таблице: i 10 i 2 a i 0 000 0000 1 001 0001 2 010 0011 3 011 0111 4 100 0110 5 101 1110 6 110 1100 7 111 1101 Как можно использовать код, сохраняющий разности, для реше- ния нашей задачи? Будем хранить в памяти (компактно) не дво- ичные представления i 2 десятичных чисел i 10 , а соответствующее кодовое слово a i . Тогда для хранения потребуется O(ng/m) ячеек памяти. В этом случае оценка неравенства (1.5) может быть эф- фективно получена следующим образом. Вычислим W (x ⊕ y), где x и y представлены описанным способом с помощью кода, сохра- няющего разности, ⊕ — означает операцию побитового исключа- ющего ИЛИ (операция XOR), W (·) — хэммингов вес полученной суммы. Обозначим десятичное значение элементов {x i } вектора x через {x (10) i }, а их представление в коде, сохраняющем разности 15 — через {x (a) i }. Тогда с учетом (1.6) W (x ⊕ y) = g i=1 W (x (a) i ⊕ y (a) i ) = g i=1 d(x (a) i , y (a) i ). Расстояние d(x (a) i , y (a) i ) в точности равно |x (10) i − y (10) i |, если аб- солютное значение этой разности не превышает t и больше t в противном случае. Отсюда следует, что неравенство (1.5) выпол- няется тогда и только тогда, когда выполняется неравенство W (x ⊕ y) ≤ t. (1.7) Приведем пример. Пусть x = (1, 2, 3, 4), y = (1, 2, 3, 5), t = 1. Очевидно, неравенство (1.5) выполняется. Представление векто- ров x, y с помощью кодов, сохраняющих разности x = (0001|0011|0111|0110), y = (0001|0011|0111|1110). Тогда x ⊕ y = (0000|0000|0000|1000), W (x ⊕ y) = 1 ≤ t, и неравенство (1.5) также выполняется с учетом (1.7). Теперь, пусть y = (1, 2, 5, 3). Тогда неравенство (1.5) не выпол- няется, а вычисление (1.7) дает x ⊕ y = (0000|0000|1001|0001), W (x ⊕ y) = 3 > t, и неравенство (1.7) также не выполнено. Таким образом, заменили представление элементов векторов x и y, и нашли способ вычислять неравенство (1.5) в этом но- вом представлении. Заметим, что при вычислении (1.7) не нужно выделять отдельные элементы векторов, сложение (XOR) может 16 быть осуществлено сложением m-битных ячеек памяти. Для вы- числения веса Хэмминга может быть использован алгоритм с ло- гарифмической сложностью, описанный в подразд. 1.1. Тогда, вы- числение неравенства (1.5) требует O(ng/m) ячеек памяти, O(ng) битовых операций для вычисления x ⊕ y, и O(log ng) операций для вычисления веса, т.е. общая временная сложность составит O(ng+log ng) ∼ O(ng). Выигрыш во времени по сравнению с базо- вой схемой вычисления (которая давала сложность O(mg)) будет достигаться в случае, если n < m. Описанный способ представле- ния позволяет экономно хранить информацию, сохраняя возмож- ность осуществлять эффективные операции с данными. 17 2 . методы построения алгоритмов 2.1. Этапы построения алгоритмов В этом разделе рассмотрим основные этапы построения ал- горитмов, задачи, которые последовательно возникают при раз- работке практически любого алгоритма и требуют своего реше- ния [4, 9]. Некоторые из этих этапов будут подробнее затрону- ты в учебном пособии. В зависимости от конкретных требований какие-то шаги при построении алгоритма для решения той или иной практической задачи могут быть опущены, дополнены, или акцентированы особо. Рассмотрим основные этапы построения ал- горитма на примере известной оптимизационной задачи, которую обычно называют задачей коммивояжера. Задача 2.1 (задача коммивояжера). Коммивояжеру для со- вершения торговых сделок требуется объехать n городов и вер- нуться в свой родной город, при этом в каждом городе он может побывать только один раз. Среди множества возможных маршру- тов требуется найти тот, который позволит минимизировать за- траты на поездку. Для нахождения решения задачи необходимо будет пройти следующие этапы. 1. Формулировка задачи В общем, «словесном» виде уже сформулировано условие за- дачи 2.1 . Однако в каждой задаче может потребоваться сформу- лировать необходимые и/или дополнительные условия и ограни- чения, а также возможные допущения. В нашем примере можно сформулировать несколько таких дополнительных условий и до- пущений: используемое понятие стоимости должно быть формализо- вано, предположим, что для каждой пары городов a и b за- дана функция стоимости C : (a, b) → c, c ≥ 0, т.е. каждой паре городов ставится в соответствие неотрицательное число (стоимость) c (это может быть время, затраченное на проезд, стоимость билета, расстояние между городами и т.п.); 18 допустим, что функция стоимости учитывает направление нашего движения, т.е. в общем случае C(a, b) не обязательно должно быть равно C(b, a); будем считать C(a, a) = ∞, т.е. запретим «вырожденный» переезд из города в этот же город; наконец, будем считать, что спрос на товары коммивояжера во всех городах одинаков, и единственное, чем определяют- ся его предпочтения при выборе маршрута — это функция стоимости C. Пусть расстояния (стоимости переездов) между городами за- даны табл. 2.1 (для простоты будем рассматривать симметричный случай C(a, b) = C(b, a), т.е. стоимость переезда из города в город не зависит от направления переезда). 2. Построение математической модели Теперь имеем формулировку задачи, и можем попробовать найти подходящую модель для описания нашей задачи. Смысл этого действия состоит, с одной стороны, в том, чтобы привлечь для решения задачи тот аппарат, который присущ данной моде- ли, а с другой — возможность использовать в решении уже извест- ные для данной математической модели приемы и способы нахож- дения требуемых результатов. В нашем примере можно описать сеть из n городов как полносвязный взвешенный ориентирован- ный граф (орграф), т.е. множество из n вершин, каждая из ко- торых связана с любой другой ребром, при этом каждому ребру приписано направление движения и стоимость переезда (рис. 2.1). Такой граф можно представить (n × n)-матрицей смежности C, в Таблица 2.1. Таблица стоимостей для задачи коммивояжера A B C D A ∞ 10 1 3 B 10 ∞ 5 6 C 1 5 ∞ 7 D 3 6 7 ∞ 19 i 1 j n c ij c ji Рис. 2.1. Полносвязный орграф A B C D 10 1 6 7 5 3 Рис. 2.2. Граф стоимостей которой каждая ячейка c i,j содержит стоимость переезда из горо- да i в город j. Граф является стандартным представлением мно- жества объектов и связей между ними, существует множество за- дач и алгоритмов на графах. Для нашего примера представление маршрутов и городов в виде графа дает возможность формали- зовать решение задачи как поиск определенного пути в графе, удовлетворяющего некоторым условиям. Граф, соответствующий табл. 2.1, приведен на рис. 2.2 (так как выбрана матрица стои- мости, симметричная относительно главной диагонали, получен неориентированный граф). Тогда, перенумеровав города целыми числами от 1 до n, можно задать объезд как последовательность чисел, соответствующую порядку посещаемых городов, при этом каждое число от 1 до n должно присутствовать в этой последовательности ровно один раз. Проще говоря, удовлетворяющий условию задачи объезд за- дается перестановкой целых чисел π = {j 1 , . . . , j n }, j i ∈ {1, . . . , n}. 20 Каждому объезду π можем поставить в соответствие функцию стоимости C(π) = c j 1 j 2 + c j 2 j 3 + . . . + c j n−1 j n + c j n j 1 , где c ij — элементы матрицы смежности C. Тогда искомое решение можно записать как π ∗ : C(π ∗ ) = min π {C(π)}. 3. Выбор или построение алгоритма На этом этапе должен быть произведен выбор одного из воз- можных известных алгоритмов решения данной задачи (наиболее подходящий по какому-то критерию), предложены модификации известных алгоритмов, либо же найдены новые алгоритмы. С точ- ки зрения построения алгоритма данный этап кажется основным, и часто под этим этапом и понимают собственно решение зада- чи. Однако это не совсем верно, так как успешно выполненные начальные этапы могут значительно упростить нахождение алго- ритма, а последующие этапы являются необходимыми для оценки его качества. В нашем случае наиболее очевидным и прямым методом на- хождения минимального объезда может быть полный перебор всех возможных маршрутов. Так как любой объезд представляет за- мкнутый цикл, то первый город, с которого начинаем маршрут, можно зафиксировать, и тогда всего существует (n − 1)! различ- ных маршрутов. Для каждого из них можно вычислить его сто- имость и выбрать маршрут, обеспечивающий минимальную стои- мость объезда. Для 4-x городов из матрицы стоимостей на табл. 2.1 существу- ет 3! = 6 объездов (предполагаем, что любой объезд начинается из города A и заканчивается там же). Эти объезды и их стоимо- сти изображены в табл. 2.2. Так как в рассматриваемом примере стоимость проезда между двумя любыми городами одинакова вне зависимости от направления движения, все объезды разбивают- ся на пары маршрутов с одинаковой стоимостью, различающих- 21 Таблица 2.2. Маршруты и их стоимости № π C(π) 1 A|BCD|A 25 2 A|BDC|A 24 3 A|CBD|A 15 4 A|CDB|A 24 5 A|DBC|A 15 6 A|DCB|A 25 ся лишь направлением объезда. Кратчайшие объезды ACBDA и ADBCA дают минимальную стоимость 15. 4. Проверка корректности алгоритма Для любого предложенного алгоритма должна быть показа- на его корректность, т.е. доказано, что при любых входных зна- чениях задачи алгоритм завершится, и полученный ответ будет соответствовать требуемому в условии задачи. Так как в каче- стве метода решения в предыдущем пункте предложили полный перебор всех вариантов, и число этих вариантов конечно, то это может служить гарантией того, что задача всегда будет решена, и решена корректно. 5. Анализ сложности алгоритма Проверив, что алгоритм корректен и всегда дает правильное решение задачи, следующим шагом является анализ трудоемко- сти алгоритма. Напомним, что оценка сложности производится как по числу операций (в среднем или в худшем случае), так и по объему требуемой памяти. В нашей задаче всего существует (n−1)! маршрутов, их можно генерировать динамически или хра- нить в памяти, в любом из этих вариантов сложность нахожде- ния полного перебора задается функцией O(n!), что эквивалентно (с учетом известных формул Стирлинга) экспоненциальному по- рядку сложности. Вдобавок, нужно хранить матрицу стоимостей из n 2 ячеек. Таким образом, предложенный алгоритм приемлем лишь при малых значениях n (порядка двух-трех десятков), так как экспоненциальная функция растет чрезвычайно быстро. 22 6. Реализация алгоритма На практике, кроме разработки алгоритма, требуется и его программная или в некоторых случаях аппаратная реализация. Как правило, каждый алгоритм может быть реализован различ- ными способами, более или менее эффективными в зависимости от самого алгоритма, условий реализации (язык программирова- ния, операционная система, элементная база для аппаратной ре- ализации, тип процессора и т.д.), квалификации программиста. Конкретная реализация может быть «заточена» под конкретные требования или ограничения по памяти или времени выполнения. Если рассматриваем просто некую «среднюю» реализацию без специфических требований и ограничений, то в нашем примере для этого достаточно уметь представлять абстрактные типы дан- ных, такие, как граф, и генерировать перестановки. И то, и дру- гое имеет свои известные способы и методы реализации. Таким образом, при реализации одного алгоритма может потребоваться и знание вопросов реализации других алгоритмов. 7. Проверка корректности программы Задача проверки корректности, или тестирование, является самостоятельной большой задачей, которой в теории алгоритмов уделяется большое внимание. Задача эта не является простой, на практике практически никогда нельзя гарантировать корректную работу сложных программ — речь идет лишь о корректной работе в определенных условиях и в заданном диапазоне входных дан- ных. Существуют методики и подходы к тестированию, к выбору и построению систем тестов. 8. Оценка сложности программы Время выполнения программы, занимаемая программой па- мять не всегда прямо зависят от сложности лежащего в основе алгоритма. Большое влияние оказывает реализация, а также ап- паратная платформа, на которой выполняется программа. Про- цессор, предназначенный, в первую очередь, для обработки целых чисел, как правило, хуже работает с вещественными и наоборот. Число шагов, которые выполняет программа, или число элемен- тов, требуемых для аппаратной реализации, сильно зависят от 23 самой реализации. Если речь идет о создании конечного продук- та, то вопросы сложности реализации выходят на первый план по сравнению со сложностью алгоритмов. Иногда бывает более выгодно реализовать «жадный» переборный алгоритм, чем более тонкий метод. Выбор и оценка алгоритмов и реализаций должны производиться здесь, исходя их конкретных требований и ограни- чений. 9. Документирование программы Шаг, который почти всегда игнорируется начинающими про- граммистами и при грамотном исполнении всегда ценится любы- ми пользователями или разработчиками программ. Через очень недолгое время после написания программы даже сам автор часто может не помнить всех деталей реализации. Если с программой должны работать сторонние пользователи, наличие четкого и яс- ного руководства по работе становится обязательным. Даже очень хорошо написанная программа может оказаться почти бесполез- ной в использовании и чрезвычайно трудной в модификации при отсутствии хорошего ее описания. Пп. 6–9 не будут рассматриваться в учебном пособии. Основ- ное внимание будет уделено пп. 3 и 5. 2.2. Методы частных целей, подъема вверх и отрабатывания назад Рассмотрим три основных подхода, которые могут быть ис- пользованы при разработке алгоритмов. Суть этих методов отра- жена в их названиях — это метод частных целей, подъема вверх и отрабатывания назад [4, 3]. Определение 2.1 Методом частных целей называется метод поиска решения, состоящий в разбиении задачи на подзадачи (установление част- ных целей), которые в совокупности дают решение исходной за- дачи. Определение 2.2 Методом подъема вверх называется метод поиска решения, 24 состоящий в последовательном (пошаговом) улучшении некоторо- го начального решения. Определение 2.3 Методом отрабатывания назад называется метод поиска ре- шения, основанный на предположении, что задача уже решена, и состоящий в последовательном определении условий, при кото- рых это решение может быть получено. Введенные определения являются довольно общими, но они не дают собственно решения задачи, а только формулируют подхо- ды к поиску этого решения. Для некоторой задачи может быть использован какой-то один подход или их комбинация. В каче- стве примера применения описанных подходов рассмотрим сле- дующую задачу. Задача 2.2 (задача о джипе). Путешественник пересекает на джипе пустыню шириной в 1000 км, расходуя по 1 л на каждый километр пути. Однако бак джипа рассчитан только на 500 л. Пу- тешественник может делать запасы бензина, завозя его в пусты- ню на некоторое расстояние, и возвращаясь назад на дозаправку. Необходимо пересечь пустыню с минимальными затратами топ- лива. Решение. На самом деле, не сразу понятно, что задача во- обще имеет решение. Выработаем определенную стратегию дей- ствий и посмотрим, к чему она приведет. Так как нельзя пересечь пустыню за один раз, необходимо заезжать на какое-то расстояние вглубь, оставлять там некоторое количество топлива так, чтобы в баке еще оставалось достаточно бензина для возвращения. Кур- сируя туда-назад и завозя все больше топлива в глубь пустыни, можно двигаться дальше, в следующий раз возвращаясь уже не к началу пути, а к предыдущему хранилищу. Таким образом, наш путь в 1000 км разбивается на дистанции x 1 , x 2 , . . . , x k , в конце которых расположены временные хранилища. Теперь предположим, что пустыня пересечена (метод отраба- тывания назад). Чтобы доехать до ее конца, полностью опустошив бак (а это необходимо по требованию минимального расхода топ- 25 лива, т.е. после пересечения пустыни не должно остаться излиш- ков бензина), последнее хранилище должно быть организовано за 500 км до конца пустыни и содержать 500 л топлива. При этом требование минимального расхода топлива означает, что перед пе- ресечением последнего отрезка пустыни бак джипа снова должен быть пуст. Последовательные шаги в решении задачи о джипе изображе- ны на рис. 2.3. Итак, известно место и объем последнего хранили- ща — 500 л (один полный бак) за 500 км до окончания пустыни. На каком расстоянии от этого хранилища должно быть преды- дущее, и сколько оно должно содержать топлива, чтобы оттуда можно было перевезти один полный бак до места последнего хра- нилища? Обозначим это расстояние через x 1 (рис. 2.3, а). Итак, сформулировали частную цель. Попробуем решить поставленную частную цель. Предположим, что за 500 + x 1 км до конца пустыни (в точке предпоследнего хра- нилища) осталось неограниченное количество топлива и доезжаем до этой точки с пустыми баками. Данная ситуация соответству- ет нахождению в точке A (рис. 2.3, б ). Заправляем полный бак (это обозначено на рис. 2.3, б как +1), доезжаем до точки B (ме- ста последнего хранилища), оставляем там какое-то количество топлива так, чтобы осталось только на дорогу назад. При возвра- щении (точка C) бак снова пуст, и он снова заправляется целиком, после чего едем до последнего хранилища (точка D), забираем то, что оставили там на прошлом шаге, и в сумме должны получить ровно 500 л, чтобы пересечь остаток пустыни. Таким образом, три раза проезжаем расстояние x 1 , затрачи- ваем 500 л, чтобы добраться от точки A до точки C, и еще 500, чтобы от точки C с учетом дозаправки пересечь пустыню. Прой- денное расстояние равно 3x 1 + 500 и на это потрачено два полных бака, т.е. 1000 л. Отсюда 3x 1 + 500 = 1000 и имеем x 1 = 500/3 26 500 x 2 Н 3 а а +1 -1/5 -1/5 -3/5 A B C D 0+1 4/5+6/5=2 -1/5 x 1 -3/5 0+1 E F -1/5 -1/5 И 2 а а С а Ф ) x n Н n+1 а +1 -(2n-1)/(2n+1) 0+1 0+1 И n а -1/(2n+1) -1/(2n+1) -(2n-1)/(2n+1) -1/(2n+1) -1/(2n+1) С а Ф ) 500 x 1 Н 2 а а +1 -1/3 -1/3 -1/3 A B C D 0+1 2/3+1/3=1 -1/3 И 1 а С а Ф ) 500 1000 x 1 Н 1 а ? С а Ф а) Рис. 2.3. Решение задачи о джипе: а – постановка частной це- ли; б – решение частной цели: вычисление x 1 ; в – подъ- ем вверх: вычисление x 2 ; г – подъем вверх: вычисле- ние x n 27 или треть бака. На рис. 2.3, б отмечен расход топлива: треть бака на дорогу длиной x 1 , треть оставить в точке B, на оставшейся трети вернуться назад. Заправить полный бак, после проезда еще x 1 километров бак полон на 2/3, доливаем еще одну треть, остав- ленную нами ранее, и с полным баком пересекаем оставшиеся 500 км. Итак, решили одну частную цель, но теперь перед нами стоит другая — нужно завезти два полных бака на расстояние 500 + x 1 = 500 + 500/3 от конца пустыни. Для решения этой частной цели можно использовать решение предыдущей. Схема действий показана на рис. 2.3, в. В этом случае нужно сделать уже не 3, а 5 поездок, расходуя 1/5 бака на каждую поездку и оставляя в хранилище 3/5 бака топлива. После 5 поездок в точке 500 + x 1 (от конца пустыни) имеем два полных бака, а в качестве следующей частной цели в точку 500 + x 1 + x 2 необходимо завезти 3 бака горючего, где x 2 = 500/5. Дальнейшая схема действий изображена на рис. 2.3, г. Для то- го чтобы завезти n баков на расстояние x n , нужно n+1 бак и 2n+1 поездка. Один бак тратится на переезды, n баков перевозятся, и тогда x n = 500/(2n + 1), или 1/(2n + 1)-я часть бака расходуется на одну перевозку. В хранилище оставляется часть топлива, равная 1 − 2/(2n + 1) = (2n − 1)/(2n + 1). После 2n + 1 поездки бак полон на 2n/(2n + 1), и в хранилище перевезено n(2n − 1)/(2n + 1) топлива, т.е. всего перевезли 2n 2n + 1 + n(2n − 1) 2n + 1 = n(2n + 1) 2n + 1 = n баков, что и требовалось. Для решения задачи теперь нужно найти число k хранилищ, которые необходимо организовать. Мы научились проходить рас- стояние 500 + x 1 + x 2 + x 3 + . . .. Чтобы пересечь всю пустыню нужно, чтобы это пройденное расстояние (или израсходованное 28 0 2 4 6 8 10 12 14 16 18 20 100 300 500 700 900 1100 500.00 666.67 766.67 838.10 893.65 939.11 977.57 1010.90 1040.31 1066.63 Рис. 2.4. Частичные суммы ряда 500/(2i+1) топливо, что одно и то же) превышало 1000 км, т.е. k i=0 500 2i + 1 ≥ 1000. Данный ряд является расходящимся, а значит задача всегда имеет решение, так как ряд не имеет предела сверху. Частичные суммы этого ряда приведены на рис. 2.4. Как видно из рисунка, для того чтобы проехать 1000 км, нужно организовать k = 15 хранилищ. Итак, в этой задаче использовали все три подхода. Предпо- ложив, что задача решена, и попробовав описать необходимые для этого условия, сформулировали частную цель. Для решения частных целей использовался метод подъема вверх, т.е. получали решение, используя уже решенные частные цели. Наконец, сово- купность решенных частных целей позволила получить решение задачи в целом. В дальнейшем часто будем использовать те или иные из опи- санных подходов, даже если не всегда применение этих методов будет указываться явно. 29 Задача 2.3 (задача о миссионерах и каннибалах ). На левом берегу реки находятся три миссионера (M ) и три каннибала (K). У них есть одна двухместная лодка для переправы, но ни в какой момент времени ни на одном берегу каннибалов не должно быть больше, чем миссионеров (включая тех, что находятся в лодке). Нужно разработать алгоритм переправки всех миссионеров и кан- нибалов на правый берег реки. Решение. Будем обозначать комбинации миссионеров и канни- балов, находящихся на берегу, как iM jK, где i — число миссионе- ров; j — число каннибалов. Легко подсчитать, что всего существу- ет 16 различных комбинаций числа миссионеров и каннибалов на одном берегу (включая случай, когда берег пуст). Недопустимыми являются всего три комбинации: M 2K, M 3K, 2M 3K. Соответственно, остальные 13 комбинаций допустимы: −, M, K, M K, 2M, 2K, 2M K, 2M 2K, 3M, 3K, 3M K, 3M 2K, 3M 3K. Для решения этой задачи попробуем применить метод подъ- ема вверх. Каждый шаг можно описать парой комбинаций iM jK, соответствующих текущей ситуации на левом и правом берегу. Кроме этого, нужно задать комбинацию миссионеров и канниба- лов, находящихся в лодке в момент переправы (таких комбинаций пять: M , K, M K, 2M , 2K) и направление движения лодки. Пе- реправу с левого берега на правый будем обозначать знаком «−», а с правого на левый — знаком «+». На первом шаге имеем комбинацию 3M 3K|−, все находятся на левом берегу. Ясно, что переправа −2M , т.е. переправа двух миссионеров с левого берега на правый недопустима, так как при- водит к комбинации M 3K|2M и миссионер, находящийся на левом берегу, будет съеден. Также недопустима комбинация −M , при- водящая к 2M 3K|M , и снова на левом берегу каннибалов оказы- вается больше. Переправа −K, хотя формально и допустима, но бессмысленна, так как получаем комбинацию 3M 2K|K, и лодка 30 3M 3K - 3M 2K K M 3K 2M 2M 2K M K 3M K 2K 2M 3K M -K -2M -MK -2K -M 2M 3K M 3M 2K K +K +M +K -2M -MK -2K M 2K 2M K 3M 3K 2M K M 2K 3M K 2K +K M K 2M 2K 2M M 3K 1 1 -2M -MK -M M 2K 2M K 2M 2K M K M 3K 2M 2M K M 2K +K +MK +M +2K 2K 3M K -K -2M -M -2K 1 2 2 3 3 +K +MK +M 4 4 3 3K 3M K 3M 2K -2K +K +2M +M +MK 2K 3M K M K 2M 2K 5 5 3 - 3M 3K -2K 2M 3K M -K -MK Рис. 2.5. Решение задачи о миссионерах и каннибалах 31 оказывается на правом берегу, поэтому на следующем шаге един- ственным возможным вариантом переправы с правого берега на левый оказывается +K, что возвращает нас к исходной ситуации. Таким образом, получаем — на первом шаге в лодку должен сесть как минимум один каннибал, и возможными переправами могут быть либо −M K, либо −KK. Для обоих вариантов мо- жем продолжить такие же рассуждения, отбрасывая недопусти- мые комбинации, и постепенно «поднимаясь вверх» — строя по- следовательность переправ. Рис. 2.5 отображает все последовательные шаги. Недопусти- мые комбинации отмечены серыми прямоугольниками, начальное и конечное состояние — двойными линиями. На этом рисунке не отмечены «петли», т.е. переправа в той же комбинации, что на предыдущем шаге, т.е. из лодки никто не выходит. Ясно, что это просто возвращает нас на шаг назад. Тем не менее, в процессе построения решения образуются циклы — случаи, когда возвра- щаемся к одной из уже рассмотренных комбинаций числа мисси- онеров и каннибалов и положения лодки. Эти циклы помечены номерами в кружках. Как видно из рис. 2.5, любая из допустимых переправ на пер- вом шаге приводит нас к единственной допустимой переправе на втором шаге. Точно так же перед предпоследней переправой воз- можны два варианта. В остальном получившаяся последователь- ность действий однозначно определена — все циклы приводят нас в недопустимые состояния. Для решения задачи можно приме- нить и метод отрабатывания назад. Это даст нам практически то же самое решение, что изображено на рис. 2.5, только строить- ся оно будет снизу вверх. Предположив, что уже перевезли всех, получим комбинацию −|3M 3K. Чтобы собрать эту комбинацию на правом берегу, последней переправой должны быть либо −2K, либо −M K — все остальные варианты недопустимы. Продолжая эти рассуждения, получим решение задачи. Задача 2.4 (задача о переливании). Есть две емкости объемом 3 и 5 л и неограниченный источник воды. Требуется отмерить в точности 4 л воды. 32 4 ? 4 0 4 3 1 3 5 2 1 0 0 2 2 0 2 3 0 5 0 0 0 1 1 5 3 3 3 0 0 3 0 0 Рис. 2.6. Задача о переливании Решение. Прежде всего определим доступные операции. Так как нам неизвестно ничего, кроме объема сосудов, а отмерять объ- ем воды нужно точно, то нельзя совершать никакие действия «на глазок». Это значит, что можно: долить любой сосуд до полного; вылить содержимое любого сосуда; если в сосуде 1 воды меньше, чем свободного места в сосуде 2, перелить всю воду из 1 в 2 ; если в сосуде 1 воды больше, чем свободного места в сосуде 2, долить 2 из 1 до полного. Во избежание двусмысленности будем различать «переливание» воды из одной емкости в другую и «выливание», означающее, что одна из емкостей опустошается, не меняя количества воды в дру- гой. Сразу заметим, что ситуация, при которой обе емкости не целиком заполнены водой, невозможна. При любой операции од- на из емкостей должна либо опустошаться, либо заполняться. 33 0 1 2 3 1 2 3 4 5 0 1 2 3 1 2 3 4 5 0 1 2 3 1 2 3 4 5 а) ) ) Рис. 2.7. Схема решения задачи о переливании Попробуем применить метод отрабатывания назад. Предполо- жим, что задача решена, и емкость объемом 5 л содержит ровно 4 л воды (очевидно, не можем налить 4 л в другую емкость). Обо- значим меньшую емкость как 3, а большую — как 5. Нам неизвест- но, сколько в итоге воды должно содержаться в емкости 3. Так как емкость 5 заполнена частично, то емкость 3 должна быть либо пуста, либо полна (рис. 2.6). Рассмотрим случай, когда емкость 3 пуста, а емкость 5 со- держит 4 л. Какой могла быть последняя допустимая операция, приведшая к данному состоянию, и каким тогда было предыду- щее состояние сосудов? Ясно, что либо сосуд 3 был полон, и вода была вылита, но этот случай уже отметили, и пока что оставим без рассмотрения (на рис. 2.6 эта операция отмечена пунктирной линией), либо — вода из сосуда 3 была перелита в сосуд 5. В этом случае на предыдущем шаге сосуд 3 был полон, а 5 содержал 1 л. Операция, которая могла к этому привести — это переливание 1 л из 3. Ход дальнейших рассуждений показан на рис. 2.6. Итак, |