問題タブ [search-tree]

私は次のプログラミングコンテストのために練習してきましたが、私は完全に当​​惑している質問に出くわしました。しかし、それは決して思い浮かばないということで、指を交差させるのではなく、今学ぶべき概念だと感じています。

基本的には、チェス盤の騎士の駒を扱います。開始位置と終了位置の2つの入力が与えられます。次に、目標の場所に到達するために騎士がたどることができる最短経路を計算して印刷することが目標です。

私は最短経路のようなものを扱ったことがなく、どこから始めればよいのかさえわかりません。これに取り組むために私はどのような論理を採用していますか？

PS関連性がある場合は、騎士の通常の動きを補うために、騎士が行うことができる（潜在的に）8つの動きによって形成される正方形の四隅に移動できるようにする必要があります。騎士の場所。

キーワードに基づいて検索ツリーを作成するこのアプリを分解しようとしていますが、少し複雑すぎるのではないかと思います。誰か説明してもらえますか？

フォーマットがオフになっているので、これがペーストビン（pastie.orgがダウンしていますか？）バージョンです。

どんな助けでも大歓迎です。

次のHaskellツリータイプがあるとします。ここで、「State」は単純なラッパーです。

また、リーフノードを取得してブランチに展開する関数「expand :: Tree a-> Tree a」、またはブランチを取得して変更せずに返す関数もあります。このツリータイプは、N-ary検索ツリーを表します。

深さ優先探索は無駄です。検索スペースは明らかに無限であり、ツリーのすべてのリーフノードでexpandを使用して検索スペースを簡単に拡張し続けることができ、誤ってゴール状態を見逃す可能性があります。巨大です...したがって、唯一の解決策は幅優先探索であり、ここでかなり適切に実装されています。そこにある場合は解決策が見つかります。

しかし、私が生成したいのは、解決策を見つけるためにトラバースされたツリーです。これは問題です。なぜなら、私はこの深さ優先を行う方法しか知らないからです。これは、最初の子ノードで「expand」関数を何度も呼び出すだけで実行できます...ゴール状態が見つかるまで。（これは、本当に不快なリスト以外のものを実際に生成することはありません。）

誰かが私にこれを行う方法（またはアルゴリズム全体）についてのヒント、またはそれがまともな複雑さで可能かどうかについての評決を教えてもらえますか？（または、これに関する情報源は、かなり少ないので。）

私は人工知能から引用します: A Modern Approach :

深さ優先探索の特性は、グラフ探索とツリー探索のどちらを使用するかによって大きく異なります。繰り返される状態と冗長なパスを回避するグラフ検索バージョンは、最終的にすべてのノードを展開するため、有限状態空間で完全です。一方、ツリー検索バージョンは完全ではありません[...]。深さ優先ツリー検索は、ルートから現在のノードへのパス上の状態に対して新しい状態をチェックするように、追加のメモリ コストなしで変更できます。これにより、有限状態空間での無限ループは回避されますが、冗長パスの増殖は回避されません。

ツリーが特定のグラフであるため、グラフ検索が完了し、ツリー検索が完了しない方法がわかりません。

その上、「無限ループ」と「冗長パス」の違いがはっきりとわかりません...

誰かが私にこれを説明してもらえますか?

ps。本をお持ちの方は86ページ（第3版）です。

Prologプログラムの段階的な検索ツリーを描くことができるツールがあるかどうか疑問に思いましたか？ありがとう。

チェス盤のKnight'sShortestPathでの以前のStackOverflow投稿の1つに質問があります

'ok、それはグラフの質問であり、そのスパース行列は'：のようなものです。

既存のエッジを記述します。ただし、ダイクストラのアルゴリズムで簡単に使用できるように、このグラフのデータ構造がどのように見えるか（隣接行列ですか？上記の「スパース行列」と記載されていますか？）はまだわかりません。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。

アルゴリズムの説明から、グラフのデータ構造が頂点のセットであり、隣接する頂点情報が利用可能である場合は便利に見えます。しかし、どうすればこれを達成できますか？

このグラフのサンプルデータ構造を書き出すにはどうすればよいですか？ダイクストラのアルゴリズムにどのように便利にリンクできるかについての理解を求めています。

私は論文を読んでいて、B+-trees をメイン メモリのキャッシュに意識させています。セクション 3.1.2では、著者は CSB+ ツリー ノード内で検索するためのいくつかのアプローチについて説明しています。

基本的なアプローチは、従来の while ループを使用してバイナリ検索を実行することです。

統一されたアプローチは、すべてのキーが使用されていると仮定して、while ループをステートメントに展開するコード展開によるものです。if-then-else

著者は、最大 9 個のキーを持つノードの検索の展開を示す次の例を示しています。ifノード内の数字は、テストで使用されているキーの位置を表します

次に、紛らわしい部分があります。

実際に存在するキーが 5 つだけの場合、ちょうど3 回の比較でこのツリーをたどることができます。一方、最も深いサブツリーを右ではなく左に配置する展開では、一部の分岐で4 回の比較が必要になります。

では、なぜ次のツリーでさらに比較が必要になるのでしょうか。

さらに、

有効なキーが 5 つしかないとわかっていれば、平均して3 回ではなく2.67回の比較を使用するツリーをハードコーディングできます。

2.67はどのように発生しますか?

ヒントをいただければ幸いです。また、コード拡張の知識へのリンクも役立ちます。

実際、ここに転記したときにいくつかの重要な情報が省略されている可能性があるため、紙で質問することが適切かどうかはわかりません (質問を再フォーマットする必要がある場合があります)。たまたま新聞を読んだ人がいてくれたらいいのにと思います。

ありがとう

答えが欲しいツリーアルゴリズムとデータベースの問題があります。

いくつかのエリアがあります。たとえば 20 としましょう。これらの各エリアにはそれぞれ 20 までのサブエリアがあります。これらの親エリアはマップ上に広がっています。これらの親領域のいくつかは互いに近接しています。

データベースは次のようになります: [area_id, title, parent_id] - 一部には複数の子があり、すべての領域を含むルート ノードがあります。(隣接リスト モデル)

これを写真にするには、次のようにします。

私が言ったように、さまざまな領域は互いに近くにある場合もあれば、離れている場合もあります。エリア 1 とエリア 5が近くにあり、エリア 1 もエリア 4 に近いことがわかっているので、どうにかしてそれらを結び付けたいと思います。ここで問題は、エリア 4 がエリア 5 にも近いとしましょう。 .

次のようになります。

無限ループになるのはどれですか? エリア 1 をエリア 4 に近づけたいだけでなく、エリア 4 もエリア 1 に近づけたいからです。

「近くのエリアを検索」を選択できる検索を行いたいので、1 つのエリアを選択すると、近くのエリアを検索できます。データベースとphpでこれを解決する方法について、いくつかのヒントを使用できます。

このフォーラムで助けを求めて探し回っていますが、この問題の「名前」がよくわかりません。誰かが私を正しい方向に向けるか、このスレッドでまっすぐに助けてくれると嬉しいです.

ありがとうございました。他に知っておくべきことがあれば、できるだけ早く答えようとします。