問題タブ [shortest-path]

一連のグラフ座標があり、それらすべてを通る最短の片道パスを見つける必要があります。始点と終点は決まっていませんが、各ポイントは 1 回だけタッチする必要があり、最適な原点に戻る必要はありません。

私はいくつかの TSP アプローチを試しましたが、それらはすべて最後に原点に戻ることに基づいているようで、この場合は非常に非効率的な結果をもたらします。

例

1、13
3、0
3、7
2、21
2、11
3、12
1、19
3、6

に解決します

3, 0
3, 6
3, 7
3, 12
2, 11
1, 13
1, 19
2, 21

ノート：

はい、検索機能を試しました。基本的に同じ質問 アルゴリズムがあります。すべてのポイント間の最短パスです が、唯一の本当の答えは TSP です。

100% 正確である必要はありません。順列メソッドは既に持っていますが、遅すぎます。少なくとも 25 ～ 30 ポイントを処理する必要があります。適切な近似値で解決することでうまくいきます。

前もって感謝します。

明確にするために編集します。TSP は img #1 のように解決する傾向があります。私の望ましい結果は img #2 です
。img 3 は TSP を介して解決された上記のサンプルであり、img #4 が望ましいです (可視性のために x 座標を -.5 後ろにシフト)

カップル#1 = TSP、#2 = 望ましい

基本的には、最も効率的な開始点と終了点を使用して、n 個のポイントを接続する最短のチェーンが必要です。

私は、ドライバー、潜在的な乗客、およびその場所に関するデータを取り込むシステムを作成し、いくつかの制約が与えられたドライバーで持ち上げることができる乗客の数を最適化しようとしています。私は python-constraint モジュールを使用しています。決定変数は次のように表されます。

したがって、p の値と driver_set および Passenger_set を出力すると、次の出力が得られます (指定したテスト データを使用)。

したがって、3 人の乗客と 2 人の運転手がいます。変数 (2,0) は、乗客 2 が 0 号車に乗っていることを意味します。次の制約を追加して、乗客が複数の車に乗らないようにし、ドライバーが座席よりも多くの人を乗せることができないようにしました。

これは機能しました - 生成されたすべてのソリューションがこれらの制約を満たしました。ただし、ドライバーが特定の距離を超えて移動することを解決策に含めてはならないという制約を追加したいと思います。ドライバー (driver_set のエンティティと同じ形式) を取り込んで、ドライバーがすべての乗客をピックアップするための最短距離を計算する関数があります。次のような制約を追加しようとしました。

これにより、次のエラーが発生しました。

この制約を python-constraint に対してどのように定義する必要があるかわかりません。各ドライバーには最短距離の値が 1 つしかありません。これにはラムダ関数を使用する必要がありますか?

編集

これのラムダバージョンを実装しようとしましたが、ラムダ構文がダウンしていないようです。私はいたるところを見てきましたが、これの何が問題なのかを見つけることができないようです。基本的に、コードの最後のスニペットを置き換え (getRouteDistance(driver) の値を制限するための制約を追加)、代わりに次のようにします。

しかし、その後、このエラーが発生しました (編集した行から呼び出されたのではなく、後に続く problem.getSolutions() から呼び出されたことに注意してください):

他の誰かがこのようなことをしようとしましたか? 制約ライブラリがこれを許可しない理由がわかりません。

次の問題が NP-HARD にあることを知っています: 単純なグラフ G=(V,E)、2 つの頂点 v、V の v'、整数 B、および非負の長さ関数 len: E-> Z+ が与えられた場合、長さが B 未満の v から v' への単純なパスはありますか?

私の質問は次のとおりです。以前と同じ条件が与えられた場合、頂点 v から v' までの G 内の必ずしも単純ではない最長のパスを見つけることに関心がある場合、問題はまだ NP-HARD にありますか?

注: ハミルトンパスをそれに還元しようとしましたが、NP に還元可能な問題があるかどうかを証明することはまだできません。ゲイリー＆ジョンソンも調べましたが、見つかりませんでした。

この問題が NP-HARD であるかどうかを証明するためのヒントを教えてください。前もって感謝します！

これは私がここのサイトから入手したコードであり、このA*の実装が正しいかどうか知りたいです。私はそれを見て、ウィキペディアのページと比較しましたが、それは有効なようです。私が尋ねる理由は、サイトにこのコードにまだバグがあると書かれているので、見つけようとしましたが見つかりませんでした。ただし、出発地と目的地を入力パラメータとして使用するように変更したい

