Ход конем или поиск нового решения задачи

Сегодня обсуждаем тему: ход конем или поиск нового решения задачи с комментариями от профессионалов. В статье собраны самые важные с нашей точки зрения нюансы, которые заслуживают особого внимания.

К играм не относится, но все же.
Захотел решить задачку:
Есть поле, 10*10 клеток. Надо походить шахматным конем так, чтобы пройти все клетки поля и на каждую клетку вступать только один раз.

возможные ходы с клетки:

Пример ходов:

Задача решается рекурсивно (другие варианты даже в голову не лезут), но вот только сделав простой алгоритм перебора и запустив его, жду порядочно давно — решение найти не может, перебрал более 10млн ходов.
Вот функция перебора:

Перед началом выполнения функции, в массив comb добавляем первую позицию коня на доске, и от нее начинает поиск решения.

Как написал выше — выполняется программа очень долго, поэтому есть вопрос — а есть ли решение данной задачи и есть ли более быстрый алгоритм?

Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, — четными.

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

Итого:
1. Доску надо представить в виде графа. Клетки представить вершинами, а возможные ходы — ребрами.
2. Теперь поставить все с ног на голову: ребра представить вершинами, вершины — ребрами. Нужно учитывать, что будут ребра, которые соединяют больше двух вершин.
3. Посчитать количество четных и нечетных вершин. По теореме им.Эйлера (которая выше) построить путь, если можно. Тут пойдет рекурсия, но если на каком-то шаге станет больше 2х нечетных вершин, то надо быстро назад.
4. .
5. PROFIT

[2]

PS Кто бородат, проверьте. В такое время я мог словить глюк.
PPS и место топу в ИИ разделе.

Ну да, учитывая выше описанную теорему решения нет. Но в детстве вроде на бумаге раскладывал, но могу и ошибаться, программа пока выполняется, но машина слабая (Celeron 2.4GHz), уже прошло 270+ млн итераций, максимально по 98 ходов найдено, буду ждать дальнейшего расклада 🙂

задачка с олимпиады по программированию помню пару лет назад ломал голову над такой же

Решил задачку, алгоритм проще простого — ходить на ту клетку, с которой меньше всего возможных ходов. Сделал демку, если кому интересно.

Chipmunk
> Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
На любой доске (во всяком случае начиная с 5×5) будет всегда больше двух нечётных вершин. И задача вообще не в том, чтобы пройти все рёбра, а чтобы обойти все вершины, так что Эйлер тут отдыхает.

Volodar
> Решил задачку, алгоритм проще простого — ходить на ту клетку, с которой меньше
> всего возможных ходов. Сделал демку, если кому интересно.
И это работает быстрее алгоритма с применением теоремы?

Zefick
> И задача вообще не в том, чтобы пройти все рёбра, а чтобы обойти все вершины,
> так что Эйлер тут отдыхает.
Так укажи ошибку в моем решении. Такое впечатление, что ты оценивал его правильность по отдельным словам.

А мне кажется, что в подобных задачах применяют так называемое «динамическое программирование».

Chipmunk
> И это работает быстрее алгоритма с применением теоремы?
>
Не делал через теорему. Если есть путь, то он его находит за то количество итераций, сколько ходов должно быть (на доске 10*10 за 100 итераций). Но иногда загоняется в тупик не пройдя и третьей части поля.

Задача Эйлера (Ход конем)

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

Вложение Размер
«ход конем», презентация к докладу 629.18 КБ
Предварительный просмотр:

Подписи к слайдам:

Задача Эйлера “ Ход конём ” Исследовательская работа на тему : Выполнил : Кривенко И.Р. 10 ” Д ” Руководитель : учитель математики Богданенко Е.Н.

Мышление о шахматных задачах и головоломках Метод Эйлера Метод Вандермонда Правило Варнсдорфа Мнемоническое стихотворение Вывод Содержание

Шахматная задача – это искусственно созданная позиция фигур на доске, в которой необходимо выполнить некоторое условие (например, поставить мат в три хода). Шахматная головоломка – это задача на сообразительность, в которой используется шахматная доска и шахматные фигуры. Решение шахматных задач, этюдов и головоломок – необычное и увлекательное занятие, способствующее развитию мыслительных способностей. Самая интересная и необычная шахматная фигура – конь. Конь – самая непрямолинейная шахматная фигура. Решение шахматных задач, в которых фигурируют только кони, способствует развитию нестандартного непрямолинейного мышления. Мышление о шахматных задачах и головоломках

Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся не пройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов . Конь ходит в порядке, указанном числами. Так как из последнего места 64 он может перейти на 1, то этот полный ход есть возвратный».Таково решение задачи о ходе шахматного коня, данное Эйлером Метод Эйлера

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей , где x и y — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8. Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности. Метод Вандермонда

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

