0

ここで何か提案があるかどうか疑問に思っています。最短経路検索ソリューションをテストするために、多くのサンプル マップ/グラフが必要です (100 個以上必要だと言われました)。私のコードは、都市設定の OpenStreetMap マップを使用してジャンクションの総数を数千に制限するシミュレーターで動作することになっています。問題は、シミュレーターで提供されるマップが 2 つまたは 3 つしかないことです。私の見方では、ここにはいくつかの選択肢があります。

  1. 独自のランダム グラフ ジェネレーターを作成します。おそらく、多くの作業 (あなたはそう思いますか? -- 私はこれまでやったことがありません) と車輪の再発明です。
  2. 市販のソリューションを使用してください。私は地図のようなグラフを生成するものを知りません (まあ、少なくとも JUNG では見つかりませんでした :-) )
  3. 何らかの自動化された方法で、OSM か​​らそれらを取得します。15000 ノード未満の要件を満たす 100 以上の都市マップを自分で探しに行くつもりはありません。ただし、それを自動化するのも簡単ではないと思います。

3は難しいと思います。既製のソリューションに関するアドバイスはありますか? または自分で書くことについてのコメント？私は決して経験豊富なプログラマーではありませんが、数日与えられました。

4

1 に答える 1

1

最初の考え：

既知の問題があり、その解決策をテストする必要があります。大量のテスト データを生成し、検証済みのアルゴリズムで正しい解を見つけてから、生成されたデータ セットに対してアルゴリズムを実行し、結果を比較します。（または、検証済みのダイクストラアルゴリズムの実装をダウンロードするだけです。このアルゴリズムの実装はあなたの仕事だと思います）

2番目の考え：

ランダムに生成されたデータ セットは、アルゴリズムをテストする最良の方法ではありません。アルゴリズムが失敗する可能性があるケースについて考え、対応するテストを作成する必要があります。たとえば、1 つのノードを持つグラフ、サイクルを持つグラフ、線形グラフ (N1---N2---N3-...-Nn)、最大ノード数を持つ完全なグラフなどです。これら 4 つのテストと 2 ～ 3 個の小さなランダム テストを作成すれば、アルゴリズムが正しく実装されていることを確認するのに十分だと思います。

于 2010-02-18T22:39:41.843 に答える