JavaScriptで反復深化ラッシュアワーアルゴリズムを最適化するのに問題がある

Question

私は6x6ラッシュアワーパズルを解く反復的な深化アルゴリズムを作るための学校の割り当てを持っています。私は練習が必要なので、すべてのもののJavaScriptを使用することを選択しました。私はしかし、アルゴリズムを大きな方法で最適化するのに問題があります。

私はその解決策をツリーに8段階に分けて解決しようとしました。私は7,350,669のノードを訪れ、解決するのに約13分かかったことがわかりました。

私はヒントを探しており、アルゴリズムそのものを理解するのに役立ちます。

ノードと車両の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 
    } 
} 

アムI右の仮定で、girdための「二次元」の配列だけでなく、車のアレイの両方を持つことはやり過ぎであること。これらの実装は、問題の一部である可能性がありますか？可能性のある動きをチェックするとき、私は車両アレイを反復するが、ガードを使用して、車両が前方に自由な道を持っているかどうかをただちにチェックする。私はこれで見ている問題に戻ります。

私は公にアルゴリズムのためのコードを投稿しますが、ここで私はIDDFSを理解し、アルゴリズムをimplementated方法ですができません。

1. それが最終状態である場合ならば解の配列に追加し、現在のノードをチェックそれは真実です。
2. それ以外の場合はmaxDepthに達しているかどうかを確認し、そうであればfalseを返します。
3. ない場合、この状態で各車両のためのバックに、彼らは（最後の移動中に移動されたものを除く）を作ることができ、すべての移動
4. ログインあなただけ行われたすべての子供（のための新しいノードを作成しますステップ1）それらがfalseを返す場合は削除します。
5. 最終状態であることが示された子が1つもない場合は、親ノードに戻り、その近隣ノードを探索します。それ以外の場合は真の連鎖反応が起こります。
6. 最後の状態を見つけるまで繰り返します。一番上に戻ったら、maxDepthを1ずつ増やして、プロセス全体を繰り返します。

1つの問題は、私のデータ構造が少し複雑かもしれないということです。

JSON.parse(JSON.stringify(node)) 

私が何かを逃したのは - ここでは、主要な質問：JavaScriptが参照としてオブジェクトのオブジェクトと配列を渡しているので、彼らは深い使用してコピーする必要がありますか？ 「悪い」子ノードを削除し、ツリー全体を何度も繰り返して繰り返しアルゴリズムを繰り返しているか、それとも誤解していたのでしょうか？彼らはちょうど "チェックされた"とマークされると仮定され、その後、ツリー全体が再び生成する必要はありませんので、後でそれらを通過するに戻っている？

Answer 1

まず、コードの実行をプロファイルする必要があります。それ以外の場合は推測で、コードを変更して0.1％の利益を得るのに多くの時間を費やすことができます。

stringifyではなく、各プロパティを手動でコピーすることで、その構造がわかっているときにオブジェクトを非常に高速に複製できます。