Обойти конём все шахматные клетки и ни разу не побывать дважды на одной и той же, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно благодаря стихотворению: Мнемоническое стихотворение Алеет Осень Ценными Дарами, Еще Один Животворящий День. Хлеба Червонят Желтыми Шнурами, Хрустальных Вод Философична Сень. Два Вечера Цеплявшиеся Шишки Артист Писал, Бездонна Синева. Дорожный Шлак Дымится Чай Эффектней Шоколада, Фарфоры Чашек Достаются Трем, Блондинке Девушка Дана Отрада Форшмак Делить Холодным Острием. Жена, Толкая Хилую Подругу, Желает Сняться Этим Выходным, Ценя Сама Арктическую Вьюг у Бросает Шар Арбуза Четверым. Цикад Пяток, Едва Чревовещая, Дарует Дрему Фикусам Окна. Хотя Довольны Жаждавшие Чая, Хозяин Шумно Жертвует Вина. Фокстротами Шесть Девушек Пленились, Эстрадных Танцев Фантастичней Па, Едва Ступающий Цыпленок Вылез, А Селезень Блуждающий Алеет Тело Бронзовой Осины, Царит Теней Ажурная Длина. Беззвучней, Чем Автомобиля Шины, Болоту Ветер Дарит Семена. Фонарь Восьмью Химерами Сияет, Жук Прилетает, Хлопая, Туда . Желанна Осень, Если Довершает Ценнейший Отдых Бодрого Труда. Первые буквы задают координаты ходов : Алеет Осень = А1; Ценными Дарами = С2 .

Читайте так же:  Хочу совет психолога!

Подходя к концу моей исследовательской работы, мы узнали : Как обойти конем все 64 клетки шахматной доски так, чтобы на каждой клетке конь был только один раз и затем возвратился бы в клетку, из которой вышел. Вывод

Ход конем или поиск нового решения задачи

Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.

Правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

На практике это реализуется, например, следующим образом. Перед каждым ходом коня вычисляется рейтинг ближайших доступных полей — полей, на которых конь еще не был, и на которые он может перейти за один ход. Рейтинг поля определяется числом ближайших доступных с него полей. Чем меньше рейтинг, тем он лучше. Потом делается ход на поле с наименьшим рейтингом (на любое из таковых, если их несколько), и так далее, пока есть куда ходить.

Эвристика всегда работает на досках от 5×5 до 76×76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.

[1]


Переборное решение

Другой способ решения задачи, состоит, очевидно, в переборе с отходом назад. Ниже дана иллюстрация подхода для доски 8×8.

Используем два одномерных массива row[64] и col[64] для хранения соответственно номеров строк и колонок, которые конь последовательно проходит по доске.

Конь, находящийся в позиции (i, j), может следующим ходом оказаться в клетках с координатами (i-2, j+1), (i-1, j+2), (i+1, j+2), (i+2, ,j+1), (i+2, ,j-1), (i+1, j-2), (i-1, j-2), (i-2, j-1). Заметим, что если конь находится вблизи края доски, то некоторые ходы могут вызвать перемещение коня за ее пределы, что, конечно же, недопустимо. Восемь возможных перемещений коня могут быть заданы в виде двух массивов ktmov1[] и ktmov2[], как продемонстрировано в следующем фрагменте программы.

Исходя из этого, конь, находящийся в позиции (i, j) может переместиться в позицию (i+ktmov[k], j+ktmov2[k]), где k — какое-либо значение из диапазона 0 — 7, выбираемое из условия, что конь должен остаться на доске. Итак, программа, реализующая перемещение коня в соответствии с вышеприведенными условиями будет выглядеть следующим образом:

Ход конем или поиск нового решения задачи

нПЦОП МЙ ДПУЛХ ТБЪНЕТБНЙ 4 × N ПВПКФЙ ИПДПН ЛПОС, РПВЩЧБЧ ОБ ЛБЦДПН РПМЕ ТПЧОП ПДЙО ТБЪ, Й ЧЕТОХФШУС ОБ ЙУИПДОПЕ РПМЕ?

тБУЛТБУЙН ДПУЛХ 4 × N Ч 4 ГЧЕФБ ФБЛ, ЮФПВЩ, ЕУМЙ ЛПОШ УФПЙФ ОБ РПМЕ ГЧЕФБ 1 (УППФЧЕФУФЧЕООП 2), ФП УМЕДХАЭЙН ИПДПН ПО ЧУФБОЕФ ОБ РПМЕ ГЧЕФБ 3 (УППФЧЕФУФЧЕООП 4).