Pqueueのコードはここにあります

ローワンさんはパリのウォーキングツアーを計画しています。しかし、彼は少し怠け者なので、行きたい場所をすべて通る最短経路をたどりたいと思っています。彼はバスで最初の場所に行き、最後の場所から別の場所に戻る予定なので、開始場所と終了場所を自由に選択できます。あなたは彼を助けることができますか？

入力

入力の最初の行には、訪問する場所の数 (n) が含まれています。次に、次の n 行で、訪問する各場所の座標を見つけます。次に例を示します。

3

132 73

49 86

72 111

出力

テスト ケースごとに、ある場所から別の場所への徒歩距離がユークリッド距離であると仮定して、Rowan 氏がすべての場所を訪れるために歩かなければならない最小距離を含む 1 行をプログラムで出力する必要があります。アルゴリズムは、小数点の右側に正確に 3 桁の数字を固定小数点表記で出力し、先頭にスペースを入れない必要があります。訪問する場所は最大で 12 か所あります。例

入力例:

3

132 73

49 86

72 111

出力例:

104.992

私は宿題のためにこのコードに取り組んできましたが、うまくいかず、これが最善のアプローチであるかどうか疑問に思い始めました..

問題は floyd-warshall 関数です。floydwarshall(path, n, next); の前後で path が同じです。floydwarshall(path, n, next);

2次元平面上にn個の点があり、n <= 12であり、すべての点を含む利用可能な最短経路の距離が必要で、それらのいずれかから始まりますが、閉回路は作成されません

フロイドマーシャル、旅行セールスマン問題、その他のアルゴリズムを試してみましたが成功しませんでした。

問題は私の先生にとっては簡単だと考えられているので、アロラ近似などは必要ないと思いますが、これを解決するための最良のアプローチは何かわかりませんが、おそらくいくつかの動的アルゴリズムなど

助けはありますか？

私は2つの配列を持っています。1つは8000のエントリを持つノード-ノードコスト配列[a_node、b_node、cost]で、もう1つはノードと座標[node、x、y]の関連付けで、約8000のエントリもあります. これら2つの静的配列を持つ方が良いですか、それともこれらをデータベースに保存し、そこからパフォーマンスの問題として配列を作成する方が良いですか?

これら 2 つの配列は、最短パス アルゴリズムを実行するために使用されます。

ノード-ノード-関連コストのコレクションであるセットデータがあります。このコストは、フィート単位の距離として表されます。

また、各ノードのxy座標もあります。ここで、A *アルゴリズムで、ノードからノードへのコスト+中間ノードから宛先へのヒューリスティックコストを追加する必要があります。ただし、これら2つの値は、同じメトリック/単位である必要があります。1つをフィートで、もう1つを座標距離にすることはできません。

これを行うには、最初にスケーリング係数を見つけて、コストをフィートからxy座標距離にスケーリングする必要があることを知っています。右？私が言えるのは、このコストはすべてスケーラブルであるということです。したがって、このベータ値は、ノードとノードのすべてのペアで同じになります。質問は、この値をどのように見つけるかです。

私が今やったことは、ノード間の座標距離を見つけ、それからフィート単位のコストと比較することです。したがって、ベータ版を見つけることができます。これは一定であり、すべてのノード-ノード-コスト（フィート）で機能するはずです...しかし、これが正しいかどうかはわかりません。私はここで魔法のトリックを探しているのではなく、これを解決するための簡単な方法/数学を探しています

最短経路アルゴリズム（2Dウェイポイントパスファインディング：curLocationからtargetLocationに移動するWPの組み合わせ）に関する一般的なアドバイスを求めた後、より具体的な実装（500以上のウェイポイント/ノードの最短経路アルゴリズム（例：Dijkstra））について尋ねた後I JUNGライブラリ（http://jung.sf.net/）を使用することを決定しました。

私の目標は、各ポイントがx距離内にあるすべてのポイントに直接接続されているポイントのリスト（サイズ〜1000）からのポイントの任意の組み合わせを使用して、ポイントAからポイントBへの最短経路を取得することです。

このために、ツリーマップを設定する必要があります。これはツリーマップの実装のリストだと思います：http：//jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

あれは正しいですか？現在、これらの実装はすべてスパースツリーマップに制限されていますが、かなり密度の高いツリーマップを作成する必要があります。

では、目標を達成するためにJUNGでどのツリーマップを使用する必要がありますか？