Графический алгоритм с участием шахмат: возможные пути в k ходах

Question

Я пытаюсь решить проблему алгоритма с участием шахмат.

Предположим, у меня есть король в A8 и вы хотите переместить его в H1 (только с разрешенными ходами). Как я мог узнать, сколько возможностей (путей) делает именно любые заданные k шагов? (например, как много путей/возможностей есть, если я хочу, чтобы переместить король от A8 до H1 с 15 ходов?)

Одно тривиальным решением, чтобы видеть это как проблема графика и использовать любой стандартный путь найти подсчет алгоритма каждое движение имеет стоимость 1. Итак, допустим, я хочу переместить моего короля с A8 на H1 за 10 ходов. Я бы просто искал все пути, которые суммируются до 10.

Мой вопрос в том, есть ли другие более умные и эффективные способы сделать это? Мне также интересно, может ли быть что-то более «математическое» и простое найти это число, а не «алгоритмическое» и «грубое»?

Answer 1

Это проблема динамического программирования O (N^3) в прямом направлении.

Просто назначить 3D массив следующим образом:

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

Базовые случаи:

foreach x in 0 to 7, 
    foreach y in 0 to 7, 
     Z[x][y][0] = 0 // forall x,y: 0 ways to reach H1 from 
         // anywhere else with 0 steps 

Z[7][7][0] = 1 // 1 way to reach H1 from H1 with 0 steps 

Рекурсивный случай:

foreach k in 1 to K, 
    foreach x in 0 to 7, 
     foreach y in 0 to 7, 
      Z[x][y][k+1] = Z[x-1][y][k] 
       + Z[x+1][y][k] 
       + Z[x][y-1][k] 
       + Z[x][y+1][k] 
       + ...; // only include positions in 
        // the summation that are on the board 
        // and that a king can make 

Ваш ответ тогда:

return Z[0][0][K]; // number of ways to reach H1(7,7) from A8(0,0) with K moves 

(Существует более быстрый способ сделать это в O (n^2), разложив движения на два набора горизонтальных и вертикальных движений, а затем объединив их и умножив на число i . nterleavings)

Смотрите этот родственный вопрос и ответ: No of ways to walk M steps in a grid

Answer 2

.......E <-end 
........ 
........ 
........ 
........ 
........ 
........ 
S....... <-start 

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

Однако, потому что вы не заботитесь , насколько вы получили в плитке, вы можете использовать технику, называемую динамического программирования. Для каждого места (I, J), то число способов попасть в п ходов (давайте назовем его пути _{I, J} (п)) является:

пути _{I, J} (п) = способы _{I-1, J} (п-1) + способы _{+ 1, J} (п-1) + способы _{I, J-1} (п-1) + способы _{я, j + 1} (n-1) + пути _{i + 1, j + 1} (n-1) + пути _{i-1, j + 1} (n-1) + пути _{I + 1, J-1} (п-1) + способами _{I-1, J-1} (п-1)

То есть, король может перемещаться из любого из смежных квадратов в 1 двигаться:

пути _{I, J} (п) = сумма _{соседей (I, J)} (способы _{соседних} (п-1))

Таким образом, вы могли бы сделать, например, в python:

SIZE = 8 

cache = {} 
def ways(pos, n): 
    r,c = pos # row,column 
    if not (0<=r<SIZE and 0<=c<SIZE): 
     # off edge of board: no ways to get here 
     return 0 
    elif n==0: 
     # starting position: only one way to get here 
     return 1 if (r,c)==(0,0) else 0 
    else: 
     args = (pos,n) 
     if not args in cache: 
      cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1) 
     return cache[args] 

Демо:

>>> ways((7,7), 15) 
1074445298 

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

>>> cache 
{} 
>>> ways((1,0), 1) 
1 
>>> cache 
{((1, 0), 1): 1} 
>>> ways((1,1), 2) 
2 
>>> cache 
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0} 
>>> ways((2,1), 3) 
5 
>>> cache 
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5} 

(В питона, можно также использовать @cached или @memoized декоратора, чтобы избежать необходимости писать весь код в последнем else: блоке. Другие языки имеют другие способы автоматического выполнения заметок.) ​​

Вышеупомянутый подход был сверху вниз. Иногда он может создавать очень большие стеки (ваш стек будет расти с n). Если вы хотите быть суперэффективным, чтобы избежать ненужной работы, вы можете сделать подход снизу вверх, где вы имитируете все позиции, которые может быть королем, для 1 шага, 2 шага, 3 шага, ...:

SIZE = 8 
def ways(n): 
    grid = [[0 for row in range(8)] for col in range(8)] 
    grid[0][0] = 1 

    def inGrid(r,c):    
     return all(0<=coord<SIZE for coord in (r,c)) 
    def adjacentSum(pos, grid): 
     r,c = pos 
     total = 0 
     for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]: 
      delta_r,delta_c = neighbor 
      (r2,c2) = (r+delta_r,c+delta_c) 
      if inGrid(r2,c2): 
       total += grid[r2][c2] 
     return total 

    for _ in range(n): 
     grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)] 
     # careful: grid must be replaced atomically, not element-by-element 

    from pprint import pprint 
    pprint(grid) 
    return grid 

Демо:

>>> ways(0) 
[[1, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(1) 
[[0, 1, 0, 0, 0, 0, 0, 0], 
[1, 1, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(2) 
[[3, 2, 2, 0, 0, 0, 0, 0], 
[2, 2, 2, 0, 0, 0, 0, 0], 
[2, 2, 1, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(3) 
[[6, 11, 6, 4, 0, 0, 0, 0], 
[11, 16, 9, 5, 0, 0, 0, 0], 
[6, 9, 6, 3, 0, 0, 0, 0], 
[4, 5, 3, 1, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

>>> ways(4) 
[[38, 48, 45, 20, 9, 0, 0, 0], 
[48, 64, 60, 28, 12, 0, 0, 0], 
[45, 60, 51, 24, 9, 0, 0, 0], 
[20, 28, 24, 12, 4, 0, 0, 0], 
[9, 12, 9, 4, 1, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0, 0, 0, 0]] 

Answer 3

Вы можете использовать матрицу смежности. Если вы умножаете такую ​​матрицу на себя, вы получаете количество путей от точки к точке. Пример:

График: полная К3 графа: а < -> В < -> С < -> A

Матрица:

[0 ; 1 ; 1] 
[1 ; 0 ; 1] 
[1 ; 1 ; 0] 

Дорожки 2 Длина: М * М

[2 ; 1 ; 1] 
[1 ; 2 ; 1] 
[1 ; 1 ; 2] 

Длина 3 будет тогда M * M * M

[2 ; 3 ; 3] 
[3 ; 2 ; 3] 
[3 ; 3 ; 2]