фПЗДБ ФБЛ ЛБЛ РПМЕК ГЧЕФПЧ 1 Й 2 УФПМШЛП ЦЕ, УЛПМШЛП Й РПМЕК ГЧЕФПЧ 3 Й 4, ФП Ч УМХЮБЕ ОБМЙЮЙС ПВИПДБ ЛПОЕН ДПУЛЙ ГЧЕФБ РБТ (1, 2) Й (3, 4) ЮЕТЕДХАФУС. уМЕДПЧБФЕМШОП, ЧУСЛЙК ТБЪ, ЛБЛ ЛПОШ ЧУФБЕФ ОБ РПМЕ ГЧЕФБ 3, УМЕДХАЭЙН ИПДПН ПО ДПМЦЕО ЧУФБФШ ОБ РПМЕ ГЧЕФБ 1 ЙМЙ 2 — Б МЕЗЛП ЧЙДЕФШ, ЮФП ПО НПЦЕФ ЧУФБФШ ФПМШЛП ОБ РПМЕ ГЧЕФБ 1. ъОБЮЙФ, РТЙ ПВИПДЕ ДПУЛЙ ГЧЕФБ 1 Й 3 ЮЕТЕДХАФУС. оП ЬФП ОЕЧПЪНПЦОП, ФБЛ ЛБЛ ФПЗДБ ЛПОШ ОЙЛПЗДБ ОЕ ЧУФБОЕФ ОБ РПМС ГЧЕФПЧ 2 Й 4. нЩ РТЙЫМЙ Л РТПФЙЧПТЕЮЙА.

1 2 1 2 1 2
3 4 3 4 3 4
4 3 4 3 4 3
2 1 2 1 2 1

йУФПЮОЙЛЙ Й РТЕГЕДЕОФЩ ЙУРПМШЪПЧБОЙС

ЛОЙЗБ
бЧФПТ зЕОЛЙО у.б., йФЕОВЕТЗ й.ч., жПНЙО д.ч.
зПД ЙЪДБОЙС 1994
оБЪЧБОЙЕ мЕОЙОЗТБДУЛЙЕ НБФЕНБФЙЮЕУЛЙЕ ЛТХЦЛЙ
йЪДБФЕМШУФЧП лЙТПЧ: «буб»
йЪДБОЙЕ 1
ЗМБЧБ
оПНЕТ 12
оБЪЧБОЙЕ йОЧБТЙБОФ
фЕНБ йОЧБТЙБОФЩ
ЪБДБЮБ
оПНЕТ 015

рТПЕЛФ ПУХЭЕУФЧМСЕФУС РТЙ РПДДЕТЦЛЕ Й .

Задача «Ход короля» Решение

Шахматный король ходит по горизонтали, вертикали и диагонали, но только на 1 клетку. Даны две различные клетки шахматной доски, определите, может ли король попасть с первой клетки на вторую одним ходом. Программа получает на вход четыре числа от 1 до 8 каждое, задающие номер столбца и номер строки сначала для первой клетки, потом для второй клетки. Программа должна вывести YES , если из первой клетки ходом короля можно попасть во вторую или NO в противном случае.

Комментарии

в этом уроке не рассматривается and

т.е. abs я имел ввиду )

как решить без abs?
в уроке об этом ни слова

a=int(input())
b=int(input())
c=int(input())
d=int(input())
if a==c-1 and b==d-1:
print (‘YES’)
else:
print (‘NO’)

Добавить комментарий Отменить ответ

Пн Вт Ср Чт Пт Сб Вс

ЕГЭ на соточку для чайников

Прошу прощения, что так долго пропадал. Питошка вернулся, да еще и с группой в вконтакте, подписывайтесь. Помимо этого, на питошке откроется новая рубрика, в которой будут четкие объяснения всех заданий ЕГЭ и ОГЭ по информатике, внимательно прочитав которые, я уверен, вы улучшите свои баллы на экзамене

Решение задачи о ходе коня¶

Алгоритм, который мы используем для решения задачи о ходе коня, называется поиск в глубину, или DFS (от англ. depth first search — прим. переводчика). В отличие от поиска в ширину, обсуждавшегося в предыдущем разделе и строящего один уровень дерева поиска за раз, этот алгоритм создаёт дерево поиска, исследуя одну из ветвей настолько глубоко, насколько это возможно. В этом разделе мы рассмотрим два алгоритма, реализующих DFS. Первый будет непосредственно решать задачу о ходе коня, явно запрещая посещать исследованный узел больше одного раза. Второй — более общий случай, позволяющий в процессе конструирования дерева посещать узлы несколько раз. Он будет использоваться в следующих разделах при разработке дополнительных алгоритмов для графов.

Исследование графа в глубину — в точности то, что нам необходимо для поиска пути ровно в 63 ребра. Мы увидим, как алгоритм, попадая в тупик (место на графе, откуда больше нет возможных ходов), возвращается вверх по дереву на следующую по глубине вершину, что позволяет сделать допустимый ход.

Функция knightTour

принимает четыре параметра: n — текущую глубину дерева, path — список посещённых вершин, u — вершину, которую мы бы хотели исследовать, и limit — количество узлов в графе. Эта функция рекурсивная. Когда она вызывается, то прежде всего проверяет базовое условие. Если путь содержит 64 вершины, мы возвращаем knightTour со статусом True , показывающим успешное завершение поиска маршрута. В противном случае исследование продолжается на уровне ниже, для чего выбирается новая вершина и вызывается knightTour .

Читайте так же:  Два муравейника

