問題タブ [breadth-first-search]

重み付けされていない大規模な循環グラフであるデータ セットがあります。サイクルは、約 5 ～ 6 パスのループで発生します。約 8000 のノードで構成され、各ノードには 1 ～ 6 (通常は約 4 ～ 5) の接続があります。私は単一ペアの最短経路計算を行っており、次のコードを実装して幅優先検索を実行しています。

上記のコードは Python 2.6 Queue モジュールを使用しています。SQL 呼び出しは高速です。

コードは正常に動作しますが、約 7 層の深さまでテストを実行するには約 20 秒かかります (2.5GHz Intel 4GB RAM OS X 10.6)。

このコードの実行時間を改善する方法についてのコメントを歓迎します。

これはラウンド 1B 2009 問題 C「Square Math」の問題です。コンテスト分析が掲載されていることを知っています。しかし、ノードに複数回アクセスできる場合に BFS を実装する方法についてはわかりません。DFSを使用してのみ実装できました。(コンテキストは再帰的 DFS で暗黙的に保存されるため)。BFSを使用してそれを行う方法は?

8パズルの問題はBFSで解決できると聞きましたが、その方法がわかりません。次のようなボードから取得する必要のある中間ステップを知りたいです。

に

中間ステップはBFS検索の「レベル」ですか？

ちなみに、これは基本的な宿題で、最適性は気にしません。

まず、この質問はこれの複製ではなく、それに基づいています。

その質問の木を例にとると、

そのように印刷するには、プログラムをどのように変更しますか。

一般というより

私は基本的にそれを行うための最も効率的な方法についての直感を探しています.結果をリストに追加してからループする方法があります. より効率的な方法は、ポップされたときに各レベルの最後の要素を格納し、後で新しい行を出力することです。

アイデア？

セットアップ (MySQL):

これは私の以前の投稿の BFS ソリューションです。

チャレンジ、6次分離のアルゴリズムを実装する方法は?

しかし、それの複雑さは何ですか?完全にnレコードがあるとします。

幅優先アルゴリズムに問題があります。スクリプトはマヤで曲線を生成し、それらを配置し、回転させてスケーリングし、木の形を与えます。これらの変数があります。

cs =現在の状態、

p =親、

ノード=訪問されていないノードリスト

lvl=現在の深さ

maxlvl=最大深度

問題は、現在の深さを判別できず、そこでツリーを終了できないことです。これは、すべてのノードにアクセスせずに存在します。

これが私のスクリプトです

前もって感謝します

現在、約1,000 万のノードと3,500 万のエッジを持つグラフがあります。今のところ、プログラムの開始時に完全なグラフがメモリにロードされます。これには数分かかり (結局のところ Java です)、約 0.5 ギガバイトの RAM が必要です。今のところ、デュアル コア プロセッサと 4 ギガバイトの RAM を搭載したマシンで動作します。

幅優先検索を使用してグラフを検索すると、メモリ使用量が 1 ギガバイトのピークに達し、平均で 10 秒かかります。

プログラムを数台のコンピューターに展開したいと考えています。グラフ検索以外の機能は、ほとんどリソースを消費しません。私のターゲット システムは非常に小型で、512 メガバイトの RAM しかありません。

メモリをあまり消費せずにそのグラフを検索するための方法を (おそらくデータベースを使用して) 実装する方法に関する提案はありますか? プログラムはハードウェア デバイスにアクセスしているため、ほとんどの場合アイドル状態であるため、上記のグラフのパス検索には最大で約 5 分かかる場合があります...

私の方向に投げかけられた考えに感謝します。

アップデート：

neo4jが見つかりました。この種の巨大なグラフに適しているかどうかは誰にもわかりませんか?

グラフの実装に必要な一般的な関数のほとんどを実装した後、いくつかの関数 (頂点の削除、頂点の検索、頂点の取得) には「最適な」実装がないことに気付きました。

グラフの実装にリンクされたリストを含む隣接リストを使用しています。必要な頂点が見つかるまで、次々と頂点を検索していました。私が言ったように、私は「最良の」実装を使用していないことに気付きました。10000 個の頂点を持つことができ、最後の頂点を検索する必要がありますが、その頂点には最初の頂点へのリンクが含まれている可能性があり、これにより作業が大幅に高速化されます。しかし、これはあくまでも仮説であり、実際に起こるかもしれないし、起こらないかもしれません。

では、検索ルックアップにはどのアルゴリズムをお勧めしますか? 私たちの教師は、主に幅優先と深さ優先について話しました (そして、Dikjstra のアルゴリズムですが、それはまったく別の主題です)。その2つのうち、どちらがおすすめですか?

両方を実装できれば完璧ですが、そのための時間がありません。第 1 フェーズの締め切りが近づいているので、どちらかを選択して実装する必要があります...

私の推測では、Depth-first を使用することであり、実装が容易であり、それらの動作方法を見ると、それが最善の策のようです。しかし、それは本当に入力に依存します。

しかし、あなたたちは何を提案しますか？

有向グラフが循環的かどうかをどのように検出できますか? 幅優先探索をしようと思ったのですが、よくわかりません。何か案は？

二分木の幅優先探索を再帰的に実装したいとしましょう。あなたならどうしますか？

コールスタックのみを補助記憶域として使用することは可能ですか?