幅優先検索で訪問済みの状態を追跡する10だから私はスライディングブロックパズル(数値型)にBFSを実装しようとしていました。今私が気づいた主なことは、4*4ボードを持っている場合、州の数は16!すべての州を事前に列挙することができないほど多くなる可能性があるということです。私の質問は、すでに訪問した州を追跡する方法ですか?(私はクラスボードを使用しています。各クラスインスタンスには一意のボードパターンが含まれており、現在のステップから可能なすべてのステップを列挙して作成されます)。私はネット上で検索し、どうやら彼らは完成前のステップに戻っていない、しかし、我々は以前に訪問されたすべてのステップを列挙する再過ぎてから、再度、別のルートで、前のステップに戻ることができます。それでは、すべての州がまだ列挙されていない場合に、訪問した州を追跡する方法は?(すでに存在する状態を現在のステップと比較すると、コストがかかります)。DuttaAソース1補足:この質問を投稿するのにより適切なスタックは考えられませんでした。このスタックでは実装の詳細は一般に歓迎されないことを知っています。20182これは、SE:AIにとって素晴らしい質問です。それは実装に関するだけでなく、コンセプト自体でもあるからです。言うまでもなく、この質問には数時間で4つの合法的な回答が集まりました。DukeZhou回答:8あなたは使用することができsetますが、すでに見てきたことを店の状態に(つまり、重複を含めることはできません、コレクション、言葉の数学的な意味で)。これで実行できるようにする必要がある操作は次のとおりです。要素がすでにそこにあるかどうかのテストほとんどすべてのプログラミング言語は、これらの操作の両方を一定の()時間で実行できるデータ構造をすでにサポートしているはずです。Javaで一見すると、このようなセットにこれまでに見たすべての状態を追加することはメモリの点で高価になるように思えるかもしれませんが、すでにフロンティアに必要なメモリと比較してそれほど悪くはありません。1つの余分訪問したノードごとのノード。closed_setとしましょう。ウィキペディアの疑似コードと一致させるには、次のように幅優先検索で使用できます。time(この疑似コードの一部のバリエーションも機能し、状況に応じて多少効率が良くなります。closed_setフロンティアにすでに子を追加したすべてのノードをに含め、generate_children()呼び出しを完全に回避することもできますcurrentすでににある場合closed_set。)上記で説明したのは、この問題を処理する標準的な方法です。直感的に、私は別の「解決策」は、後継者状態の新しいリストの順序を常にランダム化してから、それらをフロンティアに追加することだと思います。このようにして、すでに前に展開した状態を時々追加する問題を回避することはできませんが、無限サイクルでスタックするリスクを大幅に削減できると思います。注意してください:私はこのソリューションの正式な分析については知りませんが、無限サイクルを常に回避することを証明しています。直感的にこれを「実行」しようとすると、それは一種の作業であるはずであり、追加のメモリは必要ありません。私が今考えていないエッジケースがあるかもしれません、しかしそれは単にうまくいかないかもしれません、上記の標準的な解決策はより安全な賭けです(より多くのメモリを犠牲にして)。)O(1)SS1@DuttaAセットがどのように使用されるかを正確に説明するためにいくつかの疑似コードを追加しました。全体をループすることは決してないことに注意してくださいclosed_set。そのサイズは(漸近的な)計算時間に影響を与えることはありません。Soemersの答えは正しいです。BFSグラフ検索で訪問済みの状態を追跡するには、HashSetまたは同様の構造を使用する必要があります。それはあなたの質問に完全に答えるものではありません。最悪の場合、BFSでは16を格納する必要があります。セットの挿入時間とチェック時間はO(1)になりますが、それでも不合理な量のメモリが必要になります。BFSを使用しないください。単純な問題以外のすべての問題は扱いにくくなります。これは、最も近い目標状態までの距離が指数関数的な時間とメモリの両方を必要とするためです。これは、BFSの望ましい特性をすべて備えていますが、O(n)メモリーのみを使用します。nは、最も近い解に到達するための移動の数です。それでもしばらく時間がかかる場合がありますが、CPU関連の制限よりもずっと前にメモリ制限に達します。これにより、非常に少数のノードのみを調べ、線形時間に非常に近い何かで検索を完了できるようにする必要があります。ジョン・ドゥセットソース216!16!@DennisSoemersは正しいです。tbd-valueと幅優先は、枯渇することなく見逃しがちなブロックファクターがあるという点で最適です。一連の予測不可能なゲームボードトポロジでの「弱い」一般的なパフォーマンス。BFSは通常、完全なソリューションが求められる場合にのみ使用されます。*を使用するだけで済みます。Doucette「ゲームの手数」ではなく、「ゴールまでの最小手数」をお勧めします。ゲーム内の移動数は、16のいずれかから移動するすべての移動と考えることができます。これは、反復深化の使用よりもはるかに多くのメモリです。20187与えられた答えは一般的に真実ですが、15パズルのBFSは非常に実現可能であるだけでなく、2005年に行われました。アプローチを説明するペーパーはここにあります:http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdfいくつかの重要なポイント:これを行うには、外部メモリが必要でした。BFSはRAMではなくハードドライブをストレージとして使用しました。状態空間には相互に到達できない2つのコンポーネントがあるため、実際には15個の状態しかありません。これはスライディングタイルパズルで機能します。これは、状態空間がレベル間で非常にゆっくりと成長するためです。これは、任意のレベルに必要な合計メモリが、状態空間のフルサイズよりもはるかに小さいことを意味します。(これは、ルービックキューブのような状態空間とは対照的です。ルービックキューブでは、状態空間がはるかに速く成長します。)スライディングタイルパズルは無向なので、現在または前のレイヤーの重複について心配するだけで済みます。有向空間では、検索の以前の層で重複を生成する可能性があり、これにより状況がはるかに複雑になります。Korfによるオリジナルの作品(上記にリンク)では、実際には検索の結果を保存していませんでした。検索では、各レベルの状態の数が計算されました。最初の結果を保存する場合は、WMBFS(http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdfなど)が必要です。)の状態がディスクに保存されている場合、前のレイヤーの状態を比較するには、3つの主要なアプローチがあります。1つは並べ替えベースです。後続ファイルの2つのファイルをソートする場合は、それらを線形順にスキャンして、重複を見つけることができます。2つ目はハッシュベースです。ハッシュ関数を使用して後続ファイルをファイルにグループ化すると、完全な状態スペースよりも小さいファイルをロードして、重複をチェックできます。(ここには2つのハッシュ関数があることに注意してください-1つは状態をファイルに送信するためのもので、もう1つはそのファイル内の状態を区別するためのものです。)3つ目は、構造化重複検出です。これはハッシュベースの検出の形式ですが、すべてが生成された後ではなく、生成されたときにすぐに重複をチェックできるように行われます。ここで言うことはまだまだたくさんありますが、上記の論文にはもっと多くの詳細が記載されています。ネイサン・Sソースそれは素晴らしい答えです。DuttaA無向は他のレイヤーでの重複を避けるのにどのように役立ちますか?確かに、円の3つのタイルを移動することにより、別のレイヤーのノードに戻ることができます。どちらかと言えば、directedは、より制限的であるため、重複を回避するのに役立ちます。リンクされた論文は重複検出について語っていますが、無向または指示についてはまったく触れていません。さまざまなレベルでの重複の回避についても触れていません(ただし、非常に短いスキャンでは見逃していたかもしれません)。2018@NotThatGuy無向グラフでは、親と子の距離は最大で1であり、BFSで検出されます。これは、1つが見つかると、無向エッジが他のエッジがすぐに見つかることを保証するためです。有向グラフでは、深さ10の状態は深さ2の子を生成できます。これは、深さ2の子が他の状態にエッジを戻す必要がないためです(これにより、深さ10ではなく深さ3になります)。S.@NotThatGuy円で3つのタイルを移動する場合、サイクルを作成しますが、BFSはそれを両方向で同時に探索するため、実際にははるかに浅い深度に戻ることはありません。完全な3x2スライドタイルがこのデモに示されています。サイクルを追跡して、それらがどのように発生するかを確認できます。DukeZhou3皮肉なことに、答えは「あなたが望むどんなシステムでも使用すること」です。hashSetは良い考えです。メモリ使用量に対する懸念は根拠がないことが判明しました。BFSはこの種の問題で非常に悪いため、この問題は解決されます。BFSでは、未処理の状態のスタックを保持する必要があることを考慮してください。パズルに進むにつれ、処理する状態はますます異なるものになるので、BFSの各層が、調べる状態の数を約3倍にすることに気付くでしょう。メモリに収まることを確認するために使用したどのようなアプローチでも、以前にアクセスしたリストもメモリに収まるようにするのに十分です。他の人が指摘したように、これは使用するのに最適なアルゴリズムではありません。問題により適したアルゴリズムを使用してください。コートアンモンソース215パズルの問題は、4x4ボードで再生されます。ソースコードでこれを実装することは段階的に行われます。最初に、ゲームエンジン自体をプログラムする必要があります。これにより、人間のオペレーターがゲームをプレイすることができます。15パズルゲームには1つの無料要素しかなく、この要素でアクションが実行されます。ゲームエンジンは、左、右、上、下の4つのコマンドを受け入れます。他のアクションは許可されておらず、これらの指示だけでゲームを制御することが可能です。ゲームをプレイするための次の層はGUIです。これは非常に重要です。ゲームエンジンをテストし、手動でゲームを解くことができるからです。潜在的なヒューリスティックを把握する必要があるため、GUIも重要です。今、私たちはAI自体について話すことができます。AIはゲームエンジンにコマンドを送信する必要があります(左、右、上、下)。ソルバーの素朴なアプローチはブルートフォースサーチアルゴリズムです。AIは目標状態に達するまでランダムコマンドを送信します。高度なアイデアは、状態空間を削減するある種のパターンデータベースを実装することです。幅優先検索は直接ヒューリスティックではありませんが、それは始まりです。発生する可能性のある動きを時系列でテストするためのグラフを作成することと同じです。既存の状態の追跡はグラフで行うことができます。各状態はノードであり、IDと親IDがあります。AIはグラフのノードを追加および削除でき、プランナーはグラフを解いてゴールへのパスを見つけることができます。プログラミングの観点からは、15パズルのゲームエンジンがオブジェクトであり、多くのオブジェクトのリストは配列リストです。それらはグラフクラスに保存されます。ソースコードでこれを実現するのは少し難しいです。通常、最初の試行は失敗し、プロジェクトは多くのエラーを生成します。複雑さを管理するために、このようなプロジェクトは通常、学術プロジェクトで行われます。100ページ以上になる可能性のあるそれについての論文を書くためのトピックです。!16!ただし、パズルを最小のコンピューティングサイクルで完了することが目標である場合、これらの些細な事実は適切ではありません。幅優先探索は、直交移動パズルを完了するための実用的な方法ではありません。幅優先検索の非常に高いコストは、何らかの理由で移動回数が最も重要な場合にのみ必要になります。状態を表すほとんどの頂点は決して訪問されず、訪問された各状態は2つから4つの出力エッジを持つことができます。各ブロックには初期位置と最終位置があり、ボードは対称です。最大の選択の自由は、オープンスペースが4つの中間位置の1つである場合に存在します。少なくとも、オープンスペースが4つのコーナー位置の1つである場合です。妥当な視差(誤差)関数は、単純にすべてのx視差の合計とすべてのy視差の合計、およびオープンスペース(中央、エッジ)の配置により、3つの移動の自由度のどれが存在するかを発見的に表した数値です。一連の移動を必要とする完了に向けた戦略をサポートするために、ブロックが一時的に目的地から離れることがありますが、そのような戦略が8つの移動を超え、平均して5,184の順列が生成され、最終的な状態を比較できる場合はめったにありません。上記のディスパリティ機能を使用します。ビット単位の演算のみが必要なので、アルゴリズムが高速になります。8つの移動ブルートフォース戦略を繰り返すことは、格差がゼロになるまで繰り返すことができます。概要すでに完了している開始状態を除いて、初期状態に関係なく、常に8つの移動の順列の少なくとも1つが視差を減少させるため、このアルゴリズムは循環できません。FauChristianソース弊社のサイトを使用することにより、あなたは弊社のクッキーポリシーおよびプライバシーポリシーを読み、理解したものとみなされます。