DFS тоже использует окрашивание для отслеживания посещённых вершин графа. Непосещённые узлы имеют белый цвет, посещённые — серый. Если все соседи данной вершины уже исследованы, но цель в 64 узла не достигнута, то мы зашли в тупик. Следовательно, необходимо вернуться назад. Откат происходит в том случае, когда knightTour

возвращает False . В поиске в ширину для отслеживания вершины, которую нужно посетить следующей, мы использовали очередь. Поскольку поиск в глубину рекурсивен, для помощи с откатом неявно используется стек. Когда вызов knightTour возвращает False (строка 11), мы попрежнему находимся внутри цикла while и рассматриваем следующую вершину из nbrList .

Листинг 3

Давайте рассмотрим простой пример работы knightTour

в действии. Для отслеживания шагов поиска вы можете обратиться к приведённым ниже рисункам. Будем полагать, что вызовы метода getConnections в строке 6 происходят в алфавитном порядке. Начнём с knightTour(0,path,A,6) .

knightTour

начинает работу с узла А (рисунок 3). Он имеет смежные вершины B и D. Поскольку в алфавите B идёт перед D, то DFS выбирает её для дальнейшего исследования, как показано на рисунке 4. Для этого рекурсивно вызывается knightTour . В смежна с C и D, поэтому следующим knightTour выбирает исследование С. Однако, как вы можете видеть из рисунка 5, вершина С — тупик без смежных белых узлов. В этот момент мы меняем цвет С обратно на белый, и вызов knightTour возвращает False . Возврат из рекурсивного вызова эффективно откатывает поиск к вершине В (см. рисунок 6). Следующая вершина в списке исследования — узел D, так что knightTour делает для неё рекурсивный вызов (см. рисунок 7). Отсюда функция может продолжить делать рекурсивные вызовы до тех пор, пока вновь не дойдёт до узла С (см. рисунок 8, рисунок 9 и рисунок 10). Однако, в этот раз проверка n limit даст отрицательный результат, поэтому мы знаем, что узлы графа закончились. Теперь можно вернуть True , показывая, что маршрут успешно проложен. Когда мы вернём список, path будет иметь значение [A,B,D,E,F,C] — порядок, в котором нужно обойти граф, чтобы посетить каждую его вершину всего один раз.

Задача про ход коня

05.01.2019, 00:16

Ход слона(задача на шахматную доску)
Задача Шахматный слон ходит по диагонали. Даны две различные клетки шахматной доски, определите.

Задача про массивы
Дано число n. Создайте массив A и заполните его по спирали, начиная с числа 0 в центральной клетке.

задача про вероятность
Генерируя 10000 случайных элементов сравнить полученное значение с ответом. Значения a и b.

Задача про электронные часы
Электронные часы показывают время в формате h:mm:ss, то есть сначала записывается количество часов.

[3]

Задача про спортсменов и результаты
Добрый день! Подскажите, пожалуйста, как можно решить такую задачу: Пользователь с клавиатуры.

Анализ задачи о ходе коня¶

Рисунок 12: Дерево поиска для задачи о ходе коня

Рисунок 13: Количество возможных ходов для каждой клетки

Мы уже видели, что количество узлов в двоичном дереве высотой N равно (2^-1) . Для дерева, чьи вершины могут иметь до восьми потомков вместо двух, число узлов намного больше. Поскольку фактор ветвления — переменная для каждого узла, количество последних можно оценить, используя среднее значение фактора. Важно отметить, что этот алгоритм экспоненциальный: (k^-1) , где (k) — средний фактор ветвления для доски. Давайте посмотрим, насколько быстро он растёт. Для доски 5х5 дерево будет в 25 уровней глубиной или N = 24, если считать первый уровень нулевым. Средний фактор ветвления равен (k = 3.8) . Таким образом, количество узлов в дереве поиска равно (3.8^-1) или (3.12 times 10^) . Для доски 6х6 (k = 4.4) , число узлов — (1.5times 10^) . Для обычной же доски 8х8 (k = 5.25) , а количество узлов (1.3 times 10^) . Конечно, поскольку существует несколько решений задачи, мы не будем исследовать каждый конкретный узел, но дробная часть выражения для количества узлов, которые нам необходимо изучить, — всего лишь постоянный множитель, что не меняет экспоненциальный характер проблемы. Мы оставляем вам в качестве упражнения попытку выразить (k) в виде функции от размера доски.+1>+1>

К счастью, есть способ ускорить случай 8х8, чтобы он работал примерно одну секунду. В приведённом ниже листинге можно найти код, ускоряющий knightTour

. Эта функция (см. листинг 4) называется orderbyAvail и будет использоваться вместо вызова u.getConnections из кода выше. Решающая строка в orderByAvail — десятая. Она гарантирует, что выбранная для дальнейшего продвижения вершина имеет наименьшее количество доступных ходов. Вы можете подумать, что на самом деле это контрпродуктивно: почему бы не выбрать узел, из которого можно совершить максимальное количество перемещений? Такой подход легко опробовать, запустив программу и вставив строку resList.reverse() сразу после сортировки.

