2

6x6 Rush Hour パズルを解くための反復的な深化アルゴリズムを作成するという学校の課題があります。練習する必要があるので、すべてのことで JavaScript を使用することにしました。ただし、アルゴリズムを大幅に最適化するのに問題があります。

私はパズルを解こうとしましたが、その解はツリーの 8 レベルにあり、7,350,669 個のノードにアクセスし、コンピューターで解くのに約 13 分かかりました。

アルゴリズム自体を理解するためのヒントとヘルプを探しています。

NodeとVehicleの2つのクラスを作成しました。これらの実装が問題の一部である可能性があります。

class Vehicle {
  constructor(x,y,length,horizontal){
    this.x = x; //X position of the upper/left block of the vehicle
    this.y = y; //y postion
    this.length = length; //length of the vehicle
    this.horizontal = horizontal; //boolean - false if vertical
  }
}

class Node {
  constructor(grid,vehicles,moved,depth){
    this.grid = grid; //A 6x6 char array grid
    this.vehicles = vehicles; //array of vehicles on the game board
    this.moved = moved; //index of vehicle moved in last turn
    this.depth = depth; //Depth of this node
  }
}

グリッド用の「2次元」配列と車両の配列の両方を持つことはやり過ぎだと思いますか? 動きの可能性をチェックするときは、車両配列を反復処理しますが、ガードを使用して、車両の前方に自由な道があるかどうかをすばやく確認します。これで私が見た問題に戻ります。

アルゴリズムのコードを公開することはできませんが、IDDFS を理解し、アルゴリズムを実装する方法は次のとおりです。

  1. 現在のノードが最終状態であるかどうかを確認し、そうである場合はソリューション配列に追加して true を返します。
  2. それ以外の場合は、maxDepth に到達したかどうかを確認し、到達した場合は false を返します。
  3. そうでない場合は、この状態の車両ごとに、実行できるすべての移動用の新しいノードを作成します (最後の移動で移動されたものを除く)。
  4. 作成したばかりのすべての子にアクセスし (手順 1 に戻ります)、false が返された場合は削除します。
  5. どの子ノードも最終状態にならなかった場合は、親ノードに戻ってその隣接ノードを調べます。それ以外の場合は、真の連鎖反応が発生します。
  6. 最終状態が見つかるまで繰り返します。トップに戻ったら、maxDepth を 1 増やして、プロセス全体を繰り返します。

私が目にする 1 つの問題は、私のデータ構造が少し複雑である可能性があることです。JavaScript はオブジェクトとオブジェクトの配列を参照として渡すため、以下を使用してディープ コピーする必要があります。

JSON.parse(JSON.stringify(node))

ここでの主な質問は、何か見逃したことがありますか? 「悪い」子ノードを削除し、反復深化アルゴリズムでツリー全体を何度も繰り返し続けるのは正しいですか、それとも誤解していましたか? ツリー全体を再度生成する必要がないように、それらは「チェック済み」としてマークされてから返され、後で通過するだけですか?

4

1 に答える 1

2

まず、コードの実行をプロファイリングする必要があります。それ以外の場合は当て推量であり、0.1% の利益のためにコードを変更するのに多くの時間を費やす可能性があります。

上記のことを念頭に置いて、オブジェクトの構造がわかっている場合 (ここの場合のように) を使用するのではなく、各プロパティを手動でコピーすることにより、オブジェクトをはるかに高速に複製できますstringify。

于 2016-03-19T08:43:46.330 に答える