Задача с конями на шахматной доске

@Ника16 · Регистрация: 30.09.2016

Студворк — интернет-сервис помощи студентам

Помогите, пожалуйста, разобраться с алгоритмом задачи. Долго думаю и не знаю с чего вообще начинать.

На шахматной доске размером N*N находятся некоторое количество коней. Их изначальные координаты передаются на вход приложению. Эти кони ходят одновременно и стремятся сойтись в одной точке за минимальное количество ходов. Несколько коней могут находиться в одной точке в любой момент времени. Программа должна рассчитать оптимальную точку, в которой они сойдутся, и минимально возможное количество ходов до этого. Если таких точек несколько, необходимо вывести их все.
В этом задании отдельные кони могут пропускать ход.

@wingblack · 01.12.2018, 20:57

Нужно уточнение - нужно найти клетку до которой максимальное количество шагов от стартовой позиции любого коня будет минимально?
Могу предложить простое но не самое быстрое решение.
Берем матрицу Н*Н, заполняем числами "-1", на ней делаем обход в ширину для первого коня - клетки матрицы должны содержать минимальное количество шагов за которое конь дойдет до этой клетки, стартовую позицию берем за ноль.
Делаем такую же для следующего коня, числа из неё прибавляем к числам в первой матрице, если в одной из матриц стоит число "-1", то оно должно быть в первой матрице.
И так далее - считаем расстояния полного обхода для коня, прибавляем к первой матрице, оставляя числа "-1"
Ответом будет та ячейка первой матрицы, у которой наименьшее значение, но не -1.

@TheCalligrapher · 02.12.2018, 08:24

(Специально зашел, чтобы найти этот вопрос и здесь.)

Задача недостаточно ясно сформулирована. Что такое "ход"? Считаются количество "тактов", в течение которых все кони одновременно делают (или не делают) ход? Или "ходом" считается каждое индивидуальное перемещение каждого коня?

* Если задача состоит в минимизации количества "тактов" во время каждого из которых все кони одновременно делают ход, то это фактически задача нахождения минимальной охватывающей окружности в "метрике коня". Ее центр (возможно - центры, в дискретном случае) и будет той точкой, к которой должны сойтись кони. Наверное можно адаптировать алгоритм Эмо Велзла для дискретной задачи в "метрике коня".

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

Начиная с доски 5x5 для значения "лошадиного" расстояния существуют аналитические выражения. В общем, если N не может быть очень большим, то можно просто построить полную матрицу значений целевой функции, а затем найти оптимальные точки для любого способа подсчета ходов. Для досок меньшего размера значения расстояния можно предрассчитать заранее. Скажем алгоритмом Флойда-Уоршелла.

@Excalibur921 · 02.12.2018, 13:24

Сообщение от TheCalligrapher

существуют аналитические выражения.

там минимизация ходов перемещение из P в Q?

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

@TheCalligrapher · 02.12.2018, 19:40

Сообщение от wingblack

[...]максимальное количество шагов от стартовой позиции любого коня будет минимально?[...]
Делаем такую же для следующего коня, числа из неё прибавляем к числам в первой матрице,[...]

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

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

@wingblack · 02.12.2018, 20:12

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

@TheCalligrapher · 02.12.2018, 20:32

Сообщение от Excalibur921

считаем при каких коордианатх коней расстояние между ними минимально

Что именно вы имеете в виду под "расстояние между ними минимально" для случая M коней? Сумму/максимум всевозможных попарных расстояний? Скорее всего, такой алгоритм даже сможет найти какую-то оптимальную точку схождения коней. А вот как не упустить при этом все такие точки?

Алгоритм wingblack решает задачу за O(N²M). Ваш вариант - за O(M²K) , где K - количество итераций до схождения (игнорируя пока необходимость найти все точки).

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

Добавлено через 9 минут

Сообщение от wingblack

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

Ну, еще раз: матрицу полного обхода из (0, 0) строить вообще не надо - как уже не раз было сказано выше, для всех значений из этой матрицы есть готовая прямая формула (см. ссылку на "Квант"). Эта формула не работает для четырех клеток возле начального угла, но это легко исправить просто подставив вручную требуемые значения.

Однако для досок меньше чем 5x5 также не работает правило переноса координат: для вычисления расстояния между двумя конями уже нельзя просто помещать одного из коней в угол. Но эта проблема тоже легко решается: для такой маленькой доски действительно можно просто заранее вычислить матрицу расстояний "от всех до всех" хоть алгоритмом Флойда-Уоршелла.

@renat_dmitriev · 02.12.2018, 22:34

