Гурский Д., Турбина Е. - Вычисления в MathCad 12 (1077322), страница 39
Текст из файла (страница 39)
Если бы было достаточно выполнения хотябы одного условия, мы бы задействовали оператор логического ИЛИ «v». Важнойособенностью логических операторов является то, что они имеют более низкийприоритет, чем операторы сравнения (подобно тому, как операторы суммы и разности уступают по приоритету умножению и делению). Поэтому двойные сравнения не нужно брать в скобки, объединяя их посредством оператора И. На момент вычисления оператора И выражения справа и слева его уже будут вычислены в 0 или 1.• Комплекс условий записан так, что он вычисляется в истину тогда, когда конь может сделать ход в клетку.
Однако оператор continue должен быть задействован тогда, когда условия вычисляются в ложь. По этой причине нужно перед комплексомусловий ввести оператор логического НЕ «—i», который преобразует ложь в истину, а истину в ложь.Если все необходимые условия выполнятся, нужно сделать ход. Это будет выражатьсяв том, что значение соответствующего клетке элемента матрицы field должно быть изменено с 0 на номер данного хода. Определить этот номер очень просто, так как номер предыдущего хода передается функции brain в качестве четвертого параметра.field, ., <- п + 1Сделав ход, нужно выполнить рекурсивный вызов функции brain. Результатом этоговызова будет или сообщение «Bad way», означающее, что данный путь тупиковый, илиматрица с найденным маршрутом.
Если маршрут будет найден, дальнейшую работуфункции продолжать нет смысла. При этом активация должна быть разрушена, а в качестве результата ее работы возвращена матрица с маршрутом. Если же данный путьоказался тупиковым, необходимо сделать шаг назад, что будет выражаться в том, чтозначение заполненного последним элемента матрицы field должно быть заменено нулем.res_field <- brain(il,jl,field,n + 1)return res_field if res_field ^ "Bad way"field,..*-0il,jlВажным и тонким моментом является то, как активации функции brain обмениваютсяинформацией.
Почему для того, чтобы следующая активация «знала», какие клеткиуже были посещены конем, матрица field должна быть передана ей в качестве параметра? Почему для того, чтобы «спустить» матрицу с маршрутом от последней активациик первой, она должна последовательно возвращаться активациями, по мере их разрушения, как результат их работы? На это имеется две причины. Во-первых, функция неможет изменить объект данных, который не относится непосредственно к ее коду. Приобращении к внешней переменной из кода функции создается копия ее значения.И именно с копией работает код функции.
Поэтому, даже если объект данных, хранимый во внешней переменной, подвергается модификациям по мере работы кода функции, после разрушения активации никаких изменений не останется, так как все операции проводились над копией. Именно поэтому матрицы field и res field нельзя вынести162 •Глава 4. Программированиево внешние переменные. Во-вторых, функция, вызванная из кода другой функции, невидит ее локальных переменных. Поэтому нельзя создать матрицу field при вызовефункции recursive_solver, а затем лишь модифицировать ее по мере роста рекурсивнойцепи. Код функции может обращаться лишь к глобальным переменным.Если все варианты шага будут просмотрены и не один из них не приведет к нахождению искомого маршрута, направление признается тупиковым.
В этом случае функцияbrain должна возвратить строку «Bad way».Функция brain готова. Ее полный код:brain(i, j , field, n) := return field if min(field) = 1for keO..7continue if^(o<il<rows(field)AO<jl<cols(field)Afield.1. =0)field, .. <- n + 1res_field<-brain(il,jl,field,n+ 1)return res_field if res_field Ф "Bad way""Bad way"Как видите, функции brain соответствует довольно небольшой код. Это очень характерно для рекурсивных алгоритмов: их абстрактность и сложность для понимания компенсируется компактностью, доходящей порой до изящества. Именно поэтому рекурсивные алгоритмы столь популярны в программировании.Проверим написанный код в работе.
Мы увидим, что он весьма эффективен: он находит маршрут вне зависимости от того, какая клетка выбрана начальной. Однако, увы,за приемлемое время маршрут обнаруживается лишь для досок размером 6x6 клетокили более маленьких. Для стандартной же доски 8x8 клеток поиск будет вестись стольдолго, что результата будет просто невозможно дождаться. Это связано с колоссальным количеством вариантов, которые необходимо перебрать алгоритму.(\16 21 10 25 420 11 24 15 22recursive_solver(5> 0,0) = 17 2 19 6 9 recursive_solver(6,3,3) =12 7 4 23 143 18 13 8 534 29 20 11 3628 19 32 35 22 1333 30 21 12 5 1018 27 61 14 237 2 25 16 9 4J26 17 8 3 24 15Увы, но написанную программу невозможно оптимизировать так, чтобы она стала работать существенно быстрее.
Не получится найти решение для доски 8x8 клеток, дажеесли программу перевести в нерекурсивную форму или реализовать ее посредствомкомпилируемого языка вроде C++. Дело в том, что в основе нашей программы лежит4.9. Пример программирования: решение задачи Эйлера о ходе коня* 163универсальный, но неэффективный алгоритм. Количественно эффективность можнооценить, зная функцию зависимости числа необходимых для нахождения решенияшагов от входных параметров. Чаще всего точно определить такую функцию нельзя.Однако очень часто можно вывести ее общий вид.
Исходя из него, алгоритмы можноусловно разделить на линейные, полиномиальные и экспоненциальные (возможныи другие варианты, например «логарифмические» алгоритмы). Количество необходимых шагов, а следовательно, и время выполнения линейных алгоритмов пропорциоZнально величине параметра. В случае полиномиальных алгоритмов N=P , где N — число шагов, Р — величина параметра, z — показатель степени. Чем больше z, тем менееэффективен алгоритм. В случае экспоненциальных алгоритмов N=ZP, где Z — некоторое число.
Понятно, что время выполнения экспоненциальных алгоритмов увеличивается по мере возрастания параметра гораздо быстрее, чем время выполнения линейных и полиномиальных алгоритмов. Поэтому алгоритмы экспоненциального типаявляются наименее эффективными. Созданный же нами алгоритм обхода шахматнойдоски посредством перебора с возвратом — экспоненциальный.
Довольно просто оценить верхнюю границу для числа вариантов, которые придется перебрать компьютерупри поиске маршрута коня на доске размером пхп клеток:Количество необходимых шагов алгоритма с увеличением размера доски возрастаетчрезвычайно быстро. Этим объясняется то, почему для доски 6x6 клеток маршрут обнаруживается довольно быстро, а уже для доски 7x7 он ищется многие часы. Сделаемвывод. Задачу Эйлера мы решили, но лишь частично. Чтобы справиться с ней в случаебольших досок, нужно использовать более эффективный алгоритм, чем перебор с возвратом.
И такие алгоритмы за триста лет существования задачи Эйлера были найдены.Наиболее известным из них является алгоритм, основывающийся на правиле Вансдорфа.Вансдорф сформулировал свое знаменитое правило в 1823 году в брошюре, посвященной его опыту решения задачи Эйлера о коне. Оно гласит: «На каждом ходу необходимо ставить фигуру в то поле, из которого можно совершить наименьшее количествоходов на еще непосещенные поля. Если же два или несколько полей равноценны, ходможно сделать в любое из них».Алгоритм, построенный на основании правила Вансдорфа, будет очень быстрым. Несложно догадаться, что он будет исполняться за полиномиальное время, а точнее, за время, пропорциональное п2, где п — размер доски. Чтобы найти маршрут в случае доски 8x8,ему понадобится всего 64 шага.
То есть маршрут будет определен за доли секунды.Реализация метода Вансдорфа не требует использования рекурсии, и поэтому соответствующий код более прост для написания и изучения. Поэтому мы будем комментировать его кратко. Функцию chess_field и вектор step, чтобы не выполнять лишнюю работу, просто скопируем из рекурсивного алгоритма.Итак, приступим. Первое, что мы сделаем, это создадим функцию, которая будет оценивать, сколько можно осуществить ходов из данной клетки. Называться она будетchecker, а в качестве параметров принимать индексы клетки, которую нужно проверитьна количество возможных из нее ходов, и матрицу с информацией о том, какие клеткиуже были посещены (аналогична матрице field созданного ранее рекурсивного алгоритма).
Алгоритм функции checker будет следующим.1. Создаем счетчик (переменная free_position), в котором будет храниться число возможных ходов. Изначально он должен быть равен 0.1 6 4 •:• Глава 4. Программирование2. Запускаем цикл и перебираем все восемь вариантов хода.3. На каждой итерации цикла производим следующие действия.
Сначала вычисляеминдексы клетки, в которую переместится конь, сделав ход. Затем проверяем, существует ли данная клетка и является ли она «пустой». Если какое-то из условий невыполняется, необходимо перейти к следующей итерации (посредством оператораcontinue). Если условия выполнятся, нужно увеличить счетчик возможных ходов на 1.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
