問題タブ [shortest]

興味深い問題にぶつかりました。

無制限のチェス盤、N 人の騎士の開始位置、N の目標位置があります。

タスクは、すべてのナイトがすべてのターゲット位置に到達するための最小移動数を見つけることです。

1 人の騎士の最短経路問題は幅優先探索を使用して解決できることは知っていますが、複数の騎士の場合はどのように解決できるのでしょうか?

私の英語で申し訳ありませんが、めったに使用しません。

デフォルトでは、flex は最長一致ルールを使用します。この動作をオーバーライドして最短のシーケンスに一致させる方法はありますか?

ありがとうございました

次の問題があります。すべてのエッジ {i,j} 間のエッジ コスト cij を持つ有向グラフ G=(V,E) が与えられます。s1,...,sk などの複数のソースと、t などの 1 つのターゲットがあります。問題は、s1,...sk から t までの最小の合計コストを見つけることです。ここで、すべての異なるパスによって訪問された頂点の合計量は M です (ソースとターゲットは訪問された頂点としてカウントされず、0 <= M <= |V|-k+1 であるため、M = 0 の場合、すべてのパスはソースからターゲットに直接行きます。)

私は次のことを思いつきましたが、まだ解決策を見つけていません。

1. この問題は、複数のターゲット (t1、...、tk) と 1 つのソースに似ています。すべてのエッジを逆にして、ソースをターゲットにし、ターゲット ソースを作成するだけです。たとえば、Dijkstra はグラフ内の 1 つのソースから他のすべての頂点への最短パスを計算するので、これは便利だと思いました。

2. 1 つのターゲットと 1 つのソースだけで、最大で最短パスを見つけることができます。Bellman Ford アルゴリズムで訪問した頂点 M の量。これは、訪問した頂点の数を繰り返し増やすことによって行われます。

3. 頂点 v1,...,vk を訪問する必要があるときに、1 つのソースから 1 つのターゲットへの最短パスを見つける問題は、k が小さい場合、次のように解決できます。i) すべての頂点間の最短パスを計算します。ii) k のどれをチェックしてください! 順列は最短です。これは、1) で調整した問題を、あるソースから 1 つの「スーパーターゲット」に移動し、「古い」ターゲット t1=v1,...,tk=vk を強制的に訪問するという問題に変換する場合に役立つと考えました。

残念ながら、1、2、3 を組み合わせても解決にはなりませんが、役立つ場合があります。誰かが解決策を知っていますか？これは効率的に解決できますか？

私は解決するのが非常に難しい問題を抱えており、最速のルートを見つけるためにどのアルゴリズムを使用できるのか疑問に思っています。無向グラフは正と負の調整で構成され、これらの調整は迷路をナビゲートするボットまたは物に影響を与えます。私が抱えている問題は、+または-のループを含む迷路です。例が役立つかもしれません：-

1. ノードAはオブジェクトに10ポイントを与えます

2. ノードBはオブジェクトから15を取得します

3. ノードCはオブジェクトに20ポイントを与えます

route = ""

開始ノードはAで、終了ノードはCです。

グラフ構造を次のように与えます：-

ループのないノードはc+20であるため、ノードcの正の調整は20ですが、ループはありません。

ボットまたはオブジェクトのリソースに10ポイントがある場合、最適なパスは次のようになります：-

route = "a、b、c"

これは実装が非常に簡単です。次の課題は、適切なノードに戻る方法を知ることです。各ノードで、隣接するノードとその調整レベルのいずれかを見つけることができると仮定します。これが次の例です：-

ボットが5ポイントのみで開始した場合、最適なパスは次のようになります。

route = "a、a、b、c"

これは非常に単純なグラフでしたが、ノードがたくさんある場合、ボットは、可能なルートを追跡しながら、適切なノードでループするか、ある適切なノードから別のノードに移動するかを判断するのが非常に困難になります。

そのようなルートはバックトラックキューになります。

より難しい例では、多くの行き来が発生します

ボットには10​​ポイントあります

a> b> a> b> a> b> a> b> a>b>c残り5ポイント。

ボットがそれを行うことができる別の方法は次のとおりです：-

a> a> a> b> c

これはより効率的な方法ですが、これをどのようにプログラムできるかは、部分的に私の質問です。

これを解決するための優れたアルゴリズムを知っている人はいますか。iveはすでにベルマンフォード法とダイクストラ法を調べましたが、これらはループパスではなく単純なパスを提供するだけです。

何らかの形で、または何らかの形のヒューリスティックで再帰的になる可能性がありますか？

あなたのアナロジーを参照してください：-

私はあなたが言っていることを理解していると思います、これまでのところ、少し疑似がより明確になるでしょうroute（）

宿題 (C++) に問題があります。完全な解決策を求めているわけではありませんが、正しい方向に傾けることが役立つ場合があります。:)

NxN ボード (最大 N = 100) とそのボードに 1x2 の図形 (キューブ) があります。立方体は片側が赤く、反対側が青く塗られています。立方体のデフォルトの位置は、ボードの左上隅、青い面が上です。

(4x4 の例、B は青を表します)

黒板に石（障害物）がある可能性があります。 私のフィギュアでできる動き：

• 時計回りに 90/180/270 度回転させます。
• 立方体を右/左/上/下の端で反転させて、「上向きの色」を変更できます

たとえば、デフォルトの位置で右反転を使用すると、次のようになります。

次に、90度回転を使用します。

次に、左にフリップを使用します。

