問題タブ [tree-search]

二分木で特定の値を検索する反復関数を作成しています。これは、クラスをジェネリック化する方法を説明するまでは、signed int にローカライズされています。

私のクラスが BinarySearchTree で、ツリーのルート ノードへのポインターがあるとします。また、挿入関数によってノードが挿入され、2 つの子へのポインターがあるとします。以下は Node 構造体のかなり省略されたバージョンです:

したがって、ノードの uninit ポインターが NULL になると安全に想定できます。

これが私のコードです：

このコードは、次の 2 つの理由で友人によって拒否されています。

1) next に子がない場合、両方ともゼロと評価され、途中でループを終了します (検索された val を next の値に対してチェックすることはありません)。

2) next に 1 つの子があるが、検索しているデータがツリーの空の側にある必要がある場合、next は 0 に設定され、next (0 である) を左右で比較して再びループします。のようなツリーwhile(0->left())で、未定義の動作が発生します。

両方の問題の解決策はループ状態にあると言われていますが、状況を簡単に修正するために何ができるかわかりません。Stack Overflow のコミュニティは洞察を提供できますか?

分散型 Go/Gomoku ボットを作成しています。

基本的に重要なのは、ツリー検索を多くのコンピューターに分散させることです。DFS のような基本的なツリー検索アルゴリズムを使用すると、検索スペースをサブツリーに分割するだけで済むので、これは非常に簡単です。私はむしろアルファベータプルーニングを備えたミニマックスのように、より効率的なものを望んでいますが、私の理解では、共有メモリがなければまったく無意味です。だから私はちょっと立ち往生しています。

効率的で簡単に配布できるアルゴリズムを使用できるアイデアはありますか? さらに重要なことに、その (疑似) コードまたは実装をどこで見つけることができますか?

ありがとう、

どのノードも、任意の数の子を持つことができます。このツリーを検索するには、次のようなものを書きました

これはうまくいきません...何か入力はありますか？

私が遭遇する「難しい」組み合わせ問題のいくつか は、アルファベータ法、ビームサーチ、または同様のアルゴリズムなど、ある種のツリーサーチの観点から投げかけることができることに気づきました。ただし、それらをプログラミングすることは、同じことを繰り返しコーディングしているように見え、間違いを犯しやすいこともあります。これらのアルゴリズムを実装するライブラリがあるはずだと私には思えます、そして私が書くように頼まれるべきなのは

1. ソリューションのコーディング、つまり、不完全なソリューションからより具体的なソリューションを取得する方法。これにより、ツリー/グラフの構造が得られます。
2. 部分的な解決策を考えると、最大/最小コストを取得する方法、そしておそらくコストの見積もり。
3. 初期ソリューション/部分ソリューション。
4. 多分ある種の検証ソリューション。

特定のコードを提供していないことをお詫び申し上げますが、問題を説明したと思います。上記の関数のコードを記述できれば、多くのツリー/グラフ検索アルゴリズムを簡単に実行できるはずではありませんか？これを簡単にサポートするユーザーフレンドリーなライブラリ/フレームワークはありますか？PythonまたはC/C ++で使用したいのですが、何か提案があれば興味があります。

編集：より正確に言うと、私は情報に基づいたツリー検索アルゴリズムについて話しています。

lxml ElementTree 内の特定の html 要素 (el) のコンテンツが、レンダリングされた HTML ページの行の先頭のコンテンツであるかどうかを判断する関数に取り組んでいます。これを行うために、el の左にある最も右のブロック レベル要素を見つけて、これら 2 つの間にコンテンツがあるかどうかを判断しようとしています。

これは、el から始まる逆方向のトラバーサルを使用して、DFS の逆の順序でトラバーサルを行うことで発生する可能性があると考えています。しかし、これを行うためにlxmlまたはxpathを使用してより簡単な方法が存在するかどうかも調べようとしています。これまでのところ、特定の要素の祖先または左の兄弟である要素をいくつかの基準で見つける方法を見つけましたが、特定のノードの右側 (または左側) のツリー全体で機能するものは見つけていません。

lxml または xpath を使用してこの検索を行う簡単な方法を知っている人はいますか?

例

上記では、レンダリング時に行の先頭のコンテンツを表示するように見える要素に「最初の」クラスを追加しました。特に興味深いのは、ID が "tricky" の要素です。その要素は、祖先も兄弟もブロック レベルの要素ではありませんが、行の最初のコンテンツを表示するためです。「トリッキー」は、その兄弟の 1 つ (h1) の子孫がブロック レベルであり、その h1 の後に他のコンテンツがないため、新しい行になります。

フォローアップ この時点で、一種の後方トラバーサルを行う関数を Python で作成しました。少し複雑ですが、うまくいくようです：

人工知能における DFS、A* 検索に関するグラフ検索バージョンとツリー検索バージョンの違いは何ですか?

T-SQLツリー検索

親の下にある場合は、ノードのセットから選択します

MSSQL Db（80000+）レコードに非常に大きなツリーがあります。LIKE私のクライアントは、テキストコマンドを介してツリーのクイック検索を要求しました。このLIKEコマンドは500レコード未満を返します。

それぞれのツリーをすばやくチェックして、特定のノードの下にあるかどうかを確認する再帰コマンドはありますか？

編集：しかし、それはかなり明確だと思いました...。

私はSQLServer2005を使用しています。

いくつかのレベルをすばやく下げることができる再帰呼び出しがあります。ただし、名前検索を実行するには、ツリー全体をポーリングする必要があります。これは、数百レベルの深さになる可能性があり、オプションではありません。最初にテーブル全体で名前の一致を検索し、問題のツリーの一部ではないレコードをフィルタリングできるように、クエリの設計に役立つことを期待していました。

POSTを行うWebサイトがありますが、パラメーターが格納されている場所を知りたいです。それらをハックし、投稿する前に編集するために必要です。スクリプトは巨大で難読化されているため、ソースコードを読んだだけでは必要なオブジェクトを見つけることができません。

この回答windowからJSON.pruneを使用してシリアル化しようとしました。必要な文字列が格納されている場所を見つけるために使用するキーワードは、28メガバイトのテキストで40回近く見つかりました。また、部分文字列を見つけた後でも、あまり読みやすくありません。だから多分それは行く方法ではありません。

私は私に言うだろう何かが必要です：

• このsubstrは次の場所で検出されました：
  -文字列window.bla_bla_bla.deepobject.bla[5].blabla.msg_to_post
  -文字列window.bla_bla_bla.deepobject.bla[3].and_here
  -文字列window.and_even_here
  -など。

さまざまなアルゴリズムを使用して問題を解決しようとしていますが、実装が必要なアルゴリズムには、最急上昇ヒル クライミング (SAHC) と最優先探索の 2 つがあります。

ウィキペディアによると：

「最も急な上り坂のヒルクライムでは、すべての後継者が比較され、解決策に最も近いものが選択されます...」

「最も急な上り坂の登山は、1 つだけではなく、現在のパスのすべての可能な延長を試みる最善優先探索に似ています。」

SAHC : すべての後継が比較され、ソリューションに最も近いものが選択されます。
BestFS : 1 つだけではなく、現在のパスのすべての可能な拡張子を試します。

これらの違いがよくわかりません。できれば木を使った何らかの説明で、これを手伝ってもらえますか？