II. Метод подьема вверх.

Поиск решения, состоящий в пошаговом улучшении некоторого начального решения.

Пример 1: Задача о миссионерах и каннибалах.

На левом берегу реки находятся три миссионера (М) и три каннибала (К). У них есть одна двухместная лодка для переправы, но ни в какой момент времени ни на одном берегу каннибалов не должно быть больше, чем миссионеров (включая тех, что находятся в лодке). Нужно разработать алгоритм переправки всех миссионеров и кан­нибалов на правый берег реки.

Решение. Будем обозначать комбинации миссионеров и канни­балов, находящихся на берегу, как iMjK, где i — число миссионе­ров; j — число каннибалов. Легко подсчитать, что всего существу­ет 16 различных комбинаций числа миссионеров и каннибалов на одном берегу (включая случай, когда берег пуст). Недопустимыми являются всего три комбинации:

М2К, МЗК, 2МЗК.

Соответственно, остальные 13 комбинаций допустимы:

-, М, К, МК, 2М, 2К, 2МК, 2М2К, ЗМ, 3K, ЗМК, ЗМ2К, 3М3К.

Для решения этой задачи попробуем применить метод подъ­ема вверх. Каждый шаг можно описать парой комбинаций iMjK, соответствующих текущей ситуации на левом и правом берегу. Кроме этого, нужно задать комбинацию миссионеров и канниба­лов, находящихся в лодке в момент переправы (таких комбинаций пять: М, К, МК, 2М, 2К) и направление движения лодки. Пе­реправу с левого берега на правый будем обозначать знаком «—», а с правого на левый — знаком «+».

На первом шаге имеем комбинацию ЗМЗК|—, все находятся на левом берегу. Ясно, что переправа — 2М, т.е. переправа двух миссионеров с левого берега на правый недопустима, так как при­водит к комбинации М3К|2М и миссионер, находящийся на левом берегу, будет съеден. Также недопустима комбинация —М, при­водящая к 2МЗК|М, и снова на левом берегу каннибалов оказы­вается больше. Переправа —К, хотя формально и допустима, но бессмысленна, так как получаем комбинацию ЗМ2К\К, и лодка оказывается на правом берегу, поэтому на следующем шаге един­ственным возможным вариантом переправы с правого берега на левый оказывается +К, что возвращает нас к исходной ситуации.

Таким образом, получаем — на нервом шаге в лодку должен сесть как минимум один каннибал, и возможными переправами могут быть либо —МК, либо —КК. Для обоих вариантов мо­жем продолжить такие же рассуждения, отбрасывая недопусти­мые комбинации, и постепенно «поднимаясь вверх» — строя по­следовательность переправ.

Рис. 4

Рис. 4 отображает все последовательные шаги. Недопусти­мые комбинации отмечены серыми прямоугольниками, начальное и конечное состояние — двойными линиями. На этом рисунке не отмечены «петли», т.е. переправа в той же комбинации, что на предыдущем шаге, т.е. из лодки никто не выходит. Ясно, что это просто возвращает нас на шаг назад. Тем не менее, в процессе построения решения образуются циклы — случаи, когда возвра­щаемся к одной из уже рассмотренных комбинаций числа мисси­онеров и каннибалов и положения лодки. Эти циклы помечены номерами в кружках.

Как видно из рис. 4, любая из допустимых переправ на пер­вом шаге приводит нас к единственной допустимой переправе на втором шаге. Точно так же перед предпоследней переправой воз­можны два варианта. В остальном получившаяся последователь­ность действий однозначно определена — все циклы приводят нас в недопустимые состояния. Для решения задачи можно приме­нить и метод отрабатывания назад. Это даст нам практически то же самое решение, что изображено на рис. 2.5, только строить­ся оно будет снизу вверх. Предположив, что уже перевезли всех, получим комбинацию — /3 М3К. Чтобы собрать эту комбинацию на правом берегу, последней переправой должны быть либо — 2К, либо —МК — все остальные варианты недопустимы. Продолжая эти рассуждения, получим решение задачи.

Пример 2: Задача о монетах.

Имеется 25 монет, среди которых, возможно, есть фальшивка (она легче). Есть весы с двумя чашками. Надо найти фальшивку или сказать, что таких нет.

Решение. Для решения этой задачей попробуем воспользо­ваться методом подъема вверх. Найдем некоторое решение, т.е. определим порядок взвешивания монет, а затем попробуем это ре­шение улучшить. Итак, попробуем разделить все множество монет на две части. Так как число монет нечетно, то получим две груп­пы по 12 монет и еще одна останется в запасе. Порядок взвешива­ния проиллюстрирован с помощью дерева на рис. 5. Каждый овал задает количество взвешиваемых монет на каждой чаше ве­сов, в кружке рядом с овалом отмечено, сколько остается монет. Квадратами с цифрой 1 помечена ситуация, когда фальшивую монету уже можно определить однозначно. Результатом первого взвешивания могут являться три случая. Во-первых, 12 монет на левой чаше весов оказываются легче 12 монет на правой чаше. Это означает, что фальшивая монета находится на левой чаше и в дальнейшем можно рассматривать только эти 12 монет. Если правая чаша оказывается легче, то под подозрением оказываются другие 12 монет. Если же чаши весов уравновешены, то фальши­вой может являться только единственная оставшаяся монета, и еще за одно взвешивание с любой из остальных 24 определяем ре­зультат (на этом шаге результатов взвешивания два, а не три, так как знаем, какая монета точно правильная и для определенности можем положить ее на левую чашу весов).

Далее, если остались 12 монет, снова поделим их на этот раз поровну, на две части по 6 монет и осуществим взвешивание. За­тем образуются группы из 3 монет, и наконец, из оставшихся трех взвешиваются любые две. Так как в этом случае уже точно извест­но, что фальшивая монета есть, то дополнительное взвешивание для оставшейся монеты не требуется.

Схема на рис. 5 полностью симметрична, поэтому приве­дена не полностью. Эта схема требует в худшем случае четырех взвешиваний. Можно ли улучшить ее так, чтобы сократить число взвешиваний? В чем главный недостаток схемы?

Рис. 5

Можно легко увидеть, за счет чего может произойти улуч­шение. Дело в том, что любое взвешивание подразумевает три возможных результата: когда одна чаша весов легче, когда она тяжелее и когда весы уравновешены. Результат равенства весов используется только при первом и последних взвешиваниях и то для поиска среди двух или трех оставшихся монет. Главным на­шим принципом было делить все или почти все монеты на две части, что практически исключило из дерева взвешиваний подде­ревья, соответствующие равенству на весах.

Те же самые выводы можно получить с другой стороны. У нас 25 монет и существует 26 возможных исходов. Эти исходы являются листьями дерева взвешиваний. Число исходов-листьев уменьшено быть не может, но чтобы уменьшить число взвешива­ний нужно, чтобы дерево больше росло «вширь», чем «вглубь», т.е. имело меньше уровней. Для этого нужно увеличить размер­ность этого дерева. Так как более чем троичным дерево взвеши­ваний быть не может, нужно приблизить его максимально близко к полному троичному дереву, а для этого монеты необходимо де­лить на три примерно равные части. Попробуем применить этот подход. Разделим все монеты на группы по 9, 9 и 7 монет. Схема взвешиваний показана на рис. 6. Видно, что проведенные рас­суждения действительно позволили улучшить решение: теперь в худшем случае требуется только три взвешивания. Причем ясно, что еще лучше решение быть не может, так как для того, чтобы тернарное дерево имело 26 листьев, оно должно иметь как мини­мум 3 уровня.

Рис. 6

Дата добавления: 2015-11-30