Кратчайший путь рыцаря на шахматной доске
Я практиковал для предстоящего соревнования по программированию, и я споткнулся через вопрос, в котором я просто абсолютно изумлен. Однако я чувствую, как будто это - понятие, которое я должен изучить теперь, а не скрестить пальцы, что это никогда не подходит.
В основном это имеет дело с частью рыцаря на шахматной доске. Вам дают два исходных данные: стартовое местоположение и конечное местоположение. Цель состоит в том, чтобы затем вычислить и распечатать кратчайший путь, который рыцарь может взять для получения до целевого местоположения.
Я никогда не имел дело с shortest-path-esque вещами, и я даже не знаю, где запустить. Какую логику я использую для движения о занятии этим?
P.S. Если это имеет какую-либо уместность, они хотят, чтобы Вы добавили нормальные перемещения рыцаря, также позволив этому переместиться в четыре угла квадрата, сформированного (потенциально) восемью перемещениями, которые может сделать рыцарь, учитывая, что центр квадрата является местоположением рыцаря.
3 ответа
Здесь у вас есть график, где все доступные ходы связаны (значение = 1), а недоступные ходы отключены (значение = 0), разреженная матрица будет иметь вид:
(a1,b3)=1,
(a1,c2)=1,
.....
И кратчайший путь из двух точек в график можно найти, используя http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Псевдокод со страницы wikipedia:
function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity // Unknown distance function from source to v
previous[v] := undefined // Previous node in optimal path from source
dist[source] := 0 // Distance from source to source
Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break // all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v)
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt
previous[v] := u
return dist[]
РЕДАКТИРОВАТЬ:
- как придурок, сказал, используя { {1}} http://en.wikipedia.org/wiki/A*_algorithm может быть быстрее.
- самый быстрый способ - предварительно вычислить все расстояния и сохранить их в полную матрицу 8x8. ну, я бы назвал это мошенничеством, {{1 }} и работает только потому, что проблема мала. Но иногда соревнования проверяют, насколько быстро работает ваша программа .
- Суть в том, что если вы готовитесь
к соревнованиям по программированию, вы должны знать
распространенные алгоритмы, включая алгоритм Дейкстры.
Хорошей отправной точкой является чтение {{1} }
Введение в алгоритмыISBN 0-262-03384-4. Или вы можете попробовать википедию, http://en.wikipedia.org/wiki/List_of_algorithms
Что вам нужно сделать, так это представить возможные ходы коня в виде графика, где каждая позиция на доске является узлом, а возможные ходы в другую позицию - ребром. . Алгоритм Дейкстры не нужен, потому что каждое ребро имеет одинаковый вес или расстояние (все они так же просты или коротки). Вы можете просто выполнить поиск BFS от начальной точки до конечной позиции.
Другие участники рассмотрели необходимость взаимодействия с Windows API, но я также считаю, что вы можете гарантировать (или что вы обязательно захотите быть ограниченным) разработку .NET на всю оставшуюся карьеру.
.NET - отличная рамка, но маловероятно, что она будет последней. И, как бы хорошо это ни было, это не лучший выбор для каждого проекта.
Изучение основ - и я бы рассмотрел основные основы C/C + + - открывает путь для любого количества путей, включая .NET и все, что представляет собой Next Great Framework.
-121--2182182- Это просто угол плавания = atan2 (p1.y - p2.y, p1.x - p2.x) .
Конечно, возвращаемый тип в радианах, если он нужен в градусах, просто сделайте угол * 180/PI
Да, Dijkstra и BFS дадут вам ответ, но я думаю, что шахматный контекст этой проблемы дает знания, которые могут дать решение, которое намного быстрее, чем общий алгоритм кратчайшего пути, особенно на бесконечной шахматной доске.
Для простоты рассмотрим шахматную доску как плоскость (x, y). Цель - найти кратчайший путь от (x0, y0) до (x1, y1), используя только шаги-кандидаты (+ -1, + -2), (+ -2, + -1) и (+ -2, + -2), как описано в P.S. вопроса
Вот новое наблюдение: нарисуйте квадрат с углами (x-4, y-4), Этот набор (назовите его S4) содержит 32 точки. Кратчайший путь от любой из этих 32 точек до (x, y) требует ровно двух ходов .
Кратчайший путь от любой из точек 24 в наборе S3 (определяется аналогично) до (x, y) требует не менее двух ходов .
Поэтому, если | x1-x0 | > 4 или | y1-y0 | > 4, кратчайший путь от (x0, y0) до (x1, y1) ровно на два хода больше кратчайшего пути от (x0, y0) до S4. И последняя задача может быть быстро решена с помощью простой итерации.
Пусть N = max (| x1-x0 |, | y1-y0 |). Если N > = 4, то кратчайший путь от (x0, y0) до (x1, y1) имеет шаги ceil (N/2) .