Формула расчета ходов между двумя точками:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countMoves(p1, p2) {
 
    let diffX = Math.abs(p2.x - p1.x)
    let diffY = Math.abs(p2.y - p1.y)
 
    if(diffX === 2 && diffY === 2) return 4
    else if(diffX + diffY === 1) return 3
    else if(diffX === 1 && diffY === 1 &&
        (p1.x % N < 2 && p1.y % N < 2
            || p2.x % N < 2 && p2.y % N < 2)) return 4
 
 
    let moves = Math.ceil(Math.max(
        (diffX + diffY) / 3,
        diffX / 2,
        diffY / 2
    ));
 
    if((diffX + diffY) % 2 !== moves % 2) moves++
 
    return moves;
}

1) Далее срединную точку между наименьшим и наибольшим x всех коней и наименьшим и наибольшим y, считаем самое большое кол-во ходов для всех коней до этой точки, берем это число за основу.

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

3) Массив клеток с минимальным значением и будет ответом на вопрос.

@Excalibur921 · 02.12.2018, 22:41

Сообщение от TheCalligrapher

как не упустить при этом все такие точки?

Тут хитрая задачка, например оценка расстояний покажет что выгодный ход #1, когда через N итераций окажется что выгодный был другой ход +это может быть на всех конях в случайный момент.
Это наверно многовариантные расчеты…наверно только перебор.

@wingblack · 02.12.2018, 23:56

Сообщение от TheCalligrapher

Ну, еще раз: матрицу полного обхода из (0, 0) строить вообще не надо - как уже не раз было сказано выше, для всех значений из этой матрицы есть готовая прямая формула (см. ссылку на "Квант"). Эта формула не работает для четырех клеток возле начального угла, но это легко исправить просто подставив вручную требуемые значения.

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

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

@TheCalligrapher · 03.12.2018, 00:02

Сообщение от renat_dmitriev

Формула расчета ходов между двумя точками:

Ну, опять же, с той же оговоркой, что для маленьких досок (меньше 5x5) ваша формула (как и остальные) будет работать неправильно. Для N=4 расстояние от (0,0) до (3,0) равно 5. Ваша формула дает 3.

Также в вашей формуле содержится ошибка: на доске любого размера расстояние от (2, 2) до (1, 1) получается 4 вместо 2.

Сообщение от renat_dmitriev

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

Опять же вопрос о том, что имеется в виду под "ходами". Если нужно считать суммарное количество ходов каждого коня, то точки минимума не обязательно будут находиться "рядом".

@renat_dmitriev · 03.12.2018, 00:08

Сообщение от TheCalligrapher

Ну, опять же, с той же оговоркой, что для маленьких досок (меньше 5x5) ваша формула будет работать неправильно.

Формула не зависит от размера доски, кроме той части, что вычисляет расстояние соседних клеток по диагонали, когда одна из них в углу.

Также в вашей формуле содержится ошибка: на доске любого размера расстояние от (2, 2) до (1, 1) получается 4 вместо 2.

1,1 на доске любого размера - угловая точка, поэтому ее расстояние до 2,2 всегда будет 4.

Сообщение от TheCalligrapher

Опять же вопрос о том, что имеется в виду под "ходами". Если нужно считать суммарное количество ходов каждого коня, то точки минимума не обязательно будут находиться "рядом".

Судя по фразе "В этом задании отдельные кони могут пропускать ход." считается именно моя трактовка, иначе эта фраза не имеет смысла. Поэтому вычисляем самого дальнего коня.

@TheCalligrapher · 03.12.2018, 00:34

Сообщение от renat_dmitriev

1,1 на доске любого размера - угловая точка, поэтому ее расстояние до 2,2 всегда будет 4.

Ну то есть вы нумеруете клетки от (1,1), а не от (0,0)? Такие моменты надо оговаривать. Вопрос снимается.

Сообщение от renat_dmitriev

Формула не зависит от размера доски, кроме той части, что вычисляет расстояние соседних клеток по диагонали, когда одна из них в углу.

Не совсем понятно, что вы имеете в виду под "соседних клеток по диагонали". При N=4 ваша формула неправильно вычисляет расстояние от (1, 1) до (4, 1) (соседние углы), как я уже сказал выше. Правильный ответ - 5, ваша формула дает 3. На "соседние клетки по диагонали" это, вроде, не похоже.

Сообщение от renat_dmitriev

Судя по фразе "В этом задании отдельные кони могут пропускать ход." считается именно моя трактовка, иначе эта фраза не имеет смысла.

Это почему это она не имеет смысла в трактовке "суммарного количество ходов"? Представьте себе два коня на расстоянии 2. За два хода (в трактовке суммарного количества индивидуальных ходов), кони могут либо встретиться посередине, либо один может прийти "в гости" к другому. Это даст нам три точки в результате.

Если бы коням не разрешалось пропускать ход, то результатом была бы только одна точка - посередине.

