Самый длинный путь рубки
Условие задачи. На стандартном поле 8x8 расставлены черные шашки и одна белая. Необходимо найти самый длинный путь рубки для белой шашки.
Ясно, что совокупность всех возможных путей рубки представляет собой ориентированный граф, а графы очень хорошо представляются связными списками (это к вопросу о технике представления данных). А так как совокупность путей рубки хорошо представляется ориентированным графом, следовательно, иная более программистская постановка задачи звучит так: дан ориентированный граф, найти его самую длинную ветвь (или все самые длинные ветви, что не намного сложнее).
Рис. 6.5. Пример позиции
Конечно, новая формулировка не совсем идентична первоначальной, она исходит из данности графа, а в постановке задачи дана позиция на шашечной доске. Поэтому мысль разделить задачу на две - построение графа и поиск на графе - будет вполне естественной. Получив позицию, мы преобразуем ее в граф, а затем в соответствии с новой формулировкой подумаем о том, как обойти этот граф в поисках самой длинной ветви.
Примечание. Обратите внимание, что наши рассуждения носят подготовительный характер и не имеют прямого отношения к идее решения. О том, как, собственно, решать задачу, еще не было сказано ни одного слова. А вывод о возможности разбиения задачи на две нетерпеливому человеку может показаться даже лишним. Он может сказать: «Я хочу сразу придумать, как именно искать самый длинный путь». И, скорее всего, если этот человек не без способностей, то так оно и будет. А дальше будет одно большое НО. Придумать идею можно, но ее надо еще и реализовать! И нужно сказать, что зачастую возникающие технические проблемы настолько велики, что эффект от идеи сходит на нет. Что же мы фактически сделали, переформулировав задачу?
А мы как раз и озаботились хотя бы обозначением этих будущих технических проблем, приблизили постановку к тем структурам данных, которыми мы реально располагаем в языке программирования.
Внимательный читатель мог бы сказать, что ранее мы начинали именно с идеи, выраженной в общепонятных терминах, и зачастую даже не математических. Но здесь нет противоречия. Надо просто видеть разницу в задачах. Если задача заключает в себе большую смысловую проблему, то, конечно, главные усилия должны быть сосредоточены на разработке логики. Рассматриваемая задача - то, что называется технически сложная, поэтому и подход к ней иной. Конечно, что сложно технически, а что логически - это решается каждым разработчиком относительно себя. Что для одного сложно, то для другого легко! Что для одного сложная логика, то для другого технические детали!
Если вы согласны с тем, что было сказано в примечании, то вы должны быть согласны и с тем, что наш следующий шаг - это описание структуры данных, представляющих собой граф. Структуру данных определяет условие. Мы решили использовать динамическую память, следовательно, использование связных списков - дело решенное, и осталось только определить структуру записи связного списка.
Очевидно, что элемент связного списка нужен для описания текущей позиции рубящей шашки, следовательно, необходимо просто посмотреть, что известно про позицию. Л известно следующее:
- ? координаты текущей позиции;
- ? адреса элементов связного списка, описывающих позиции, в которые рубящая шашка может попасть из текущей.
Достижимых позиций не более трех (позицию, из которой шашка пришла, можно исключить), а координат две. Следовательно, в структуре элемента связного списка должно быть три поля, являющихся указателями на элемент связного списка, и два числовых поля, имеющих смысл координат.
После обсуждения структуры данных можно обдумать, как эта структура данных должна быть построена:
- ? количество указателей в нашей структуре данных также фиксировано, но они не обязаны все указывать на реально существующие адреса;
- ? ветви строятся до тех пор, пока это возможно, различные ветви могут иметь различную длину.
Эти замечания существенны, но они не касаются общей структуры программы, которую можно построить как поиск на двоичном дереве. Это рекурсивная процедура, получающая на вход координаты текущей позиции и выполняющая следующие действия:
Для каждого из 4 возможных направлений рубки
Если в рассматриваемом направлении рубка возможна, то Осуществляем рубку.
Ищем свободный указатель и от него создаем указатель на новый элемент списка, который и будет содержать информацию о новой позиции рубящей шашки.
Вызываем процедуру с координатами нового положения шашки.
Далее зададим себе вопрос, что в нашем алгоритме неопределенного, ответ на который даст информацию для дальнейшего анализа. А неопределенности есть, и достаточно существенные, например:
- ? не вполне понятно, как определить, возможно данное направление или нет. И что такое направление вообще;
- ? в чем заключается процедура рубки;
- ? предполагается, что возможных направлений рубки четыре. Это не так. Их только три, так как с одного из направлений шашка пришла, и его как направление рубки рассматривать нельзя. Но если мы желаем одно из направлений исключить, то необходимо придумать, как его отделить от других трех;
- ? и самое главное - из сказанного ранее совершено не ясно, как мы собираемся обходить построенный граф в поисках самого длинного продолжения, хотя, может быть, пока это и не важно.
Попробуйте подумать хотя бы над первым вопросом. Даже интуитивно ясно, что в структуре данных нет достаточной информации для ответа. Это от того, что была совершена серьезная ошибка. Описав необходимую структуру графа и начав рассуждать об алгоритме (программе), мы ничего не сказали о том, как данный граф будет построен. Повторимся еще раз. Необходимо понять не только, то что граф будет из себя представлять, но и то, как он строится из первичной информации, то есть из той информации, которая дана непосредственно в условии.
Первичная информация - это позиция на доске. Ее можно представить, например, двумерным массивом. Договоримся, что пустая клетка будет представлена нулем. Шашка, осуществляющая рубку, пусть изображается числом два, а ее противники пусть будут единицами.
Теперь можно ответить на поставленные вопросы.
- 1. Направление - это вектор, такой что если его прибавить к координатам (индексам) элемента двумерного массива доски, то получим элемент массива, представляющий клетку, в которую можно осуществить ход. Таких направлений (векторов) четыре: (-2, -2), (-2, 2), (2, -2), (2, 2).
- 2. Для того чтобы выяснить допустимость направления, необходимо установить истинность двух утверждений: первое - ячейка массива, полученная прибавлением к координатам (индексам) текущего элемента вектора направления, содержит ноль (клетка доски пуста); второе - ячейка массива, полученная прибавлением половины вектора направления, содержит единицу (в клетке доски стоит шашка противника).
- 3. Процедура рубки заключается в двух действиях:
- • изменении координат (индексов) текущего элемента на вектор направления;
- ? обнулении элемента, полученного прибавлением половины вектора направления.
Отбросить одно из направлений можно двумя способами. Например, запоминать, откуда пришла шашка, для чего в элементе связного списка ввести одно дополнительное поле, описывающее источник перехода. Но можно этого и не делать, если немного подумать о том, как проводится проверка на допустимость направления.
Только что было сказано, что одно из условий допустимости - это наличие единицы в ячейке через «половину вектора направления», а в описании процедуры рубки сказано, что эта единица обнуляется. Это означает, что направление, с которого шашка пришла, при расчете следующего хода будет недопустимым (там после выполнения хода стоит ноль). Следовательно, можно проблему допустимости проигнорировать и проверять все четыре направления. Одна из проверок окажется лишней, но в качестве компенсации отпадет необходимость в дополнительных операциях по проверке допустимости, которые почти наверняка окажутся более сложными, а следовательно, мы получим и еще выигрыш в упрощении логики программы.
Проблема восстановления данных. Переборные алгоритмы, а мы имеем дело именно с перебором, требуют «отката», то есть восстановления данных в некоторой точке перебора с целью построения нового варианта. В нашей ситуации «откат» заключается в восстановлении одной-единственной шашки, срубленной только что. Из смысла процедуры рубки ясно, что срубленная шашка находится ровно посредине между исходной и конечной позициями рубящей шашки (при рубке одной шашки противника). То есть координаты поля, на котором стояла шашка (индексы элемента массива, содержащего единицу), можно найти как среднее арифметическое координат исходного и конечного полей. Это, в свою очередь, потребует запоминания информации об исходном поле.
Все, что обсуждалось до сих пор, касается только построения графа (связного списка), а теперь подходим к главному, к проблеме поиска наидлиннейшего пути рубки, или, в наших терминах, наидлиннейшей ветви графа, или, что то же самое, наидлиннейшей ветви связного списка.
Решение этой задачи сводится к необходимости помечать элементы связного списка, через которые проходит путь рубки. Можно, конечно, создать дополнительную структуру, в которую наидлиннейший путь будет записываться, но дополнительные структуры данных - это дополнительное усложнение логики, и, может быть, существенное. Поэтому лучше создадим еще одно поле в элементе связного списка для хранения информации о пути. Это тоже дополнительная структура, но она уже локальная.
Эта дополнительная информация может быть длиной уже построенного пути, проходящего через данное поле. В этом случае алгоритм поиска наидлиннейшего пути построить несложно:
Числовую характеристику начального узла объявить максимальной.
Пока не достигнут тупик, делать Проверить все поля ссылок
Если ссылка не тупиковая, то
Если элемент, на который указывает ссылка, содержит характеристику, равную максимальной, то перейти по этой ссылке.
Нетрудно заметить, что алгоритм обеспечивает поиск не одного маршрута, а всех существующих. Сложность в понимании, наверное, вызывает первый пункт, в котором числовая характеристика начального узла объявляется максимальной. Может быть, не вполне понятно, на каком основании. Заметим, что наидлиннейший маршрут обязан проходить через начальный элемент, а так как числовая характеристика длины только одна, то она и будет содержать длиннейший маршрут по окончании работы.
Л теперь все-таки о механизме. Значение длины маршрута известно только на последнем поле (последнем элементе связного списка). Следовательно, определение характеристики длины должно заключаться в возврате этого конечного числа при возврате по маршруту.
Пусть шашка находится в некоторой точке А и предстоит принять решение о числовой характеристике для пункта Л. Предположим, что из А выходит максимальное количество ненулевых указателей (то есть три), это означает, что характеристику для Л необходимо выбирать из трех возможных значений, которые возвращены в Л рекурсивными вызовами. Какое из них выбрать? Конечно же, максимальное.
И последнее, когда принимать решение о числовой характеристике для текущего элемента (поля доски)? Конечно же, тогда, когда будут отработаны все допустимые направления рубки. Из этого следует, что формировать числовую характеристику мы можем в процессе построения графа (связного списка). Все существенные технические проблемы обсуждены, можно записать алгоритм. Головной алгоритм, видимо, будет состоять из двух процедур:
- ? алгоритм построения связного списка - графа;
- ? алгоритм поиска длиннейшего маршрута.
Алгоритм построения связного списка:
Ввод данных в виде двумерного массива
Создание начального элемента списка с записью в него исходного положения рубящей шашки
Вызов рекурсивной процедуры построения связного списка Запись в начальный элемент полученной длины длиннейшего маршрута
Рекурсивная процедура построения связного списка:
Входные данные: адрес на текущий элемент списка, длина уже
пройденного маршрута
Запомнить адрес на текущий элемент
Обработка направления (-2, -2)
Максимальная длина = возвращенной длине Восстановить адрес на текущий элемент Обработка направления (2, -2)
Длина = возвращенной длине
Если Длина > Максимальной То Максимальная = Длине Восстановить адрес на текущий элемент Обработка направления (2, 2)
Длина = возвращенной длине
Если Длина > Максимальной То Максимальная = Длине Восстановить адрес на текущий элемент Обработка направления (-2, 2)
Длина = возвращенной длине
Если Длина > Максимальной То Максимальная = Длине Восстановить адрес на текущий элемент
Записать Максимальную длину как характеристику длины маршрута для текущего элемента связного списка.
Обработка направления:
Проверить допустимость хода в заданном направлении Если Ход допустим, То
Ищем свободный (то есть указывающий в никуда) указатель на адрес элемента списка Создаем новый элемент списка
Записываем в новый элемент координаты новой позиции рубящей шашки
Вызываем процедуру построения связного списка с новыми фактическими параметрами Восстанавливаем позицию
Возвращаем длину, равную пройденной длине
Иначе
Возвращаем длину, меньшую пройденной длины на 1 (так как ход оказался недопустимым)
Задача для самостоятельного решения
Все алгоритмические проблемы задачи уже исследованы, напишите
самостоятельно программу.
