Thuật toán đồ thị liên quan đến cờ vua: các đường dẫn có thể có trong k di chuyển

Question

Tôi đang cố gắng giải quyết một vấn đề về thuật toán liên quan đến cờ vua.

Giả sử tôi có một vị vua trong A8 và muốn chuyển nó sang H1 (chỉ với các lần di chuyển được phép). Làm thế nào tôi có thể tìm ra bao nhiêu khả năng (đường dẫn) có làm cho chính xác bất kỳ chuyển động k nào? (ví dụ: Có bao nhiêu đường dẫn/khả năng có nếu tôi muốn di chuyển vua từ A8 đến H1 với 15 lần di chuyển?)

Một giải pháp tầm thường là xem vấn đề đồ thị và sử dụng bất kỳ thuật toán tìm đường tiêu chuẩn nào mỗi di chuyển như có chi phí 1. Vì vậy, chúng ta hãy nói rằng tôi muốn di chuyển vua của tôi từ A8 đến H1 trong 10 di chuyển. Tôi chỉ đơn giản là tìm kiếm tất cả các con đường tổng cộng lên đến 10.

Câu hỏi của tôi là, nếu có cách thức thông minh và hiệu quả hơn để thực hiện việc này? Tôi cũng đã tự hỏi, nếu có thể có một cái gì đó nhiều hơn "toán học" và đơn giản để tìm số này và không phải như vậy "thuật toán" và "brute-lực giống như"?

Answer 1

Đây là vấn đề lập trình động thẳng đứng O (N^3).

Đơn giản chỉ cần gán một mảng 3D như sau:

Hãy Z [x] [y] [k] là số lần di chuyển của bước k để đạt đến đích từ vị trí (x, y) trên tàu.

Các trường hợp cơ sở là:

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 

Trường hợp đệ quy là:

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 

câu trả lời của bạn là sau đó:

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

(Có một cách nhanh hơn để làm điều này trong O (n^2) bằng cách phân tách các bước di chuyển thành hai bộ chuyển động ngang và dọc và sau đó kết hợp chúng và nhân với số của i . Nterleavings)

Xem câu hỏi liên quan này và trả lời: No of ways to walk M steps in a grid

Answer 2

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

Rất tiếc, bạn không thể sử dụng "bất kỳ thuật toán tìm đường dẫn chuẩn nào" vì đường dẫn của bạn có thể không phải là đường đi ngắn nhất. Bạn sẽ phải sử dụng cụ thể một tìm kiếm ngây thơ mà xem xét tất cả các đường dẫn (chiều sâu đầu tiên hoặc chiều rộng đầu tiên, ví dụ).

Tuy nhiên, vì bạn không quan tâm cách bạn đã vào ô xếp, bạn có thể sử dụng kỹ thuật được gọi là lập trình động. Đối với mỗi vị trí (i, j), các số cách để đạt được điều đó trong n di chuyển (chúng ta hãy gọi nó cách _{i, j} (n)) là:

cách _{i, j} (n) = cách _{i-1, j} (n-1) + cách _{i + 1, j} (n-1) + cách _{i, j-1} (n-1) + cách _{i, j + 1} (n-1) + cách _{i + 1, j + 1} (n-1) + cách _{i-1, j + 1} (n-1) + cách _{i + 1, j-1} (n-1) + cách _{i-1, j-1} (n-1)

Đó là, nhà vua có thể di chuyển từ bất kỳ các ô vuông liền kề trong 1 di chuyển:

cách _{i, j} (n) = tổng _{hàng xóm (i, j)} (cách _xóm (n-1))

vì vậy bạn muốn làm, ví dụ trong 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] 

Demo:

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

Các kỹ thuật nói trên được gọi là memoization, và đơn giản hơn để viết hơn các chương trình năng động, bởi vì bạn không cần phải thực sự suy nghĩ về thứ tự mà bạn làm việc.Bạn có thể thấy bộ nhớ cache phát triển như chúng ta thực hiện một loạt các truy vấn lớn hơn và lớn hơn:

>>> 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} 

(Trong python, cũng có thể sử dụng một @cached hoặc @memoized trang trí để tránh phải viết toàn bộ mã trong else: khối cuối cùng. Các ngôn ngữ khác có các cách khác để tự động thực hiện ghi nhớ.)

Ở trên là cách tiếp cận từ trên xuống. Đôi khi nó có thể tạo ra các ngăn xếp rất lớn (ngăn xếp của bạn sẽ tăng lên với n). Nếu bạn muốn siêu hiệu quả để tránh công việc không cần thiết, bạn có thể thực hiện cách tiếp cận từ dưới lên, nơi bạn mô phỏng tất cả các vị trí mà nhà vua có thể, trong 1 bước, 2 bước, 3 bước, ...:

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 

Demo:

>>> 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

Bạn có thể sử dụng một ma trận kề. Nếu bạn nhân một ma trận với chính nó, bạn sẽ nhận được số lượng đường dẫn từ điểm đến điểm. Ví dụ:

Graph: đồ thị đầy đủ K3: Một < -> B < -> C < -> Một

Matrix:

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

Paths cho chiều dài 2: M * M

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

Độ dài 3 sau đó sẽ là M * M * M

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