С++ мастер-класс. 85 нетривиальных проектов, решений и задач Решение

С первого взгляда видно, что задача может быть решена перебором. Видно также, что перебор не так уж велик (не шахматы всё-таки). Вопрос в том, как грамотно его организовать.

Иа практике алгоритм оказывается сравнительно простым, поэтому я ре-пшл сразу привести листинг на С++ со всеми необходимыми комментариями.

Для начала нам потребуются типы данных расположение лодки и ситуация :

лодка находится на одном из берегов enum BoatPos { LEFT, RIGHT };

struct Situation {

int LC, RC; количество людоедов на левом и правом берегу int LM, RM; количество миссионеров на левом и правом берегу BoatPos Pos; расположение лодки

string Move; ход - комментарий, объясняющий, каким образом данная ситуация была достигнута

Situation(int Ic, int rc, int Im, int rm, BoatPos pos, const strings move)

: LC(lc), RC(rc), LM(lm), RM(rm), Pos(pos), Move(move) {}

void Print() вывести содержимое ситуации на экран {

cout LC LM * - RC : RM ;

cout (Pos == LEFT ? -left : -right ) ( Move -)\n-; }

простая операция сравнения, игнорирующая значение Move

bool operator==(const Situations rhs) const

return LC == rhs.LC SS RC == rhs.RC SS LM == rhs.LM S& RM == rhs.RM SS Pos == rhs.Pos;

Единственным заслуживающим отдельного пояснения элементом структуры Situation является поле Move. Алгоритму перебора безразлично, каким путём мы добрались до той или иной ситуации в головоломке. Однако при выводе решения на экран пользователю будет гораздо удобнее видеть конкретные ходы, а не только расположение объектов игрового мира.

и завершить работу прогрс1ммы exit(0);

if(Pos == LEFT) лодка находится на левом берегу {

виды перевозок: два людоеда

Solve(LC - 2, RC + 2, LM, RM, RIGHT, -CC ); людоед и миссионер

Solve(LC -1, RC+1, LM-1, RM+1, RIGHT, -CM ); два миссионера

Solve(LC, RC, LM - 2, RM + 2, RIGHT, -MM ); один людоед

Solve(LC - 1, RC + 1, LM, RM, RIGHT, -C ); один миссионер

Solve(LC, RC, LM - 1, LM + 1, RIGHT, -M );

else if(Pos == RIGHT) лодка находится на правом берегу {

виды перевозок: два людоеда

Solve(LC + 2, RC - 2, LM, RM, LEFT, -CC);

Последовательность ходов, ведущая к решению, хранится в векторе Trace: vector<Situation> Trace;

Основная работа выполняется функцией Solve (), производящей поиск решения подзадачи, исходное состояние которой задано передаваемыми аргументами:

void Solve(int LC, int RC, int LM, int RM, BoatPos Pos,

const string Move = - ) { условный оператор выявляет ситуацию, при которой продолжение исследования текущей ветви не имеет смысла

if ( (LC > LM SS LM > 0) II (RC > RM SS RM > 0) I I LC < 0 II RC < 0 II LM < 0 II RM < 0 II find(Trace.begin(), Trace.end(). Situation(LC, RC, LM, RM, Pos, --)) != Trace.end()) return;

запомнить текущую ситуацию в истории ходов Trace.push back(Situation(LC, RC, LM, RM, Pos, Move));

if(RC == 3 SS RM == 3) {

если на правом берегу три людоеда и три

миссионера, задача решена, вывести решение

for each(Trace.begin{), Trace.end(), mem fun ref(&Situation::Princ));

mUausi

Функция main о всего лишь вызывает Solve () для начальной ситуации, в которой все миссионеры, все людоеды и лодка находятся на левом берегу реки:

int main(int argc, char* argv[]) {

Solve(3, 0, 3, 0, LEFT); return 0;

Первым делом с помощью громоздкого оператора if лроверяется перспективность анализируемой ветви. Ветвь неперспективна, если выполняется хотя бы одно из условий:

количество людоедов на одном из берегов превышает количество миссионеров (LC > LM &:& LM > О или RC > RM && RM > 0);

величина какого-либо параметра станет отрицательной величиной - на берегу не могут находиться, например, минус два миссионера (LC < ОII RC < ОII LM < ОI! RM < 0);

текущая ситуация уже встречалась в процессе работы алгоритма, то есть мы ходим по кругу (find (Trace.begin ( ) , Trace. end(). Situation(LC, RC, LM, RM, Pos, )) != Trace.

end 0 ).

Если ситуация перспективна, следует испытать каждый возможный вариант переправы. Например, запись

Solve(LC, RC, LM - 2, RM + 2, RIGHT, MM );

означает перевозку двух миссионеров с левого берега на правый. Количество людоедов на каждом берегу не меняется (LC, LR), зато два миссионе-

1 Обратите внимание, что количество миссионеров должно быть ненулевым, поскольку лишь в

этом случае людоеды могут кого-то съесть.

4.2.8. Раскраска карт (последний пример перебора с возвратами)

Географическая карта состоит из N областей (государств или административных единиц). Каждая область идентифицируется при помощи порядкового номера в диапазоне 1...N. Входной файл содержит список пар областей, являющихся смежными, то есть имеющих общую границу.

Программа должна приписать каждой области некоторый цвет таким образом, чтобы никакие две соседние области не были бы раскрашены одинаково. Требуется использовать минимально возможное количество цветов. Доказано, что для любой плоской карты достаточно четырёх цветов (или меньше).

На выходе печатается схема раскраски - список пар вида (номер области, код цвета).

4.3. ЭВРИСТИЧЕСКИЙ ПОИСК

4.3.1. Игра в 15, или эвристический поиск А* Суть задачи

Игра в 15 - старая, очень известная головоломка. В коробке размером 4x4 находится 15 пронумерованных от 1 до 15 фишек. Шестнадцатая ячейка

ра вычитаются с левого берега (LM - 2) и добавляются к правому (RM + 2). Лодка после этого действия находится на правом берегу

Вероятно, фрагмент с восемью вызовами Solve () можно легко ужать вдвое, но при этом, как мце кажется, пострадает ясность.

Результат работы готовой программы показан ниже:

людоед и миссионер

Solve(LC + 1, RC 1, LM + 1, RM - 1, LEFT, CM ); два миссионера

Solve(LC, RC, LM +2, RM - 2, LEFT, MM ); один людоед

Solve(LC + 1, RC - 1, LM, RM, LEFT, C ); один миссионер

Solve(LC, RC, LM + 1, LM - 1, LEFT, M );

извлечь текущую ситуацию из истории ходов Trace.pop back();

Рис 4.18. Игра в 15 (головоломка решена)

коробки пуста. Цель игры состоит в том, чтобы с помощью последовательности сдвигов расположить фишки по возрастанию номеров (рис. 4.18).

Требуется приспособить компьютер для реншния этой головоломки. Человек вводит начальную конфигурацию кубиков коробки, а компьютер печатает список кубиков, сдвигаемых на каждом шаге.

Не для всякой конфигурации решение существует. Например, если отсортировать фишки по возрастанию, а затем поменять местами номера 14 и 15, решить головоломку не удастся. Разумеется, в такой ситуации пользователя придётся огорчить соответствующим сообщением.

Подсказка

Идея, что задача представляет собой поиск вершины в графе (конфигурации - вершины, ходы - рёбра), лежит на поверхности. Полный перебор вершин (такой, как поиск в ширину), конечно, всегда находит решение, но в нашем случае граф задачи велик, и как-то ускорить этот процесс необходимо.

Считаю уместным кратко описать здесь так называемый эвристический поиск А*, который может пригодиться при решении задачи. В самом общем виде поиск в графе представляет собой нехитрую процедуру. Формируется список вершин, подлежащих рассмотрению. Изначально в него помещается только стартовая вершина графа. Далее по некоторому правилу из списка извлекается и просматривается очередная вершина, а её соседи - вершины, непосредственно связанные с нею рёбрами - добавляются в список. Поиск заканчивается, как только целевая вершина найдена. Если список

2 Надо признаться, что на практике для Ифы в 15 так вряд ли получится. Граф игры огромен,

и его полный перебор потребует недопустимо долгого времени.

вершин пуст, это означает, что мы уже просмотрели весь граф и так и не достигли цели.

Правило выбора очередной рассматриваемой вершины из списка и определяет вид поиска. Например, если всегда выбирать вершины, относящиеся к самому глубокому уровню, мы получим поиск в глубину (depth-first search). А если не переходить к соседям потомков до того, как будут полностью рассмотрены соседи предков, получится поиск в ширину (breadth-first search).

Идея поиска А* заключается в выборе на очередном шаге такой верпшны из списка, для которой сумма г<еиы и эвристики была бы минимальной.

Цена в нашем случае просто представляет собой количество ходов, которое пришлось сделать, чтобы добраться до этой вершины из стартовой конфигурации. Цена стартовой вершины равна нулю, цена любой соседней с ней - единице, цена соседа соседней - двойке и так далее. Обратите внимание, что из любой вершины, являющейся соседней для стартовой, можно также вернуться в саму стартовую вершину. Метод поиска не обязан запоминать, какие вершины уже просмотрены, поэтому стартовая вершина опять попадёт список, но уже с ценой, равной двойке.

Можно модифицировать поиск так, чтобы просмотренные вершины запо-мршались. Забегая вперёд, скажу, что для решения задачи Игра в 15 список просмотренных вершин был бы полезен.

Эвристика является оценкой количества ходов от текущей позиции до вершины, соответствующей решению головоломки. Эвристика - оценка оптимистичная, то есть её величина не должна превосходить истинного количества ходов, требуемого для нахождения решения. Например, если заведомо известно, что за пять ходов головоломка решается, значение эвристики будет числом в промежутке 0-5. При этом эвристика должна быть настолько близкой к истине, насколько возможно, иначе пользы от неё окажется мало. Так, эвристика, всюду равная нулю, допустима, но совершенно бесполезна.

При использовании эвристического поиска в первую очередь рассматриваются наиболее перспективные ходы, ведущие прямо к цели. Быстрота нахождения решения напрямую зависит от качества эвристики. Заметьте, однако, что здесь требуется найти определённый компромисс: хорошая эвристика может требовать большего времени для вычисления и, следовательно, замедлять поиск.

Поиск А* - очень полезная, широко используемая на практике методика. Например, с её помощью можно найти кратчайший путь между двумя точками на карте. Для маленьких карт обычно применяют известный алгоритм Дейкстры, но его производительность для больших, разветвлённых графов