Проблема с использованием вершины с наибольшим числом доступных ходов в качестве следующей на пути состоит в том, что конь будет пытаться пройти срединные клетки в самом начале. Когда так происходит, фигура может легко попасть в тупик у одной стороны доски, откуда не будет иметь возможность дойти до непосещённых клеток на другом её краю. С другой стороны, посещение клетки с наименьшим количеством возможных ходов подталкивает фигуру к первоочередному обходу клеток вдоль края доски. Это гарантирует, что конь посетит труднодостижимые углы раньше и сможет использовать средние клетки только при необходимости перепрыгнуть на другую сторону. Применение информации такого рода для ускорения алгоритма называется эвристикой. Люди используют эвристики каждый день для помощи в принятии решений, эвристический поиск часто применяется в области искуственного интеллекта. Данная эвристика называется алгоритмом Вансдорфа — по имени Г. Вансдорфа, опубликовавшего эту идею в 1823 году.

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

четверг, 25 апреля 2013 г.

Задача о путешествии шахматного коня

Когда то давно, мы уже рассматривали пример решения задачи рекурсивным образом, на примере задачи по размену денег. Пришло время вспомнить некоторые классические подходы и начать хотелось бы с задачи о путешествии шахматного коня.

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

Итак, каждый ход мы будем характеризовать 3-мя числами: его порядковым номером i и парой координат x, y. История ходов будет храниться в матрице списков, в соответствующей ячейке записываем порядковый номер хода. Соответственно, если в ячейке 0, значит туда мы еще не ходили.

Важно определиться с вычислением новой координаты. Можно заметить, что у коня есть 8 позиций-кандидатов (u, v) куда может прыгнуть конь.
Будем получать новые координаты прибавляя соответствующие смещения, хранящиеся в 2х списках dx, dy и отслеживать допустимость хода (находимся в пределах доски).

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

Читайте так же:  Расставание с психотерапевтом

Очень советую читать именно алгоритм, тем более Питон в этом сильно помогает. Это даст куда больше толку. чем множество лишних слов!)

Видео удалено.
Видео (кликните для воспроизведения).

Привожу пример заполнения шахматной доски.

Снова задача про ход коня

27.09.2012, 12:55

Ход коня
Здравствуйте, уважаемые форумчане. у меня возникла проблема с задачей про коня. Дело в том.

Видео удалено.
Видео (кликните для воспроизведения).

Дейтел ход коня(выход за массив)
проблема в том что конь выходит за пределы массива. Проблема в функции horsemove(); что не так.

Ход коня по шахматной доске случайным образом
Используйте генерацию случайного числа для предоставления коню возможности ходить по шахматной.

Задачка про Коня и Короля
Задана шахматная доска, на которой расставлены черные и белые фигуры, в том числе белый король и.

Создать простую программу про шахматную фигуру (коня)
Поле шахматной доски определяется парой натуральных чисел, первое из которых задаст номер.

Ход конем или поиск нового решения задачи

Все дело в том, что, когда в одном доме живут сразу несколько поколений, спокойной эту жизнь назвать сложно.
Бесконечные баталии между представителями разных поколений и младших между собой способны свести с ума даже самых морально стойких взрослых.

Со временем такой жизненный уклад начинает казаться разве что не нормой, но вот однажды, однажды кому-то из взрослых в семье приходит замечательная по своей сути идея, что что-то с этим необходимо делать, причём срочно!
Так было и в этом конкретном случае — во всем, кроме слова срочно.

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

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

Согласитесь, знакомая ситуация из разряда «а почему бы и нет» или классического, «а что, если?».

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

Здесь никто никому не даёт советов, не ставит оценок, потому и общение идёт легко и непринужденно. Согласитесь, в такой атмосфере легче думать, рассуждать, отвечать и находить отличные решения.

Итак, на первый мой вопрос, обращенный к собеседнице,–что Вас привело на встречу? — ответ был прост и лаконичен.
– Просто подумала, а вдруг удастся найти способ уладить конфликт между старшей дочерью и младшими детьми,–сказала она мне.

А дальше вопрос–ответ, вопрос–ответ, и вот в ходе беседы разворачивается следующая картина. Жила была семья:
бабушка, дедушка, мама (их дочь) и её дочь, отец ребёнка в семье не жил. Жили дружно, между собой ладили. Девочка — единственная внучка, единственная дочка и единственная племянница (была у и есть у нее еще и тетя со стороны мамы, которая живёт отдельно), ни в чем отказа не знала, все её любили и всегда спешили её чем-нибудь порадовать.

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

Забот у нее прибавилось, хлопот прибавилось, рук перестало хватать, но она выстояла, поддержала семья. С той поры прошло 4.5 года, девочка подросла, ей уже 10 лет, недавно ушёл из жизни отец моей собеседницы и соответственно дед девочки, захандрила мама (бабушка), и вдруг стало понятно, что старшей девочке трудно уживаться с младшими детьми, что она считает их виновными во всех своих бедах, в общем, не в радость ей стало такое соседство.

