2016-12-07 14 views
1

У меня есть следующая проблема.Подсчет количества движений от A до B

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

Я должен найти кратчайший путь в то время как подчиняться правилам движения рыцаря в шахматах (в форме L движется) и подсчитать число ходов:

так:

enter image description here У меня пробовал разные вещи, но безуспешно.

Что я могу сделать?

+1

Это английский сайт, поэтому не используйте другие языки. См. Ответы на этот вопрос: http://stackoverflow.com/questions/2339101/knights-shortest-path-chess-question – Pavel

ответ

4

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

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

1

Я не проверял в Интернете, чтобы найти какой-либо эвристики для этого, но я могу дать вам несколько советов внутри об этом:

Каждый квадрат по диагонали фактической площади рыцаря можно достичь только в двух ходов , при условии, что рыцарь не находится в углу. Квадрат (x, y) на квадраты (x-1, y + 1), (x + 1, y + 1), (x + 1, y-1) и (x-1, y-1) принимает 2 движется;

  • Квадраты, сверху, справа и слева от фактического квадрата, занимают 3 хода; Каждый квадрат на диагонали фактического квадрата с одним квадратом между ними (например, фактический квадрат = c4, целевой квадрат a6), занимает 4 хода.

  • Каждый квадрат на диагонали фактического квадрата с двумя квадратами между ними (например, фактический квадрат = c4, целевой квадрат f7) занимает всего 2 хода.

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

  • Количество шагов, которые берет коня из данного положения в другое в 8x8 плате при макс 6.

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

Этот answer от http://math.stackexchange.com также может помочь вам. Вы также можете найти множество хороших ответов here, с решениями O (1).

+1

«Каждый квадрат на диагонали фактического квадрата Рыцаря может быть доступен всего за два хода». мммм ... достигнуть A1 от B2 в 2 ходах. –

+0

yep, если рыцарь не находится в углу xD – dreamcrash

0

динамического программирования решение имеет описание рекуррентную:

DP(x,y)= 1 + min(
       DP(x-2,y-1),DP(x-2,y+1),DP(x+2,y-1),DP(x+2,y+1), 
       DP(x-1,y-2),DP(x-1,y+2),DP(x+1,y-2),DP(x+1,y+2) 
     ); 

Если я не ошибаюсь, потребуется O (N^2) к memoize.

Смежные вопросы