Так что ни о каком "не имеет смысла" речи быть не может.

@renat_dmitriev · 03.12.2018, 00:45

Сообщение от TheCalligrapher

Ну то есть вы нумеруете клетки от (1,1), а не от (0,0)? Такие моменты надо оговаривать. Вопрос снимается.

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

Сообщение от TheCalligrapher

Не совсем понятно, что вы имеете в виду под "соседних клеток по диагонали". При N=4 ваша формула неправильно вычисляет расстояние от (1, 1) до (4, 1) (соседние углы), как я уже сказал выше.

Да, это я не учел.

Сообщение от TheCalligrapher

Если бы коням не разрешалось пропускать ход, то результатом была бы только одна точка - посередине.

Соглашусь.

@Shamil1 · 03.12.2018, 13:26

Нужно для каждого коня найти список точек, в которые он может попасть за 1 ход. Если пересечение таких списков ненулевое, то это ответ. Иначе повторяем для 2 ходов. И так далее.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Ника16 1 / 1 / 0 Регистрация: 30.09.2016 Сообщений: 7

	Задача с конями на шахматной доске 01.12.2018, 16:28. Показов 5166. Ответов 14 Метки нет (Все метки) Помогите, пожалуйста, разобраться с алгоритмом задачи. Долго думаю и не знаю с чего вообще начинать. На шахматной доске размером N*N находятся некоторое количество коней. Их изначальные координаты передаются на вход приложению. Эти кони ходят одновременно и стремятся сойтись в одной точке за минимальное количество ходов. Несколько коней могут находиться в одной точке в любой момент времени. Программа должна рассчитать оптимальную точку, в которой они сойдутся, и минимально возможное количество ходов до этого. Если таких точек несколько, необходимо вывести их все. В этом задании отдельные кони могут пропускать ход. 1

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	01.12.2018, 20:57
	Нужно уточнение - нужно найти клетку до которой максимальное количество шагов от стартовой позиции любого коня будет минимально? Могу предложить простое но не самое быстрое решение. Берем матрицу Н*Н, заполняем числами "-1", на ней делаем обход в ширину для первого коня - клетки матрицы должны содержать минимальное количество шагов за которое конь дойдет до этой клетки, стартовую позицию берем за ноль. Делаем такую же для следующего коня, числа из неё прибавляем к числам в первой матрице, если в одной из матриц стоит число "-1", то оно должно быть в первой матрице. И так далее - считаем расстояния полного обхода для коня, прибавляем к первой матрице, оставляя числа "-1" Ответом будет та ячейка первой матрицы, у которой наименьшее значение, но не -1. 1

@TheCalligrapher Вездепух 12919 / 6787 / 1817 Регистрация: 18.10.2014 Сообщений: 17,169
	02.12.2018, 08:24
	(Специально зашел, чтобы найти этот вопрос и здесь.) Задача недостаточно ясно сформулирована. Что такое "ход"? Считаются количество "тактов", в течение которых все кони одновременно делают (или не делают) ход? Или "ходом" считается каждое индивидуальное перемещение каждого коня? * Если задача состоит в минимизации количества "тактов" во время каждого из которых все кони одновременно делают ход, то это фактически задача нахождения минимальной охватывающей окружности в "метрике коня". Ее центр (возможно - центры, в дискретном случае) и будет той точкой, к которой должны сойтись кони. Наверное можно адаптировать алгоритм Эмо Велзла для дискретной задачи в "метрике коня". * Если же количество ходов считается как сумма количества индивидуальных ходов каждого коня, то это похоже на поиск геометрической медианы. Ее можно искать методом градиентного спуска, как в алгоритме Вайзфельда. Однако из-за дискретности задачи можно выполнять итерации не по формуле Вайзфельда, а просто в лоб в окрестности текущего приближения. Начиная с доски 5x5 для значения "лошадиного" расстояния существуют аналитические выражения. В общем, если N не может быть очень большим, то можно просто построить полную матрицу значений целевой функции, а затем найти оптимальные точки для любого способа подсчета ходов. Для досок меньшего размера значения расстояния можно предрассчитать заранее. Скажем алгоритмом Флойда-Уоршелла. 1

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	02.12.2018, 20:12
	Ну да, так то можно строить матрицу полного обхода один раз (поместив коня в угол), а дальше каждый раз ее использовать, лишь поставляя правильные индексы. 0

@Shamil1 Модератор 3132 / 2279 / 469 Регистрация: 26.03.2015 Сообщений: 8,870
	03.12.2018, 13:26
	Нужно для каждого коня найти список точек, в которые он может попасть за 1 ход. Если пересечение таких списков ненулевое, то это ответ. Иначе повторяем для 2 ходов. И так далее. 0