Гурский Д., Турбина Е. - Вычисления в MathCad 12 (1077322), страница 38
Текст из файла (страница 38)
Суть этого метода заключается в следующей последовательности действий.1. Организуется иерархия шагов коня. Каждому варианту шага присваивается свойиндекс.2. То, куда будет сделан ход, зависит от того, какие варианты шага приведут коня в «пустую» клетку. Если все варианты возможны, используется шаг с наименьшим индексом. Если сделать этот шаг нельзя, осуществляется попытка сделать шаг с индексом, на единицу большим, — и так до тех пор, пока свободная клетка не будет найдена.3.
Если в результате очередного шага конь попал в клетку, из которой невозможносделать шаг в клетку, в которой он не был ранее, маршрут признается тупиковым.При этом конь должен сделать один шаг назад и «попробовать» походить в другуюклетку (последовательно используя варианты шага, расположенные в иерархиипозже тупикового). Если это невозможно, делается еще один шаг возврата и попытка осуществляется снова — и так до тех пор, пока «пустая» клетка не будет найдена.4. Если решение найдено не будет, то конь вернется в исходную клетку, опробовав всевозможные маршруты.
О том же, что искомый маршрут обнаружен, можно судитьпо тому, что на поле не останется ни одной непосещенной клетки.Визуально алгоритм перебора с возвратом можно представить как последовательныйобход графа (дерева) неизвестной структуры в поисках ветви максимальной длины.Пример подобного обхода для небольшого графа показан на рис. 4.7. Чтобы найти наиболее длинную ветвь из шести узлов, понадобилось сделать 17 шагов.
В случае графа,соответствующего обходу конем шахматной доски, чтобы найти ветвь из 64 узлов, может понадобиться сделать миллионы или даже миллиарды шагов.Каждый из возможных маршрутов коня может быть визуализирован как ветвь графа.Клеткам маршрута будут соответствовать узлы.
Так как любой маршрут будет иметьчасть, общую с другими маршрутами, ветви при движении сверху вниз сливаются, сходясь к одному узлу, соответствующему клетке начала движения. Чтобы найти ветвьграфа требуемой длины, нужно организовать последовательный обход его ветвей слева направо или справа налево (см. рис.
4.7). Наиболее простой способ это сделать с помощью средств программирования связан с использованием рекурсии.4.9. Пример программирования: решение задачи Эйлера о ходе коня * 1 5 9Рис. 4.7. Обход графа посредством последовательного перебора с возвратомАлгоритм рекурсивно вызываемой функции, выполняющей обход графа маршрутов,будет несложен. Каждая ее активация будет соответствовать отдельному узлу графа.Основная цель активации — выполнить очередной шаг вверх к следующему узлу ветви.
Для этого посредством цикла проверяется, имеется ли вариант хода, который приведет коня в непосещенную ранее клетку. Если такой обнаруживается, осуществляется рекурсивный вызов, создающий соответствующую этой клетке активацию. Текущаяже активация ожидает результата дальнейшего исследования ветви, который будетвозвращен в конце концов новой активацией. Если, просмотрев все варианты хода, кодактивации обнаружит, что возникла тупиковая ситуация, активация должна быть разрушена, а в точку соответствующего ей вызова, относящегося к предыдущей активации,должно быть возвращено информационное сообщение об этом. Получив это сообщение, нижележащая активация проверит, можно ли посредством хода с более низкимприоритетом, чем осуществленный ранее, перейти в «пустую» клетку.
Если такой вариант хода имеется, действия повторятся. Если же все варианты уже исчерпаны, активация разрушится, передав сообщение о тупике нижележащей активации. И так до техпор, пока не будет найден нужный маршрут. Об успехе будет говорить то, что очередная активация окажется в стеке в качестве элемента под номером п2, где п — размерность доски. При этом активация должна быть разрушена, а в точку вызова возвращено сообщение, говорящее об успешном завершении обхода. Данное сообщение должнопередаваться сверху вниз от активации к активации, разрушая их.
В качестве такогосообщения имеет смысл использовать матрицу с найденным маршрутом.Приведенное выше описание алгоритма, который нам предстоит реализовать, скореевсего, покажется вам запутанным и малопонятным. Это неудивительно ввиду чрезвычайной абстрактности рекурсивных алгоритмов.
Вернитесь к описанию алгоритма обхода после того, как мы создадим соответствующую ему функцию. При этом вы легкопоймете то, что трудно понять сейчас.Функцию, предназначенную для рекурсивного обхода графа маршрутов коня, мы назовем brain. Она будет принимать четыре параметра: индексы клетки, из которой должен быть сделан ход (i и j), матрицу с информацией о том, в каких клетках конь ужепобывал (field), количество «заполненных» на момент вызова клеток (п). Чтобы запуститьработу алгоритма, активировав brain, необходимо предварительно создать описывающуюдоску матрицу нужной размерности посредством функции chess_field, а затем заменить1 6 0 •:• Глава 4. Программированиев ней значение 0 элемента, соответствующего клетке начала движения, на 1.
Исполнятьроль такого «детонатора» у нас будет функция recursive_solver(n, i, j), где n — размерность доски, i и j — индексы клетки, из которой конь должен начать движение. Ее код:recursive_solver(n,i,j) :=field < chess_field (n)field. <- 1brain(i, j , field, 1)Первое действие, которое должна выполнить функция brain, это проверить, не закончил ли конь обход доски на прошлом шаге. На то, что это действительно так, будет указывать отсутствие нулей в описывающей поле матрице field. Наименьшим значениемв ней будет 1. Выделить же минимальный элемент из матрицы можно, воспользовавшись функцией min.
Если проверка покажет, что обход был успешно завершен, то текущая активация должна быть разрушена, а в точку вызова возвращена матрица field,хранящая найденный маршрут. Осуществить эти действия позволяет оператор return.brain(i,j, field, n) := return field if min(field) = 1Если на поле есть еще непосещенные клетки, нужно проверить, можно ли сделать шагв одну из них из клетки, в которой конь находится в данный момент. Для этого следуетзапустить цикл от 0 до 7, последовательно перебирая все варианты хода. Чтобы вычислить индексы клетки, в которую конь переместится, сделав некоторый ход, нужнок индексам данной клетки прибавить смещения по соответствующим направлениям(как вы помните, смещения для всех вариантов шага хранятся в векторах вложенноговектора step). Вычислив индексы, нужно проверить, корректны ли они.
Индекс не может быть меньше нуля и больше или равен номеру последнего столбца (строки) матрицы поля. Если окажется, что значение индекса некорректно, необходимо сразу перейти к рассмотрению следующего варианта хода, для чего нужно задействоватьоператор continue. Аналогично нужно поступить, если клетка, в которую перешел быконь в результате хода, уже была посещена им ранее (об этом говорит то, что значениесоответствующего элемента матрицы поля не равно 0).for keO..7continueif -/o < il < rows(field) л 0 < jl < cols(field) л field. ..
=•Обратите внимание, как был задан комплекс условий, выполнение которых необходимо, чтобы ход можно было осуществить.• В Mathcad возможны двойные сравнения типа А<х<В. Это довольно необычно:в универсальных языках программирования сначала бы вычислилось условие А<х,а полученный при этом результат сравнился затем с В. По этой причине в такихязыках, как C++, двойные сравнения невозможны (их необходимо разбивать наотдельные операции сравнения, связанные посредством операторов логическогоИ и ИЛИ). В Mathcad же можно задавать не только двойные, но и более сложныесравнения, содержащие сколь угодно много операций.
Например:2<3<4<5<6=16>4<5<7<7>7= 14.9. Пример программирования: решение задачи Эйлера о ходе коня• 161О Посредством двойных сравнений мы проверяем, существует ли клетка, в которуюпереместился бы конь в результате хода. Ее индексы не должны быть отрицательными и превышать количество строк (столбцов) в матрице. Определить размерность матрицы можно, воспользовавшись функцией rows (количество рядков) илиcols (количество столбцов).• Отдельные условия объединяем в комплекс условий посредством операторов логического И «л», так как для того, чтобы конь мог сделать ход, необходимо одновременное выполнение всех условий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
