ग्राफ एल्गोरिदम शतरंज से जुड़े: के चालों में संभावित पथ

Question

मैं शतरंज से जुड़े एक एल्गोरिदम समस्या को हल करने का प्रयास कर रहा हूं।

मान लीजिए कि मेरे पास ए 8 में राजा है और इसे एच 1 (केवल अनुमति चाल के साथ) में ले जाना चाहते हैं। मैं कैसे पता लगा सकता हूं कि वास्तव में किसी भी दिए गए के कदमों को कितनी संभावनाएं (पथ) बना रही हैं? (जैसे है कितने रास्तों/संभावनाओं वहाँ अगर मैं 15 चाल के साथ एच 1 के लिए ए 8 से राजा ले जाना चाहते हैं?)

एक तुच्छ समाधान एक ग्राफ समस्या के रूप में देखते हैं और किसी भी मानक पथ खोजने एल्गोरिथ्म गिनती उपयोग करने के लिए है प्रत्येक कदम 1 लागत के रूप में। तो, मान लीजिए कि मैं 10 राजाओं में अपने राजा को ए 8 से एच 1 तक ले जाना चाहता हूं। मैं बस सभी पथों को खोजता हूं जो 10 तक की राशि हैं।

मेरा प्रश्न यह है कि यदि ऐसा करने के अन्य और चालाक और कुशल तरीके हैं? मैं भी सोच रहा था, अगर इस संख्या को खोजने के लिए कुछ और "गणितीय" और सीधा हो सकता है और इतना नहीं "एल्गोरिदमिक" और "क्रूर-बल-जैसी"?

Answer 1

यह एक सीधी-आगे ओ (एन^3) गतिशील प्रोग्रामिंग समस्या है।

Let जेड [x] [y] [k] कश्मीर कदम की चाल की संख्या बोर्ड पर स्थिति से गंतव्य (एक्स, वाई) तक पहुँचने के लिए हो सकता है: इस प्रकार

बस एक 3 डी सरणी आवंटित।

आधार मामलों रहे हैं:

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 

(वहाँ में यह करने के लिए एक तेज़ तरीका है ओ (एन^2) क्षैतिज और ऊर्ध्वाधर चाल के दो सेटों में चाल को विघटित करके और फिर इन्हें जोड़कर और संख्या की संख्या से गुणा करके । Nterleavings)

इस संबंधित सवाल देखें और जवाब: No of ways to walk M steps in a grid

Answer 2

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

दुर्भाग्य से आप उपयोग नहीं कर सकते "किसी भी मानक पथ खोजने एल्गोरिथ्म" क्योंकि आपके पथ कम से कम-पथ नहीं हो सकता है। आपको विशेष रूप से एक बेवकूफ खोज का उपयोग करना होगा जो सभी पथों (गहराई-प्रथम या चौड़ाई-पहले, उदाहरण के लिए) माना जाता है।

हालांकि, आप पर कोई परवाह नहीं है कैसे आप एक टाइल करने के लिए मिला है, तो आप एक तकनीक गतिशील प्रोग्रामिंग कहा जाता है का उपयोग कर सकते हैं। हर स्थान (i, j) के लिए, तरीकों की संख्या n चाल है (यह तरीके _{i, j} (एन) कॉल) में वहां पहुंचने के लिए:

तरीके _{i, j} (एन) = तरीके _{i-1, जे} (n-1) + तरीके _{i + 1, जे} (n-1) + तरीके _{i, j-1} (n-1) + तरीके _{मैं, जे + 1} (एन -1) + तरीके _{i + 1, j + 1} (एन -1) + तरीके _{i-1, j + 1} (n-1) + तरीके _{i + 1, जे -1} (n-1) + तरीके _{i-1, जे -1} (एन-1)

अर्थात, राजा 1 में आसन्न वर्गों में से किसी से स्थानांतरित कर सकते हैं ले जाने के:

तरीके _{i, j} (एन) = योग _{पड़ोसियों (i, j)} (तरीके _{पड़ोसी} (एन-1))

इस प्रकार आप करना चाहते हैं, उदाहरण के लिए पायथन में:

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 

ऊपर तकनीक Memoization कहा जाता है, और गतिशील प्रोग्रामिंग से लिखने के लिए है, क्योंकि आप वास्तव में जिस क्रम में आप बातें करते हैं के बारे में सोचने की जरूरत नहीं है सरल है।आप देख सकते हैं कैश बढ़ने के रूप में हम में अधिकाधिक महत्वपूर्ण प्रश्नों की एक श्रृंखला प्रदर्शन:

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

आप एक निकटता मैट्रिक्स इस्तेमाल कर सकते हैं। यदि आप अपने साथ इस तरह के मैट्रिक्स को गुणा करते हैं, तो आपको पॉइंट टू प्वाइंट से पथों की मात्रा मिलती है। उदाहरण:

ग्राफ़: पूरा K3 ग्राफ: एक < -> बी < -> सी < -> एक

मैट्रिक्स:

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

पथ लंबाई 2 के लिए: एम * एम

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

लंबाई 3 तब एम * एम * एम

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