АЛГОРИТМЫ
Новости
Рассылка новостей
Форум
AlgoPascal
Редактор блок-схем
Статьи
О сайте
Контакты
Автор:Быстрицкий В.Д.
| Поводом к написанию данной статьи послужило письмо с описанием не рекурсивного алгоритма решения задачи о Ханойской башне, пришедшее от Артема Алексеева (е-майл: aralexx@inbox.ru; www: http://aralexx.tripod.com), это письмо практически полностью приведено в третей части статьи. При написании статьи использовались материалы книги Ж. Арсака "Программирование игр и головоломок". |
Головоломка "Ханойские башни" достаточно старая и хорошо известная, с ней связано несколько забавных легенд, но суть проблемы, которую я попытаюсь рассмотреть на примере данной задачи - использование рекурсивных алгоритмов и преобразование их к не рекурсивным.
Для начала сформулируем саму задачу. Даны три стержня ((н) - начальный, (к)- конечный, (д) - дополнительный) на стержень (н) нанизано некоторое количество дисков (будем полагать его равным n) при этом все диски имеют разный диаметр и расположены на стержне (н) в порядке уменьшения диаметра снизу в верх (см. рис).
Необходимо переместить все диски на стержень (к), т.е. головоломка должна быть приведена к виду:
при этом за один ход можно переместить только один диск, и в результате хода не должно возникнуть ситуации, когда диск с большим диаметром будет положен на диск с меньшим диаметром.
Выбор той или иной стратегии перемещения дисков приводит к новому вопросу, сколько необходимо ходов для того чтобы головоломка была полностью разрешена. Причем очевидно что количество ходов растет с ростом числа дисков, и желательно получить некоторую функцию f(n), которая выдавала бы для данной стратегии количество ходов необходимых для решения задачи в зависимости от числа дисков. В статье рассматривается только одна стратегия, оптимальность которой можно доказать. Вначале стратегия получается в виде рекурсивного алгоритма, а затем преобразуется к не рекурсивной форме.
Рекурсивная стратегия.
Итак, нам необходимо перенести n дисков со стержня (н) на стержень (к). Допустим у нас есть процедура перенесения n-1 диска, обозначим ее Х(n-1,(Ст1),(Ст2)), тогда задача легко разрешима для этого вначале перенесем n-1 диск со стержня (н) на стержень (д), применяя процедуру Х, затем перенесем n-ый диск со стержня (н) на стержень (к) (обозначим эту процедуру П((Ст1),(Ст2)) и наконец перенесем n-1 диск со стержня (д) на стержень (к). Работа выполнена. Алгоритм в этом случае можно записать следующим образом:
1. Х(n-1, (н), (д)) 2. П((н),(к)) 3. Х(n-1, (д), (к))
Теперь необходим частный случай, не являющийся рекурсивным. Если диск всего один, то можно сразу перенести его со стержня (н) на стержень (к), таким образом, выполняется тождество Х(1, (Ст1), (Ст2))=П((Ст1), (Ст2)). Таким образом, процедура Х представляется в виде блок-схемы:
Просто? Да, несомненно, просто, но все равно некоторым такое решение внушает опасение. Почему? Скорее всего, сказывается недостаток владения рекурсивными методами, но не только. Рекурсивные решения отличаются от обычных именно своей не очевидностью. Что же сделать, чтобы "поверить" в то, что предъявленная стратегия верна? На мой взгляд, лучший способ проверить стратегию "практически" для малых n.
Вернемся к вопросу вычисления функции f(n). Для предъявленной рекурсивной процедуры, представление f(n) достаточно тривиально:
f(1)=1 f(n)=2* f(n-1)+1
Явный вид функции f(n) нетрудно найти из приведенных выше соотношений, пользуясь принципом математической индукции: f(n)=2n -1.
Дополнительно к тому, что уже имеется, заметим еще одно свойство перемещаемых дисков. Пусть наши диски пронумерованы от 1 до n, таким образом, что диск с наименьшим диаметром имеет номер 1, второй по величине диаметра диск номер 2, и т.д., наконец диск с наибольшим диаметром имеет номер n. Тогда можно заметить, два диска с номерами одинаковой четности никогда не будут лежать друг на друге (т.е. диск с номером 2 не ляжет на диск с номером 4, 6 или 8). Докажем что это свойство выполнено. Доказательство будем проводить по индукции, допустим, что свойство выполнено для процедуры Х(p,(Ст1),(Ст2)), где p < n (для p=1 и Х(1,(Ст1),(Ст2)) свойство выполнено автоматически), далее докажем, что тогда свойство выполняется и для Х(n,(Ст1),(Ст2)). Начнем с переноса (n-1) дисков на стержень (д). Пока не передвинут (n-1)-ый диск, ни один диск не кладется непосредственно на диск с номером n и значит требуемое свойство выполнено. Рассмотрим момент, когда n-2 дисков находятся на одном стержне, диски с номерами n-1 и n - на другом стержне, а третий стержень пуст. Мы перемещаем диск с номером n-1. Теперь нужно переместить первые n-2 дисков на диск с номером n-1, поэтому диски будут оказываться на диске с номером n. Если мы помещаем диск с номером k на диск с номером n, то для того, чтобы образовать пирамиду дисков с номерами от k до 1 и иметь возможность, переместить диск с номером k+1 на диск с номером n-1. Но поскольку требуемое свойство выполняется для n-1 дисков, то честность k+1 диска не может совпадать с четностью n-1. А значит, она совпадает с четностью n, и отсюда следует, что четность n и k различна.
Те из Вас кто склонен к пунктуальному разбору доказательств, может усмотреть некоторую нечеткость, но смею заверить, это не приводит к тому, что доказательство становиться "не законным", и сделано просто для сокращения изложения.
Итеративная стратегия.
Итеративная стратегия основывается на рекурсивной, но при этом из решения полностью исключается рекурсия. Это хорошо, как с точки зрения практического понимания алгоритма (теперь его можно "пощупать"), так и с той точки зрения, что не все языки программирования поддерживают рекурсивный вызов (хотя таких и меньшинство).
Вначале я процитирую (вернее приведу практически полностью, изменив только обозначения) письмо Артема Алексеева (е-майл: aralexx@inbox.ru; www: http://aralexx.tripod.com), а затем попытаюсь доказать более или менее строго, те факты на которых Артем основывает свой алгоритм:
|
Это не рекурсивный алгоритм "переброски" Ханойской башни. Вот он, метод (не знаю, описан ли он где-то: (литературы на эту тему я не встречал, до всего дошёл сам): |
На самом деле алгоритм переброски, который предлагает Антон, если хорошо присмотреться, получается из рекурсивного. Поэтому избавимся от рекурсии и докажем, более или менее строго, те факты, которые приведены в письме.
Заметим вначале, что, в силу условий налагаемых на перемещение дисков, всегда диск с номером 1 находится на вершине одного из стержней. И на любом шаге мы можем переместить либо диск 1, либо один из дисков (с наименьшим диаметром) находящихся на вершине стержня отличного от того на котором расположен диск с номером 1. Из всего этого можно сделать вывод, что диск один перемещается один раз в каждые два хода, иначе расположение дисков повторялось бы. Покажем, что наш первый диск всегда перемещается по одной из выбранных стратегий: либо (н)-(д)-(к), либо (н)-(к)-(д), причем выбор той или иной стратегии зависит от четности общего количества дисков n. Доказательство проведем индукцией по общему числу дисков n. Допустим, что в процедуре Х(n-1,(н),(к)) диск 1 перемещается всегда в одном направлении. Тогда для Х(n,(н),(к)) нам необходимо выполнить Х(n-1,(н),(д)) и Х(n-1,(д),(к)), т.е. вместо того чтобы непосредственно переходить от стержня (н) к стержню (к) мы делаем этот переход, используя стержень (д) , другими словами мы делаем два перехода в обратном направлении. При этом диск 1 продолжает перемещаться всегда в одном и том же направлении, но это перемещение меняется при переходе от n-1 к n. Поскольку при n=1 диск 1 перемещается с диска (н) на диск (д), то такое перемещение сохраняется для всех нечетных n. В то время как для четных n он будет перемещаться согласно стратегии (н)-(д)-(к).
В принципе уже это дает нам возможность представить итеративный алгоритм перемещения дисков, который имеет вид:
Неплохой алгоритм, если мы хотим перемещать диски вручную, но фраза "переместить единственный диск, который можно переместить, кроме диска 1" выглядит не достаточно конкретизировано, поэтому вернемся к письму Артема.
Номер любого хода можно единственным образом представить в виде k=(2r+1)2p-1.
Итак, первое, что нам надо доказать, это то, что на шаге с номером k мы перемещаем диск, номер p. Для p=1 это тривиально, он действительно перемещается каждый нечетный ход. Возвращаясь к рекурсивному алгоритму, заметим, что перенос диска с номером p, происходит только внутри процедуры Х(p,(Ст1), (Ст2)), а между двумя вызовами этой процедуры, происходит одно перемещение диска (алгоритм Х - П - Х), причем число шагов необходимых для выполнения процедуры Х(p,(Ст1), (Ст2)) равно значению функции f(p). Таким образом, первое перемещение p-го диска происходит на шаге f(p-1)+1=2p-1, а каждое следующие через 2p-1-1+1+2p-1=2p-1 шагов, т.е. номера шагов, когда мы перемещаем p -ый диск действительно имеют вид k=(2r+1)2p-1. При этом, как мы показали, диски с нечетными номерами перемещаются по той же стратегии, что и диск номер 1, диски с четными номерами по обратной стратегии. Таким образом, теперь мы можем конкретизировать приведенный выше итеративный алгоритм:
Я надеюсь, что данная статья еще раз подчеркнула, тот факт, что при помощи рекурсии многие задачи решаются легко и красиво, что называется "в две строки". Решение той же проблемы, без использования рекурсии, приводит к серьезным сложностям, даже тогда когда мы уже имея рекурсивный алгоритм, пытаемся его просто переработать.
Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU