Раздел: Документация
0 ... 47 48 49 50 51 52 53 ... 177 универсальный, но неэффективный алгоритм. Количественно эффективность можно оценить, зная функцию зависимости числа необходимых для нахождения решения шагов от входных параметров. Чаще всего точно определить такую функцию нельзя Однако очень часто можно вывести ее общий вид. Исходя из него, алгоритмы можно условно разделить на линейные, полиномиальные и экспоненциальные (возможны и другие варианты, например «логарифмические» алгоритмы). Количество необходимых шагов, а следовательно, и время выполнения линейных алгоритмов пропорционально величине параметра. В случае полиномиальных алгоритмов N-P", где N — число шагов, P - величина параметра, г — показатель степени. Чем больше z. тем менее эффективен алгоритм. В случае экспоненциальных алгоритмов N-Z*. где Z - некоторое число. Понятно, что время выполнения экспонищиальных алгоритмов увеличивается по мере возрастания параметра гораздо быстрее, чем время выполнения линейных и полиномиальных алгоритмов. Поэтому алгоритмы экспоненциального типа являются наименее эффективными. Созданный же нами алгоритм обхода шахматной доски посредством перебора с возвратом — экспоненциальный. Довольно просто оценить верхнюю границу Для числа вариантов, которые придется перебрать компьютеру при поиске маршрута коня на доске размером пхп клеток: Количество необходимых шагов алгоритма с увеличением размера доски возрастает чрезвычайно быстро. Этим объясняется то, почему для доски 6x6 клеток маршрут обнаруживается довольно быстра а уже для доски 7x7 он ищется многие часы. Сделаем вывод. Задачу Эйлера мы решили, но л ишь частично. Чтобы справиться с ней в случае больших досок, нужно использовать более эффективный алгоритм, чем перебор с возвратом. И такие алгоритмы за триста лет существования задачи Эйлера были найдены. Наиболее известным из них является алгоритм, основывающийся на правиле Вансдорфа. Вансдорф сформулировал свое знаменитое правило в 1823 году в брошюре, посвященной его опыту решения задачи Эйлера о коне. Оно гласит: «На каждом ходу необходимо ставить фигуру в то поле, из которого можно совершить наименьшее количество ходов на еще нелосешеиные поля. Если же два или несколько полей равноценны, ход можно сделать в любое из них». Алгоритм, построенный на основании правила Вансдорфа. будет очень быстрым. Несложно догадаться, что он будет исполняться за полиномиальное время, а точнее, за время, пропорциональное п1, где п — размер доски. Чтобы найти маршрут в случае доски 8x8, ему понадобится всего 64 шага. То есть маршрут будет определен за доли секунды. Реализация метода Вансдорфа нетребует использования рекурсии, и поэтому соответствующий код более прост для написания и ид учения. Поэтому мы будем комментировать его кратко. Функцию chesa field и вектор step, чтобы не выполнять лишнюю работу, просто скопируем из рекурсивного алгоритма. Итак, приступим. Первое, что мы сделаем, это создадим функцию, которая будет оценивать, сколько можно осуществить ходов из данной клетки. Называться она будет checker, а в качестве параметров принимать индексы клетки, которую нужно проверить на количество возможных из нее ходов, и матрицу с информацией о том, какие клетки ужебыли посещены (анплошчна матрице field седланного ранее рекурсивного алгоритма). Алгоритм функции checker будет следующим. 1, Создаем счетчик (переменная free position). в котором будет храниться число возможных ходов. Изначально он должен быть равен 0. 2. Запускаем цикл » перебираем все восемь вариантов хода. 3 На каждой итерации цикла производим следующие действия. Сначала вычисляем индексы клетки, в которую переместится конь, сделав ход. Затем проверяем, существует ли данная клетка и является ли она «пустой». Если какое-то из условий не выполняется, необходимо перейти к следующей итерации (посредством оператора continue). Если условия выполнятся, нужно увеличить счетчик возможных ходов на 1. 4. По завершении работы цикла счетчик должен быть возвращен программой как результат ее работы, В коде функция checker будет иметь следующий вид: checker(i,j,field) := free position for keO.7 pl*-i+(stepk Л«Ч+(*ерк) continue on error field, ,, il.jl free posilion «— free position + 1 if field. — 0 I free position Обратите внимание, как в коде функции checker учитывается, что вычисленные индексы могут соответствовать не существующей реально клетке. Для этого используется оператор on error. Как вы помните, выражение в левом маркере данного оператора irpo-делывается тогда, когда выполнение выражения в правом маркере приводит к возникновению ошибки. Если индексы не определяют конкретного элемента field, система зарегистрирует ошибку. При этом будет активизирован оператор continue и цикл перейдет к следующей итерации. Далее мы должны создать функцию, которая будет определять, в какую нз свободных клеток нужно сделать ход с учетом правила Вансдорфл. Называться она будет optim step. Параметры у нее будут следующие: индексы клетки, в которой находится конь, и матрица с информацией о предыдущих ходах фигуры. Алгоритм функции optlm step несложен, 1.Запускаем цикл, перебирающий все варианты хода. 2.Перейдя к очередному варианту хода, вычисляем индексы и проверяем, соответствуют ли они существующей и непосещенной еще клетке. Если необходимые условия не выполняются, переходим сразу на следующую итерацию. 3.Если клетка существует и свободна, вычисляем ее «рейтинг» посредством созданной ранее функции checker. Далее сравниваем полученное значение со значением переменной min res, в которой хранится наименьший рейтинг из определенных на предыдущих шагах (изначально min res необходимо присвоить значение, заведомо превосходящее наибольший нз возможных рейтингов, то есть 8). Если рейтинг клетки оказывается меньше значения min res, данную переменную следует переопределить, присвоив ей его значение. Также при этом в переменную best stcp необходимо занести индекс вектора, описывающего данный ход. 4.В качестве результата работы функции нужно возвратить переменную beststep, хранящую индекс вектора вложенного вектора step, который соответствует Ходу в клетку, из которой можно сделать наименьшее число ходов. На языке программ и рпвания функция optim stcp может быть реализована следу ю а щм образом: optim step (i,j, field) rain res <— 10 for k e 0.. 7 il «- 1 + [n<-L+(step4 jN-i+(stepk),] continue on error field res II. Jl checker(il,jl,field) if fieldjl *0 continue otherwise (best step *-k minres «- res) if res < min res I beststep Написанные выше функции лишь вспомогательные. Непосредственно маршрут будет определять функция solver. У нее будет три параметра: размерность матрицы, которую нужно обойти, и индексы клетки, с которой необходимо начать движение. Алгоритм функции solver будет следующим, 1.Сначала, используя соэдш тую еще для «курсивного алгоритма функцию chess field, создаем описывающую поле матрицу field. Далее переопределяем значение элемента field, соответствующего клетке, с которой начинается обход, с 0 на 1. 2.Запускаем цикл из п1-1 итераций, где п — размерность матрицы (не п!, гак как первый ход делается вручную). 3.На каждой итерации осуществляем один шаг вперед. Для этого с помощью функции optim step определяем, в каком векторе вложенного вектора step находятся смещения, описывающие нужный ход. Зная смещения, легко найти шшексы клетки. Ход в нее должен заключаться в том, что значение соответствующего ей элемента матрицы field должно переопределяться с 0 на помер данного хода. 4.В качестве результата работы функции возвращаем матрицу field, содержащую маршрут обхода поля. Код функции solver solver(n,i first, j first) := field field (i й>т k e 2.. n nexi step chess field(n) ifirsi, jfirei - ifirst j *- .Lfirst) 2 optim step (i, j, field) field .J field 0 ... 47 48 49 50 51 52 53 ... 177
|
