問題タブ [tree-search]

ルートから最下位の子まで、すべてのレベルを 1 ～ 10 回展開するツリーを使用して、すべてのパスを要約しようとしています。私の関数はすべての子に再帰的に歩きますが、ノードのリストを作成してリストでこのリストを実行しようとすると、リストのリストのリスト...リストのリストになるという問題があります。私の問題は結合ステップだと思いますそして、パターンマッチング方法を作成しようとしましたが、リストのリストになったときにリストを比較し、新しいリストを作成して、それが一方向だけの場合はそれらを比較する方法(リストを満たすリストを含むリストではなく、ノードを含む）は機能しません。

私は木のような構造をしています。一緒に接続してツリーを構成するいくつかの線を取得できます。線は始点と終点で構成されています。XML 形式のツリーからのサンプル データを次に示します。

ツリーのグラフィカルな表現は次のとおりです。

私がする必要があるのは、画像に示されているように、このツリーのリーフとジャンクションを抽出することです:

このタスクを実行するための複雑さと時間に関して最適化されたアルゴリズムを見つけたいです。

互換性のあるヒューリスティック (h) は、以下の条件を持つものです。

h(n) <= c(n,a,n') + h(n')

****************************************************

許容ヒューリスティック (h) は、以下の条件を持つものです。

0 <= h(n) <= h*(n)

h*(n) は、ノードからノードnまでの実際の距離です。goal

ヒューリスティックに互換性がある場合、それが許容できることをどのように証明しますか?

どうもありがとう。

タスクの可能なすべてのケースを組み合わせてカウントする必要があります。そのために木を作りたい。いくつかのジョブがあり、各ジョブにはいくつかのサブジョブがあります。仕事をするために利用できる多くのエージェントがあります。ジョブ 1 サブジョブ 1 がエージェント 1 または 2 によって実行される場合、ジョブ 1 サブジョブ 2 はいずれかのエージェントによって実行されるとします。そして、ジョブ 2 が開始されます。等々。ノードはさまざまであり、子ノードの数もさまざまなレベルで変化するため、私の質問は次のとおりです。

1. 同じものを実装するのに最適なデータ構造は何ですか?

2. あなたが推奨したデータ構造を使用してツリーをたどる最良の方法は何ですか?

私はコーディングに慣れていないので、抽象的なアドバイスだけでなく、具体的な C++/Java の例または Web ソースも提供してください。

編集：

私が考えているツリーのフローチャートを参照してください。

この質問を stackoverflow と cs.stackexchange.com のどちらに投稿すべきかわかりません。移動する必要があるかどうかお知らせください。

モンテカルロ木探索 (MCTS) の時間計算量を見つけようとしています。グーグルは助けにならないので、私は自分でどこまで計算できるかを見ようとしています.

n反復のために、または時間がなくなる前に、4 つのステップを実行します。だから私たちは持っています

O(n*(選択+拡張+シミュレーション+逆伝播))

展開は、現在選択されているノードに子を追加するだけです。単一リンクリストなどを使用してツリーの子を格納していないと仮定すると、これは一定の時間で発生する可能性があるため、除外できます。

O(n*(選択+シミュレーション+逆伝播))

分岐係数bとtツリー内のノードの総数を考えると、ツリーの深さが log _b t であるため、選択フェーズは O(b*log _b t) で実行されると想定しています。以上の子供たち。

したがって、時間の複雑さは次のようになります

O(n*(b*log _b t+シミュレーション+逆伝播))

バックプロパゲーションには、ツリーの深さに比例する時間もかかるため、次のようになります。

O(n*(b*log _b t+シミュレーション+b*log _b t))

しかし、これにシミュレーションフェーズを追加する方法がわかりません。

私は Python で Bresenham のライン アルゴリズムを実装し、グリッド ワールドのグリッド セルの注目リスト間のグリッドの占有率を識別しました ([(1,1), (3,2),(5,6),(8,4 など) ) いくつかの占有されたグリッドがある 10X10 グリッドの世界で) 次に、視線アルゴリズムを適用して、合計距離を減らすために頂点リストをスキップできるかどうかを確認しました。

しかし、グラフベースの検索の見通し線を実行するにはどうすればよいですか? 座標形式 (x,y) でグリッド セルを表したように、ツリー/グラフ ノードをどのように表すことができるのでしょうか。提案/アイデアは大歓迎です。

現在、ミニマックスアルゴリズムに取り組んでいますが、各ノードを比較するのに問題があり、最良のノードを返すことができません。比較できたら、ノードの一番下を選択します。誰かがコードを修正するのを手伝ってくれますか?

ここに私のコードがあります: