您好，我目前正在 Geeksforgeeks https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1閱讀騎士之旅問題， 我正在自己測驗代碼，當我更改騎士移動的順序時代碼
let xMove = [ 2, 1, -1, -2, -2, -1, 1, 2 ];
let yMove = [ 1, 2, 2, 1, -1, -2, -2, -1 ];
對此
let xMove = [1,1,-1,-1,2,2,-2,-2]
let yMove = [2,-2,-2,2,-1,1,-1,1]
并且問題似乎無法解決。這個問題是否依賴于騎士移動的順序或它的原因是什么？就我的理解，遞回會搜索所有可能的動作，所以應該沒有區別吧？
uj5u.com熱心網友回復：
......問題似乎沒有解決
這正是維基百科上也提到的問題：
除了最小的棋盤外，對騎士之旅進行蠻力搜索是不切實際的。例如，在一塊 8×8 的棋盤上大約有 4×10 51 個可能的移動序列，在如此大的集合上執行操作遠遠超出現代計算機（或計算機網路）的能力。
你從 GfG 參考的實作中的移動順序是一個幸運的順序。對于您測驗過的訂單，回溯的數量是巨大的。人們可以想象在路徑的最開始采取正確的行動是至關重要的。如果早期的移動之一是錯誤的，那么在遞回樹的更深節點中將發生大量的回溯。
有一種啟發式方法可以大大減少要考慮的移動次數，大多數情況下只有 1：這是Warnsdorff 的規則：
騎士被移動，以便它總是前進到騎士前進最少的方格。在計算每個候選方格的向前移動次數時，我們不計算重新訪問任何已經訪問過的方格的移動次數。可以有兩個或多個選擇，向前移動的次數相等；打破這種聯系的方法有很多種，...
在 8×8 板的情況下，實際上沒有必要打破平局：回溯將解決錯誤的選擇。但是由于現在搜索樹很窄，這不會導致很多回溯，即使我們很不走運。
這是一個可運行的 JavaScript 代碼段的實作。它有意隨機打亂移動串列，并在需要回溯時列印“回溯”，以便您可以嘗試不同的運行。這將表明，這總能找到平均幾乎沒有任何回溯的解決方案：
class Solver {
constructor(size) {
this.size = size;
this.grid = Array.from({length: size}, () => Array(size).fill(-1));
}
toString() {
return this.grid.map(row =>
row.map(i => (i "").padStart(2, "0")).join(" ")
).join("\n");
}
liberty(x, y) {
// Count the number of legal moves
return [...this.getMoveList(x, y)].length;
}
*getMoveList(x, y) {
// Get list of legal moves, in random order
let moves = [[1, 2], [1, -2], [-1, -2], [-1, 2],
[2, -1], [2, 1], [-2, -1], [-2, 1]];
// Shuffle moves randomly
for (var i = moves.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i 1));
[moves[i], moves[j]] = [moves[j], moves[i]]; // Swap
}
// Yield the valid positions that can be reached
for (let [moveX, moveY] of moves) {
if (this.grid[x moveX]?.[y moveY] == -1) {
yield [x moveX, y moveY];
}
}
}
getBestMoveList(x, y) {
// Get list of move(s) that have the least possible follow-up moves
let minLiberty = 100000;
const bestMoves = [];
// Consider every legal move:
for (let [nextX, nextY] of this.getMoveList(x, y)) {
let liberty = this.liberty(nextX, nextY);
if (liberty < minLiberty) {
minLiberty = liberty;
bestMoves.length = 0; // Empty the array
}
if (liberty == minLiberty) bestMoves.push([nextX, nextY]);
}
if (Math.random() >= 0.5) bestMoves.reverse();
return bestMoves;
}
solve(x, y, moveCount=0) {
this.grid[x][y] = moveCount ;
if (moveCount == this.size * this.size) return true;
// Try all of the BEST next moves from the current coordinate x, y
for (let [nextX, nextY] of this.getBestMoveList(x, y)) {
if (this.solve(nextX, nextY, moveCount)) return true;
}
console.log("backtrack");
this.grid[x][y] = -1;
return false;
}
}
// Driver code
const solver = new Solver(8);
let success = solver.solve(0, 0);
console.log(success ? solver.toString() : "Solution does not exist");轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/391152.html
上一篇：C 中的遞回函式呼叫