4

私は木を持っています。底は平らです。一番下の葉だけに興味がありますが、これはおおよそ一番下にある葉の数です...

2 x 1600 x 1600 x 10 x 4 x 1600 x 10 x 4

それは〜13,107,200,000,000枚の葉ですか?サイズの関係で(各葉で実行される計算が1秒未満かかるように最適化される可能性は低いようです)、すべての葉を訪問できるとは思いませんでした。

したがって、(周囲のノードの結果に基づいて)最も「可能性の高い」ノードを最初に検査する「スマート」リーフクローラーを構築することを考えています。したがって、葉が隣人の枝/グループで評価されることを期待するのは合理的ですが、グループのサイズと分布は異なります。

どの葉が訪問され、どの葉が訪問されなかったかを記録する最も賢い方法は何ですか?

4

3 に答える 3

1

多くの情報は提供されませんが、検索アルゴリズムを調整して、見たものを追跡できるようにすることをお勧めします。「可能性」によって葉をランク付けするグローバルな方法があれば、可能性の降順で葉を訪問するだけでよいので、問題はありません。しかし、私の理解が正しければ、あなたは一種の山登りをしているだけですよね? 完全なサブツリー (たとえば、「可能性が高い」として選択されたクラスター内のすべての 1600 x 10 x 4 リーフ) を検索し、個々のリーフではなくクラスターを追跡することで、必要なストレージを減らすことができます。

ツリー ジオメトリが一貫しているように聞こえるので、検索の仕組みに応じて、ノードを上方にマージするのは簡単なはずです...たとえば、葉がすべて検査されたレベル 1 ノードを追跡し、レベル 2 ノードがリストにある場合は、子をドロップして親を保持します。これは、何を調べるかを選択する良い方法でもあります。レベル 3 ノードの 3 つの子を調べた場合、4 番目と最後のノードも調べる価値があります。

最後に、考えてみてください: グループ内のいくつかのソリューションを除外する方法がないことを本当に本当に確信していますか (個々のソリューションをすべて調べることなく)。数独のような問題には、天文学的に大きな探索空間がありますが、優れた力ずくのソルバーは、可能性のあるすべての 9 x 9 ボードを調べることなく、可能性の大きなブロックを排除します。問題の規模を考えると、これは問題を攻撃する最も実用的な方法です。

于 2012-09-01T20:48:45.583 に答える
1

メンバーシップ テストを行うための迅速かつ効率的な (メモリ使用量の点で) 方法を探しているようです。もしそうなら、そしていくつかの誤検知に対処できるなら、ブルームフィルターを選びましょう。

要点:データ セットが非常に大きく、必要なのはセット内に特定の要素が存在するかどうかをチェックすることだけであり、誤検出の可能性がわずかであっても許容できる状況では、ブルーム フィルター使用ます

Python の実装がいくつか存在するはずです。

これが役立つことを願っています。

于 2012-09-01T08:50:15.750 に答える
0

これは明白すぎるかもしれませんが、同様のツリーに結果を保存できます。あなたの計算は遅いので、結果ツリーがあまりにも速く成長するべきではありません。次に、特定のノードの結果があるかどうかを調べます。

于 2012-09-01T09:24:00.020 に答える