Спрашиваю – а как вообще складываются отношения с другими людьми у ребёнка?

– Плохо складываются, она все время чем-то или кем-то недовольна, – отвечает моя собеседница. Потом добавляет: –она раньше и в школе на всех жаловалась, очень ей нравилось, что я за неё заступаюсь.
–А что потом?
– А потом, потом я стала ей говорить, что у неё самой прекрасно получается свои конфликты со сверстниками улаживать,.
– И что в итоге?
Смеётся и говорит – жаловаться она не перестала, но знаете, что я подметила?
–Что? – спрашиваю я.
— Что конфликтов с одноклассниками стало в разы меньше, обвинять она их меньше стала, а с некоторыми и вовсе сейчас дружит.

— Выходит, все дело в том, что я уделяю теме конфликтов между старшей дочерью и младшими детьми большое внимание, а надо давать им возможность уладить их самостоятельно. Вот двойняшки сызмальства друг с другом договариваются. Нет, конечно, без ссор не обходится, но ведь это не превращается в обиду на весь мир. Наверное, все же стоит отмечать те моменты, когда ей удалось договориться с младшими без ругани, без скандала, проявить к людям уважение, – делает вывод моя собеседница.

Конечно, впереди само воплощение найденного решения в жизнь.

Но, согласитесь, ведь все большие свершения начинались с маленьких шагов. Главное, не переставайте искать новые способы и решения для реализации своих маленьких задумок и больших целей.

о ходе коня

Постановка задачи. Дана доска nxn. Конь, который ходит согласно шахматным правилам, помещается на поле с начальными координатами x0, y0. Нужно покрыть всю доску ходами коня, т.е. вычислить обход доски, если он существует, такой, что каждое поле посещается ровно один раз.

Методы решения

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

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей x/y , где x и y — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8.

Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности.

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

Со времен Эйлера известен так называемый «раздельный ход коня«; который заключается в нахождении пути по одной половине доски, его симметричном дублировании и соединении обеих путей вместе(рис.1) .

[3]

Многие решения опираются на создание симметричного маршрута, пример одного из них на рисунке 2.

Читайте так же:  Что необходимо своевременно закладывать в ребенка

Если говорить о графиках маршрутов коня, то здесь придумано множество необычных решений, изображающих различные предметы, буквы или знаки (известен даже график, посвященный Наполеону). Два достопримечательных примера такого рода приведены ниже. График одного маршрута (он является замкнутым) напоминает собой вазу, а график другого подобен цветку, части которого расположены в высшей степени симметрично( см. рис.3 и 4)

Описание алгоритмов

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

Идея алгоритма для итеративной программы заключается в следующем:

· на каждом шаге ищется фрагмент пути, начинающийся из текущей клетки и не включающий уже пройденные;

· при совершении хода из массива возможных ходов извлекается очередной элемент, который приводит в незанятую клетку, находящуюся в пределах доски;

· если ход невозможен, то происходит возврат в предыдущую клетку (отмена хода);

· поиск пути считается успешным тогда, когда номер текущего хода станет равным количеству клеток на доске. Если из начальной клетки перебраны все возможные ходы, то пути не существует.

Ниже приведена структура функции, выполняющей перебор:

for( move_num = 1 ; move_num 1 )

undo_move() ; // Отменить ход.

return ; // Обход невозможен.

Номер использованного варианта хода для каждого из ходов запоминается в массиве, размер которого выбирается в соответствии с размером доски.

Описанный алгоритм осуществляет перебор вариантов и находит решение, если оно имеется. Отсутствие решения приводит к полному перебору всех вариантов.

Оценить сложность данного алгоритма трудно. Для некоторых клеток программа работает чрезвычайно медленно уже при небольших размерах доски. Например, для доски 6 * 6 при старте из клетки (5,2) поиск пути требует более 290 миллионов возвратов.

Наиболее известное решение для задачи обхода конем — рекурсивное . При этом структура функции, выполняющей перебор, имеет следующий вид:

int find_path( int cur_x, int cur_y, int move_num )

desk_state[cur_x][cur_y] = move_num ; // Запомнить ход.

if( move_num > max_moves ) return 1 ; // Проверить завершение обхода.

// Проверить каждый возможный ход из текущей клетки.

Задача о ходе коня

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

Методы оптимизации

К одному из наиболее интересных разделов программирования относятся задачи из области искусственного интеллекта, в которых решение ищется методом проб и ошибок [1,2]. При этом имеет место перебор при поиске решения, а его продолжительность может быть сокращена за счет применения тех или иных эвристических правил (методы оптимизации).

Класс алгоритмов, позволяющий решать подобные задачи, в англоязычной литературе называется «backtracking algorithms» («алгоритмы с возвратом»). Такие алгоритмы применяются тогда, когда не подходят более «направленные» методы [3].

