正と負のエッジを持つ有向グラフで、ソースから宛先への最短パスを見つけます。パスのどのポイントでも、負になる前に来るエッジの合計がありません。そのようなパスが存在しない場合は、それも報告してください。
修正されたベルマンフォードを使用しようとしましたが、正しい解決策が見つかりませんでした。
いくつかのポイントを明確にしたいと思います：
確かにこれは建設的な答えではありませんが、コメントを投稿するには長すぎます...
この問題には、離散ナップサック問題だけでなくバイナリ問題も含まれているように思われるため、最悪の場合の実行時間はせいぜい疑似多項式です。次のように接続され、重み付けされたグラフについて考えてみます。
次に、同等のバイナリナップサック問題は、Σaiを最大化する集合{a0、...、an}から重みを選択しよう とします。ここで Σai < Xです。
ちなみに、重み付きループを導入すると、代わりに無制限のナップサック問題を簡単に構築できます。
したがって、選択する可能性のある実用的なアルゴリズムには、「平均的な」ケースと見なすものに応じた実行時間があります。私が考慮しなかった、または自由に使える問題に制限はありますか？あなたはそれがO（ n 3）の問題であるとかなり確信しているようです。（この場合のnは何ですか？）
Peter de Rivazはコメントの中で、この問題には特別な場合としてハミルトン経路が含まれていると指摘しました。彼の説明は少し簡潔で、詳細を理解するのに時間がかかったので、苦労しているかもしれない他の人のためにいくつかの図を描きました。この投稿コミュニティウィキを作成しました。
例として、6つの頂点を持つ次のグラフを使用します。そのハミルトン経路の1つは太字で示されています。
ハミルトンパスを見つけたいn個の頂点を持つ無向グラフが与えられた場合、n 2 個の頂点に加えて、START頂点とEND頂点を持つ新しい重み付き有向グラフを作成します。元の頂点viと新しい頂点wikに0≤ < em>i、 k < n のラベルを付けます。元のグラフのviとvjの間にエッジがある場合、0≤ < em> k < n -1の場合、新しいグラフには、重み-2のwikからwj （k +1）までのエッジがあります。jそして、重み-2iでwjkからwi（k +1）まで。STARTからwi0までの重み2n− 2 i − 1と、wi（n −1 ）からENDまでの重み0のエッジがあります。
この構造は、スコア2 n − 1から始めて、wijにアクセスするたびに2iを引くのと同じであると考えるのが最も簡単です。（これが私が下のグラフを描いた方法です。）
STARTからENDまでの各パスは、正確にn + 2個の頂点（各行から1つ、さらにSTARTとEND）にアクセスする必要があるため、パスに沿った合計がゼロになる唯一の方法は、各列に1回だけアクセスすることです。
これが、6つの頂点を持つ元のグラフが38の頂点を持つ新しいグラフに変換されたものです。元のハミルトンパスは、太字で描かれたパスに対応しています。パスに沿った合計がゼロであることを確認できます。
更新： OPには現在、数回の説明があり、現在は別の問題です。問題の最初のバージョンに関する私の考え（またはむしろそれについての私の理解）を文書化するために、これをここに残しておきます。問題の現在のバージョンに対して新しい答えを試してみます。 更新の終了
OPが未解決の質問のいくつかを明らかにしていないのは残念です。私は次のことを想定します：
最初の仮定は明らかに一般性を失うことはありませんが、（2番目の仮定を介して）nの値に大きな影響を与えます。最初の仮定がなければ、小さな（固定された）グラフでさえ、重みを無制限に変化させることにより、任意の長い解を持つことができます。
私が提案するアルゴリズムは非常に単純で、よく知られているグラフアルゴリズムに似ています。私はグラフの専門家ではないので、場所によっては間違った言葉を使うかもしれません。お気軽に訂正してください。
即時の行き止まりではない各「ステップ」が、新しい（頂点、コスト）組み合わせを作成することは明らかです。これらの組み合わせのうち最大でn*n ^ 2 = n ^ 3が格納されるため、ある意味で、このアルゴリズムはO（n ^ 3）です。
さて、なぜこれが最適なパスを見つけるのですか？私には本当の証拠はありませんが、以下の考えが私がこれで十分だと思う理由を正当化すると思います。そしてそれらが本当の証拠に変わる可能性があるかもしれません。
私たちが示さなければならないのは、条件c <= n^2で十分であることは明らかだと思います。
まず、任意の（到達可能な）頂点にn未満のコストで到達できることに注意してください。
（v、c）を最適パスの一部とし、c> n ^2とします。c>nであるため、（v、c）に到達する前に、パス上に何らかのサイクルが必要です。ここで、サイクルのコストは0<m1です。 <nであり、（v、c）に到達した後、パス上に何らかのサイクルが存在する必要があります。ここで、サイクルのコストは0>m2>-nです。
さらに、上記の最初のサイクルに接するパスによって、コスト0 <= c1 <nのソースからvに到達可能にし、コスト0 <= c2 <nのパスによって、vから宛先に到達可能にします。上記の他のサイクルに触れます。
次に、コストc1、c1 + m1、c1 + 2 * m1、...でソースからvへのパスを構築し、コストc2、c2 + m2、c2 + 2 * m2、..でvから宛先へのパスを構築できます。 。c1 + c2 + a * m1 + b * m2が最小になるように、0 <= a<=m2および0<=b <= m1を選択します。これにより、最適なパスのコストが削減されます。この最適なパスでは、vのコストはc1 + a * m1 <n^2になります。
m1とm2のgcdが1の場合、コストは0になります。gcdが1より大きい場合、gcdが1になるように他のサイクルを選択できる可能性があります。それが不可能な場合は、それも不可能です。最適なソリューションのために、そして最適なソリューションのための正のコストがあります。
（はい、この証明の試みにはいくつかの問題があります。いくつかの正または負のサイクルコストなどのgcdを取る必要があるかもしれません。しかし、反例に非常に興味があります。）
ここにいくつかの（Python）コードがあります：
def f(vertices, edges, source, dest):
# vertices: unique hashable objects
# edges: mapping (u, v) -> cost; u, v in vertices, cost in {-1, 1}
#vertex_costs stores the possible costs for each vertex
vertex_costs = dict((v, set()) for v in vertices)
vertex_costs[source].add(0) # source can be reached with cost 0
#vertex_costs_from stores for each the possible costs for each vertex the previous vertex
vertex_costs_from = dict()
# vertex_gotos is a convenience structure mapping a vertex to all ends of outgoing edges and their cost
vertex_gotos = dict((v, []) for v in vertices)
for (u, v), c in edges.items():
vertex_gotos[u].append((v, c))
max_c = len(vertices) ** 2 # the crucial number: maximal cost that's possible for an optimal path
todo = [(source, 0)] # which vertices to look at
while todo:
u, c0 = todo.pop(0)
for v, c1 in vertex_gotos[u]:
c = c0 + c1
if 0 <= c <= max_c and c not in vertex_costs[v]:
vertex_costs[v].add(c)
vertex_costs_from[v, c] = u
todo.append((v, c))
if not vertex_costs[dest]: # destination not reachable
return None # or raise some Exception
cost = min(vertex_costs[dest])
path = [(dest, cost)] # build in reverse order
v, c = dest, cost
while (v, c) != (source, 0):
u = vertex_costs_from[v, c]
c -= edges[u, v]
v = u
path.append((v, c))
return path[::-1] # return the reversed path
そして、いくつかのグラフの出力（エッジとその重み/パス/パスの各ポイントでのコスト。申し訳ありませんが、素敵な画像はありません）：
AB+ BC+ CD+ DA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-
A B C D A X Y H I J K L M H
0 1 2 3 4 5 6 7 6 5 4 3 2 1
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-
A B C D E F G A B C D E F G A B C D E F G A X Y H I J K L M H I J K L M H I J K L M H I J K L M H
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-
A X Y H
0 1 2 3
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-
A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G A X Y H I J K L M N O P H I J K L M N O P H I J K L M N O P H I J K L M N O P H I J K L M N O P H
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
その出力を生成するコードは次のとおりです。
def find_path(edges, source, path):
from itertools import chain
print(edges)
edges = dict(((u, v), 1 if c == "+" else -1) for u, v, c in edges.split())
vertices = set(chain(*edges))
path = f(vertices, edges, source, dest)
path_v, path_c = zip(*path)
print(" ".join("%2s" % v for v in path_v))
print(" ".join("%2d" % c for c in path_c))
source, dest = "AH"
edges = "AB+ BC+ CD+ DA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-"
# uv+ means edge from u to v exists and has cost 1, uv- = cost -1
find_path(edges, source, path)
edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-"
find_path(edges, source, path)
edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-"
find_path(edges, source, path)
edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-"
find_path(edges, source, path)
Kaganarが指摘しているように、ポリタイムアルゴリズムを取得するには、基本的にいくつかの仮定を行う必要があります。エッジの長さが{-1、1}であると仮定しましょう。グラフを前提として、重み付きの文脈自由文法を作成します。この文法は、ソースから宛先までの有効なパスを、超過した1エッジの数に等しい重みで認識します（バランスのとれた括弧の文法を一般化します）。非終端記号ごとに、RHSに非終端記号がないプロダクションがあるかどうかに応じて、すべてを無限大または1に初期化し、n-1回緩和することによって最も安価なプロダクションのコストを計算します。nは非終端記号の数です。
人々は速い解決策が存在しないことを示しましたが（P = NPでない限り）。
ほとんどのグラフ（95％以上）では、かなり迅速に解決策を見つけることができるはずです。
サイクルがある場合、通常は多くの解決策があり、そのうちの1つを見つけるだけでよいという事実を利用します。私のアイデアにはおそらくいくつかの明白な穴があるので、私に知らせてください。
Ideas:
1.目的地に最も近い負のサイクルを見つけます。サイクルと目的地の間の最短距離をd（end、negC）として示します
（これは可能だと思います。1つの方法は、フロイドを使用して負のサイクルで（i、j）を検出し、次に、負のサイクルに関連する何かに到達するまで、目的地から幅優先探索を行うことです。）
2.開始ノードに最も近い正のサイクルを見つけ、開始からの距離をd（start、posC）として示します。
（グラフの95％で、これらのサイクルを簡単に見つけることができると主張しています）
Now we have cases:
a) there is both the positive and negative cycles were found:
The answer is d(end,negC).
b) no cycles were found:
simply use shortest path algorithm?
c) Only one of the cycles was found. We note in both these cases the problem is the same due to symmetry (e.g. if we swap the weights and start/end we get the same problem). I'll just consider the case that there was a positive cycle found.
find the shortest path from start to end without going around the positive cycle. (perhaps using modified breadth first search or something). If no such path exists (without going positive).. then .. it gets a bit tricky.. we have to do laps of the positive cycle (and perhaps some percentage of a lap).
If you just want an approximate answer, work out shortest path from positive cycle to end node which should usually be some negative number. Calculate number of laps required to overcome this negative answer + the distance from the entry point to the cycle to the exit point of the cycle. Now to do better perhaps there was another node in the cycle you should have exited the cycle from... To do this you would need to calculate the smallest negative distance of every node in the cycle to the end node.. and then it sort of turns into a group theory/ random number generator type problem... do as many laps of the cycle as you want till you get just above one of these numbers.
幸運を祈ります。私の解決策がほとんどの場合にうまくいくことを願っています。
ここでは再帰ブルートフォーシングを使用します：（言語固有ではないことを確認するための擬似コード）のようなもの
必要になるだろう：
あなたはやる：
function(int xPosition, int yPosition, int steps)
{
if(You are at target AND steps < Shortest Path)
Shortest Path = steps
if(This Position is NOT legal)
/*exit function*/
else
/*try to move in every legal DIRECTION, not caring whether the result is legal or not
but always adding 1 to steps, like using:*/
function(xPosition+1, yPosition, steps+1);
function(xPosition-1, yPosition, steps+1);
function(xPosition, yPosition+1, steps+1);
function(xPosition, yPosition-1, steps+1);
}
次に、function（StartingX、StartingY、0）;で実行します。
最短パスは静的外部intに含まれます
いくつかのポイントを明確にしたいと思います：
現在の仮定は次のとおりです。
一般性を失うことなく、頂点の数は最大でnであると仮定できます。グラフを再帰的にウォークし、各頂点のコスト値を覚えておいてください。頂点のコストがすでに記憶されている場合、またはコストが負になる場合は停止します。
O（n）ステップの後、目的地に到達していないか、解決策がありません。そうでなければ、O（n）頂点のそれぞれについて、最大でO（n）の異なるコスト値を覚えており、これらのO（n ^ 2）の組み合わせのそれぞれについて、他の頂点への歩行が最大n回失敗した可能性があります。 。全体として、それはO（n ^ 3）です。qed
更新：もちろん、また何か怪しいものがあります。仮定3はどういう意味ですか：問題に解決策がある場合、O（n）の長さのパスが存在しますか？解決策がないかどうかも報告する必要があるため、どの解決策もそれを検出する必要があります。しかし、それを検出することは不可能です。これは、アルゴリズムが機能する個々のグラフのプロパティではないためです（これは漸近的な動作です）。
（目的地に到達できるすべてのグラフが長さO（n）の解のパスを持っているわけではないことも明らかです：重み-1のm個のエッジのチェーンを取り、その前にm個のエッジと総重みの単純なサイクルを取ります+1）。
[私は今、他の答え（問題の最初のバージョンを試みた）からのPythonコードのほとんどが再利用できることに気づきました。]
ステップ1：答えは最大で2 * nになることに注意してください（存在する場合）。
ステップ2：[vertex][cost]のペアである頂点を持つ新しいグラフを作成します。（2 * n ^ 2頂点）
ステップ3：新しいグラフのすべてのエッジが1に等しく、[vertex][cost]ペアごとに最大で2*nであることに注意してください。
ステップ4：[start] [0]から始めて、このグラフに対してdfsを実行します。
ステップ5：[finish] [k]にアクセスできるように、最小のkを見つけます。
全体の複雑さは最大でO（n ^ 2）* O（n）= O（n ^ 3）です
編集：ステップ1の明確化。
最初からアクセス可能な正のサイクルがある場合は、nまで行くことができます。これで、アクセス可能な頂点まで歩くことができます。エッジはn個以下で、それぞれが+1または-1のいずれかであり、[0;2n]の範囲が残ります。それ以外の場合は、負のサイクル、または負のサイクルにないn +1以下のいずれかをウォークスルーし、[0;n]の範囲を残します。