一個八*八的西洋棋盤 若我的騎士在(8,8)的位置 有兩個敵軍分別在(3,2)(4,4)的位置 而我方補給在(7,3)的位置 若要找出最短消滅兩個敵軍的最短路徑...請大大幫幫我阿 快想破頭了...再消滅完第一個敵軍後要先前往我方補給的位置來補給後 才能再去殺第二個敵軍喔...記得唷 是騎士的走法喔就是目自行走法 跟我門軍棋裡面的馬是一樣的 謝謝囉 感激不進

伱的問題再演算法書中應該找的到 這是我書上的皇后問題 由於篇幅蠻大的我只key其中的一小部分 希望對你有幫助 The Backtracking Algorithm for the n-Queens Problem: (cont.) The promising function must check whether two queens are in the same column or diagonal. If let col(i) be the column where the queen in the ith row is located, then, to check whether the queen in the kth row is in the same column, we need to check whether col(i) = col(k). Next check the diagonal, for the queen threatening from the left, the difference in the column is the same as the difference in the rows. These are examples of the general result that if the queen in the kth row threatens the queen in the ith row along one of its diagonals, then col(i) – col(k) = i – k or col(i) – col(k) = k – i --------------------------------------------------------------------- P: Position n queens on a chessboard so that no two are in the same row, column, or diagonal. I: positive integer n. O: all possible ways n queens can be placed on an nxn chessboard so that no two queens threaten each other. Each output consists of an array of integers col indexed from 1 to n, where col[i] is the column where the queen in the ith row is placed. ------------------------------------------------------------------- void queens(index i) { index j; if(promising(i)) if(i == n) cout << col[1] through col[n]; else for(j=1;j<=n;j ) { col[i 1]=j; queens(i 1); } } ------------------------------------------------------------------- bool promising(index i) { index k; bool switch; k = 1; switch = true; while(k < i && switch) { if(col[i] == col[k] || abs(col[i] – col[k]) == i – k) switch = false; k ; } return switch; } ~ 勿在浮沙上面築高塔 ~

------
~ 勿在浮沙上面築高塔 ~

這個問題我想在AI(人工智慧)的書裏會比較找得到喔 我記得有個最短路徑演算法是專門解這種問題的，希望對你有點小幫助

我又想了一下你的問題，你的問題可以做個簡化： 其實只是在找２種最短路徑： (8,8)→(3,2)→(7,3)→(4,4) 或是 (8,8)→(4,4)→(7,3)→(3,2) 2種 由於騎士的走法是可逆的， 因此(3,2)→(7,3)和(7,3)→(3,2)這２種最短路徑走法是一樣的 同理(4,4)→(7,3)和(7,3)→(4,4)也是一樣的 那麼，最短路徑就決定於(8,8)→(3,2)或(8,8)→(4,4)這二者了 這樣子，只要考慮這４個點中，任２點的最短路徑，有沒有比較簡化一點？ 再來，騎士每次可以走的路徑，有８個方向，最笨的方法你可以用搜尋的， 舉例來說，騎士走第一步，座標會有８種變化 x 1,y 2 x 1,y-2 (以下省掉x和y) 2,-1 2, 1 -1,-2 -1, 2 -2, 1 -2,-1 那麼走第２步呢？就是上面8種再走一次， 如走了x 1,y 2後，再走一次，就是x 2,y 4，或是 1, 2→ 1,-2，也就是 2, 0 1, 2→ 2,-1，也就是 3, 1 ... 就有8*8=64種了(其實扣除掉走回到前一步的選擇，只有8*7=56種) 第3步最多就是8的3次方 第4步最多就是8的4次方 ... 直到走到目標點上，西洋棋不過8*8的空間可走，也就是說，最多8步，一定可以走到，所以用最笨的方法，也不過一千多萬次，就可以解出來了，你可以再加上一些限制，像是不可以走出棋盤、不可以走到曾走過的點，那麼絕對可以很快就解出來的。 以現在電腦的速度，這個複雜度絕對可以負荷得了，而且我想在不到一秒之內，應該就解出來了吧？ 希望這樣寫，對你有點幫助。