Давайте исследуем одну из наиболее известных задач данного класса — о ходе коня [3—5]. Она состоит в том, чтобы найти обход доски размером NxM конем, перемещающимся по правилам шахматной игры. Если такой обход существует, то каждое поле посещается только один раз (выполняется NxM-1 шагов). Здесь мы проанализируем методы оптимизации (сокращение перебора) и исследуем работу итеративной, рекурсивной и автоматной программ. Рассмотрим сначала методы оптимизации, применяемые для сокращения перебора в итеративной программе:

  • определение клеток, обход из которых невозможен (оптимизация 1);
  • выявление заблокированных клеток (оптимизация 2);
  • применение правила Варнсдорфа (оптимизация 3);
  • использование различных массивов для ходов коня (оптимизация 4).

Определение клеток, обход из которых невозможен

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

Выполнение данного условия проверяется следующей функцией:

Однако приведенное правило не охватывает всех клеток, для которых обхода не существует. Так, для доски размером 3×7 клеток помимо тех, для которых выполняется приведенное правило, обход невозможен также из клетки (2,4).

Выявление заблокированных клеток

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

Его развитием стало определение групп заблокированных клеток, связанных друг с другом, но отрезанных от остальной части доски. В рассматриваемой программе определяются группы из двух заблокированных клеток, что значительно уменьшает количество возвратов для небольших досок, а при использовании вместе с правилом Варнсдорфа — и для больших (например, размером 100×100 клеток).

Применение правила Варнсдорфа

Среди многих эвристических методов, используемых для сокращения перебора [5], правило Варнсдорфа является наиболее простым. В соответствии с ним при обходе доски шахматного коня следует каждый раз ставить на то поле, из которого он может сделать наименьшее число ходов по еще не пройденным полям. Если таких полей несколько, то можно выбрать любое из них, что может, однако, завести коня в тупик и потребовать возврата. Отметим, что наилучшим образом правило Варнсдорфа работает для угловых полей.

Использование различных массивов для ходов коня

Ходы коня могут быть заданы, например, в виде массива:

Каждый его элемент определяет один возможный ход коня и содержит изменения его координат на доске при совершении хода. При использовании различных массивов для ходов коня количество возвратов может различаться. В программе применяются пять массивов, содержащих возможные ходы коня в различном порядке. В ней задается максимальное число возвратов (GOOD_RET), и когда оно будет достигнуто, поиск пути начинается заново с использованием уже другого массива. При поиске обхода с применением последнего массива количество возвратов ограничивается значением MAX_RET. Если при совместном использовании всех предложенных методов оптимизации установить значение GOOD_RET равным единице, то для досок, близких к квадратным, можно строить обходы без единого возврата для всех клеток, из которых существует обход. Обход без единого возврата из каждой клетки не удается получить для «вытянутых» досок (например, 14×3 клетки) и для больших (например, 100×100 клеток).

Читайте так же:  О маленьких лидерах и об их родителях

Итеративная программа

Полный перебор

Идея алгоритма для итеративной программы заключается в следующем:

  • на каждом шаге ищется фрагмент пути, начинающийся из текущей клетки и не включающий уже пройденные;
  • при совершении хода из массива возможных ходов извлекается очередной элемент, который приводит в незанятую клетку, находящуюся в пределах доски;
  • если ход невозможен, то происходит возврат в предыдущую клетку (отмена хода);
  • поиск пути считается успешным тогда, когда номер текущего хода станет равным количеству клеток на доске. Если из начальной клетки перебраны все возможные ходы, то пути не существует.

Структура функции, выполняющей перебор, приведена в листинге 2.

Номер использованного варианта для каждого из ходов запоминается в массиве, размер которого выбирается в соответствии с размером доски. Описанный алгоритм выполняет перебор вариантов и находит решение, если оно имеется. Отсутствие решения приводит к полному перебору всех вариантов. В табл. 1 для иллюстрации выполнения возвратов приведен протокол обхода доски размером 3×4 клетки из клетки (2,4).

Таблица 1. Протокол обхода доски размером 3×4 клетки из клетки (2,4)

Для некоторых клеток программа работает чрезвычайно медленно уже при небольших размерах доски. Так, для доски 6×6 клеток при старте из клетки (5,2) поиск пути требует 291 077 505 возвратов.

Результаты работы программы с оптимизацией

Из работы [5] известно, что для досок размером NxM и MxN:

  • не существует ни одного обхода при N, M 7; N > 4, M > 5.

Переходя к изложению полученных результатов отметим, что они относятся к перечисленным выше методам оптимизации и эвристически выбранным массивам вариантов для хода коня. При применении других методов оптимизации [5] и иных массивов получаемые результаты могут различаться.

