2

私はSQLを初めて使用し、隣接リスト、ネストされたセット、クロージャーテーブルについて学んでいますが、私が理解したことから、これらのソリューションは通常非循環データに適用されます。

この種の問題は、Neo4j などのグラフィカル データベース エンジンに適している可能性があることを認識しており、それについても調査しています。しかし、この質問については、SQLite でこの目標を達成できるかどうかを具体的に知りたいです。

これに対する可能な答えを出す前に、問題をよりよく定義または説明する方法を理解するのを手伝ってください. 問題の定義が洗練されたら、正しい方向性 (テクニック、参考資料) を教えてくれます。

目的:

  1. エリアのリストとそれらがどのように接続されているかを維持します。
  2. エリアには、国、高速道路、州、市、近隣など、さまざまなタイプがあります。
  3. 領域は、循環 (無向) で接続できます。
  4. エリアには複数の出口がある場合があります。
  5. エリア内で、ある出口から別の出口への加重リストを維持します。
  6. ある地域から別の地域への最適な経路を抽出します (この近隣から最も近い高速道路まで)。

仮定:

  1. SQLite 3 (最新バージョン) を使用します。
  2. 小さなデータ セット (< 1,000 エリアと接続、< 5 秒の DB 作成)。
  3. 比較的静的 (< 5 回の挿入または更新/年)。
  4. 更新するよりもデータベースを最初から再作成する方が簡単でしょうか?
  5. ハイウェイはエリアであり、コネクタではありません。
  6. 道路は、論理的なコネクタであり、長さも重さもありません。

エリアと接続は、複数のドアのある部屋がたくさんある家のようなものです。ドアは部屋を接続します。ドアを通過するトラバーサル ウェイトはありません。ドアを選択する際の重みは、ドア間の距離に由来します。廊下は引き戸のようなものなので重量があり、タイプの部屋とされています。部屋のサイズは大きいかもしれませんが、2 つのドアだけが近くにある場合、その重量は小さいかもしれません。私の目的で重要なのは部屋の大きさではなく、ドア間の距離です。

いつものように、お読みいただき、建設的なコメントをお寄せいただきありがとうございます。

4

1 に答える 1

0

はい、SQLite を使用してこの種のデータを保存することは可能です。これは実用的ではなく、パフォーマンスの問題が発生する可能性があります。そのようなデータを大量に保存する予定で、スケーラブルなソリューションが必要な場合は、グラフ DB を使用する必要があります。

最大 1000 個のノードを保存する場合は、SQLite で単純な処理を行うことができます。

特に、更新の数が非常に少ないため、距離を事前に計算できます。そのため、毎回実際に再計算する必要はなく、DB からロードするだけです。

問題をグラフとして表す必要があると思います。

グラフ表現

ノードは「ドア」であり、それらの間の距離を縁取ることができます。これをリレーショナル データベースに簡単に格納できます。(エリア(ID,名前), ドア(ID,エリア1,エリア2) ドアドア距離(ドア1, ドア2, 距離))

これらのデータを保存すると、すべてのドアからすべてのドアまでの最短経路を計算できます。これを新しいテーブルに保存できます。(距離 (ドア 1、ドア 2、パス、距離))

最短経路を計算するには、さまざまなアルゴリズムを見つけることができます: 最短経路アルゴリズム

この後、ドアの各ペア間の最短経路が得られます。

これからの唯一の質問は、開始エリアから目的エリアのどのドアに移動するかという魔女のドアです。

これほど正確になりたくない場合は、最短のパスを選択します。それ以外の場合は、エリアの開始点からドアの距離を維持する必要があります。A; 領域の中心から開始すると想定できるため、中心 B からのドアの距離を保存できます。正確なドアの位置を保存し、正確な開始点からのドアの距離を計算することで、より正確にすることができます。

どちらの場合も、開始エリアと目的エリアの両方で、コストが最も低いドアを選択する必要があります。

合計コスト: (徒歩からドアまでの距離) + (開始ドアから目的地へのドア パス) + (目的地エリア内の目的地までの徒歩)

私はこれをこのようにします。お役に立てば幸いです、楽しんでください！

于 2013-12-27T11:02:16.523 に答える