もちろん、回転時や反転時は石に着地できません。したがって、問題は - ボードの特定の構成 (フィギュアの位置と石の位置)に対して、最小数の移動と戻りを使用して、デフォルトの位置 (青い面が上向き!) で「立方体を家に持ち帰る」プログラムを作成することです。可能であれば 1、不可能であれば 0 を返します。

この問題は興味深いと思いますが、少し混乱していることを認めなければなりません。特にブルーサイド/レッドサイドの部分。通常の最短経路アルゴリズムの言語で使用できるこれらの動きを「翻訳」する方法が本当にわかりません (そして、これらのいずれも使用したことがありません)。だから、私はあなたが与えることができるすべてのアドバイスに感謝します！:)

例えば：

m_array = new int[6][6];
m_array[0] = new int[]{2, 0, 0, 0, 0, 0};
m_array[1] = new int[]{0, 2, 0, 0, 0, 2};
m_array[2] = new int[]{2, 0, 0, 1, 0, 0};
m_array[3] = new int[]{0, 0, 0, 0, 0, 0};
m_array[4] = new int[]{0, 2, 0, 0, 2, 0};
m_array[5] = new int[]{0, 0, 2, 0, 0, 0};


最も近い 2 対 1 を見つけるにはどうすればよいですか?

配列パスを返す関数が欲しいのですが、配列のポイントが含まれています。たとえば、関数に「m_array」を指定すると、[2,3][3,4][4,4] のような配列パスである、最も近い 2 対 1 が返されます。

n駅の場合、駅から(i,j <= n)までの直行時間を表すn*n行列Aが与えられます。A[i][j]ij

駅間を移動する人は常に最短時間を求めます。2 つの駅番号a,が与えられた場合b、それらの間の最小移動時間の計算はどのように進めればよいでしょうか?

この問題は、グラフ理論を使わずに、つまり行列 A だけで解決できますか?

ポイントAからポイントEまでの最短距離を返すプログラムを作成することを想定しています。長さを取得するようにコーディングしましたが、実際にポイントを取得する方法がわかりません。

入力に対する答え：shortestPath（["A"、 "B"、 "C"、 "D"、 "E"]、d）は10です。ただし、プログラムは距離も出力する必要があるため、実際には答えが必要です。 be [10、["A"、 "C"、 "D"、 "E"]]

幅優先探索を使用して、単純な（指示されていない）2部グラフで最短のサイクルを見つけるにはどうすればよいですか？

私はしばらくの間、Neo4j 1.9.M03 を評価してきましたが、予期していなかったような結果になりました。

〜140,000頂点のグラフがあります。また、エッジには 3 つのクラスがあります。これらを父、母、夫と呼びましょう。クラスごとに約 80,000 のエッジがあります。プロパティもインデックスもありません。頂点ストアのサイズは約 1.3 MB、エッジ ストアのサイズは約 8 MB です。

データは SQL Server に由来し、SQL から Neo4j への移行の品質は正しいことが知られています。SQL 最短パス ストアド プロシージャは、数十の頂点ペアに対して実行され、最短パスの距離とパスがわかっています。

最短パス クエリは Cypher です。START one=node(0), two=node(1234) MATCH p = shortestPath(one-[*..1000]-two) RETURN p;

部分的なテスト ケース 1:私は夫と父の関係のみを使用し、サイクルの発生 (例:v[0] -> v[1] -> v[2] -> v[0])低い。特定の既知の長いパス (例: ~450 ホップであることがわかっている) で最短パス計算を実行すると、50ms 以内に返されます (キャッシュされていない) ~550 ホップのパス. エッジの一部を除外しているため、長さが増加することが予想されます.

部分的なテスト ケース 2 : 同様に、夫と母の関係のみを使用する場合、サイクルの発生 (たとえばv[0] -> v[1] -> v[2] -> v[0])、低いです。同じ最短パスを実行すると、前と同じ順序で結果が得られます: 約 50 ミリ秒 (非キャッシュ) )、経路長も同様に増加します。

完全なテスト ケース: 私はすべての関係 (父、母、夫) を使用します。一般的なケースのため、サイクルの発生率は予想通り高くなりましたv[0] mother-> v[1] husband-> v[2] <-father v[0]。最短パス クエリを実行すると、JVM が 4 ギガバイトのメモリを割り当て、計算が完了しません。これが問題です。

私の論文は、サイクルの定期的な発生がこの動作を引き起こしているということです。そうでなければ、最短パスアルゴリズムがサイクルを考慮していない限り、親エッジの別のクラスを追加するだけで、パフォーマンスにそれほど大きな違いはないと思います。

Java API を直接使用して Dijkstra アルゴリズムを適用し、すべてのエッジでコストを 1 に設定し、使用した標準の ShortestPath アルゴリズムと同様の結果を達成しました。その結果、IntelliJ デバッグ時間の 6 分後にこの例外を受け取りました。

私が正しいと思いますか？これは、グラフ データベースまたはその最短パス アルゴリズムの既知の制限ですか? 以前に訪れた頂点がハッシュ テーブルに格納されないというのは、非常にばかげているように思えます。そのため、最短パス アルゴリズムは、以前に訪れた頂点からのパスを 2 回以上試行しません。

2013 年 1 月 25 日更新

フォローできるように Github リポジトリを作成してください。

2013 年 2 月 7 日更新

受け入れられた回答を参照してください。要するに、サイクルはそれとは何の関係もありません。