Для примера рассмотрим результаты обхода некоторых досок. Для доски размером 5×5 клеток приводится таблица, где указывается количество возвратов, выполненное при нахождении обхода из соответствующей клетки (табл. 2). В случае отсутствия обхода в клетке ставится символ N, а если количество возвратов превысило задаваемую в программе величину (MAX_RET = 400 000), то поиск пути прекращается, а в соответствующей клетке выводится сокращение LIM. В таблицах, построенных для метода оптимизации, когда используются различные массивы вариантов для хода коня, в клетке дополнительно дается обозначение того массива (от A до E), при применении которого обход совершался без возвратов (GOOD_RET = 1). Причем если результат был получен для первого массива, то соответствующий ему символ A не выводится.

Таблица 2. Результаты работы программы для доски размером 5 x 5 клеток

Для классической шахматной доски размером 8×8 клеток получены такие результаты:

  • для оптимизаций 1 и 2 в большинстве клеток превышено предельное значение числа возвратов. Минимальное количество возвратов в клетке (5,5) — 2502;
  • для оптимизаций 1 и 3 во всех клетках получился ноль возвратов, кроме клеток (4,1) и (6,4), где вышло 9 и 79 возвратов соответственно;
  • для оптимизаций 1-3 в клетке (6,4) было три возврата, а в остальных — ноль возвратов;
  • для оптимизаций 1-4 во всех клетках вышел ноль возвратов, а в клетке (6,4) был использован второй массив возможных ходов.

Для доски размером 100×100 клеток получены такие результаты:

  • для оптимизаций 1-3 в большинстве клеток получен ноль возвратов, а количество возвратов в остальных клетках варьируется от единицы до значений, превышающих заданный предел;
  • для оптимизаций 1-4 во всех клетках, за исключением клеток (94,24) и (94,79), вышел ноль возвратов.

Рекурсивная программа

Наиболее известное решение для задачи обхода конем — рекурсивное [2]. При этом структура функции, выполняющей перебор, имеет следующий вид:

В этой программе могут быть использованы все виды оптимизаций, описанные выше.

Автоматная программа

Если две первые программы для решения этой задачи вполне традиционны [2], то автоматные к таковым не относятся. Отметим, что автоматная программа может быть формально построена из описанной выше итеративной с помощью метода, изложенного в работе [7]. Автоматная программа может быть также формально построена и по приведенной рекурсивной программе с использованием метода, предложенного в работе [8].

Рис. 1. Схема связей автомата

Кроме того, можно создать автоматную программу путем непосредственного построения автомата по условиям задачи. На рис. 1, 2 приведены соответствующие схема связей и граф переходов автомата Мили.

Рис. 2. Граф переходов автомата

Данный автомат использует функции и переменные, определенные в итеративной программе, поэтому в нем применяются все рассмотренные методы оптимизации, а получаемые с его помощью результаты совпадают с результатами работы итеративной программы.

Упрощенный текст функции, реализующей этот автомат, приведен в листинге 4.

Что же лучше?

Совместное применение сравнительно простых и известных методов оптимизации позволило резко сократить перебор, благодаря чему удается относительно быстро находить пути в досках весьма большой размерности. Так, на компьютере, оснащенном 400-МГц Pentium II, поиск обхода из каждой клетки доски размером 200×200 клеток занял примерно 20 минут (на поиск одного обхода — около 0,03 с), причем для большинства клеток обход выполняется без единого возврата. В программе наряду с рассмотренными могли бы использоваться и другие методы оптимизации [5]. А на досках очень большого размера, например 2000×2000 клеток, нахождение даже одного пути занимает значительное время.

Как было отмечено выше, итеративная и автоматная программы выдают одинаковые результаты, однако автоматная, выделяющаяся явным выделением состояний, более понятна.

Результаты других экспериментов и полный текст программы, с помощью которой они были выполнены, будут приведены на сайтах is.ifmo.ru и www.softcraft.ru в разделе «Автоматы».

Настоящая работа выполнена на кафедре «Компьютерные технологии» С.-Петербургского государственного института точной механики и оптики (технического университета). Авторы выражают благодарность А. Э. Григорьеву, студенту этой кафедры, принимавшему участие в начале данной работы. Она выполнялась при поддержке Российского фонда фундаментальных исследований.

Источники


  1. Добрович, А. Б. Воспитателю о психологии и психогигиене общения / А.Б. Добрович. — М.: Просвещение, 2016. — 208 c.

  2. Иванова, Ольга Сила баланса. Обретение себя и стабильного брака. Баланс тела-ума. Как научиться слушать и понимать свое тело (+ CD). Путь Четырех. Часть 1. Создайте баланс стихий в своей жизни (комплект из 3 книг) / Ольга Иванова , Ошо, Дебора Липп. — М.: ИГ «Весь», 2016. — 704 c.

  3. Ричард, Витфилд. Анни Лайоннет Как выйти замуж и остаться там. Великолепные отношения. Управление эмоциями. Как сохранить семью, или Когда лучше развестись (комплект из 4 книг) / Ричард Витфилд. Анни Лайоннет, И. А. Удилова. И. И. Петрова Петрова, Александр Кичаев. — М.: ИГ «Весь», 2015. — 658 c.
Ход конем или поиск нового решения задачи
Оценка 5 проголосовавших: 1

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here