3

バックトラッキングを使用してナイツ ツアーの問題を解決するアルゴリズムを JavaScript で記述しようとしていますが、うまくいきません。基本的に、この関数は、各移動の場所を含むVisitedという配列を出力することになっています。ただし、配列には位置が追加されず、[[0,0]] のままです。これが私のコードです。どんな手掛かり？

var unit = 75;

function m1(position) { position[0] += unit; position[1] += 2*unit; return [position[0],position[1]]}
function m2(position) { position[0] -= unit; position[1] += 2*unit; return [position[0],position[1]]}
function m3(position) { position[0] += 2*unit; position[1] += unit; return [position[0],position[1]]}
function m4(position) { position[0] -= 2*unit; position[1] += unit; return [position[0],position[1]]}
function m5(position) { position[0] += unit; position[1] -= 2*unit; return [position[0],position[1]]}
function m6(position) { position[0] -= unit; position[1] -= 2*unit; return [position[0],position[1]]}
function m7(position) { position[0] += 2*unit; position[1] -= unit; return [position[0],position[1]]}
function m8(position) { position[0] -= 2*unit; position[1] -= unit; return [position[0],position[1]]}

var moves = [m1, m2, m3, m4, m5, m6, m7, m8];   
var currentPosition = [0, 0];
var visited = [currentPosition];

function knightour(currentPosition)
{

    var j; 

    if (promising(currentPosition))
    {

        if (visited.length == 64)
        {
            return visited;
        } 
        else 
        {
            for (j=0; j<moves.length; j++)
            {
                context.drawImage(knight, currentPosition[0], currentPosition[1]);
                alert("NEXT");
                visited.push(moves[j](currentPosition));
                knightour(currentPosition);
            }
        }
    } 
}  

function promising(currentPosition)
{
    if (currentPosition[0] < 600 && currentPosition[0] >= 0 &&
        currentPosition[1] < 600 && currentPosition[1] >= 0 &&
        isVisited(currentPosition, visited))
        {
        return true;
    } else {
        return false;
    }

} 

function isVisited(position, visited)               // visited is an array of size n of array of size 2 ([x,y])
{                                                       // currentPosition is an array of size 2 ([x,y])
    for (var i=0; i<visited.length; i++)
    {
        if (position[0] == visited[i][0] && position[1] == visited[i][1])
        {
            return true;
        }
    }
    return false;

}

ありがとうございました。

4

1 に答える 1

3

後退する必要があります。バックトラッキング アルゴリズムを整理することすらできず、表示するボードとアルゴリズムが必要とするボードをすでに混同しているのです。最善の策は、最初からやり直してアルゴリズムを解いてから、すべての表示について心配することです。その考えで、最初に疑似コードでアルゴリズムを解決し、次にその疑似コードを JavaScript に変換する必要があります。(ヒント: あなたのコードでは、現在の位置を決して変更していないようです。)

全体的なプロセスは次のようになります。

findAllKnightsTours:
  for every board position
    set path = empty
    set board = all false
    findKnightsTour(currentPosition, path, board)

スタックとしてパスを持つことは素晴らしいことです。スクエアが訪問されたかどうかを毎回検索するのは面倒なので、別の「ボード」を使用します。ボードはブール値のマトリックス (false == 訪問なし、true = 訪問済み) である必要がありますが、簡単にするために単純な配列を使用します。

findKnightsTour(position, path, board):
  push position onto path
  set board[position] to true

  if path.length == 64
    print out path
  else
    for each of the eight moves
      next = calculate new position based on move
      if validPosition(next, board)
        findKnightsTour(next, path, board)

  set board[position] to false
  pop position off path

validPosition ルーチンは、位置がボードの制限内にあり、現在アクセスされていない (つまり、true) かどうかを確認します。

このルーチンを見ると、現在の位置をパスとボードに追加し、何かを実行してから、パスとボードからそれを削除することがわかります。これは、アルゴリズムのバックトラック部分です。状態を保存し、何かを試してから、古い状態を復元します。

JavaScript の変換は、Reader の簡単な演習として残しておきます。

于 2011-06-29T02:47:35.160 に答える