最小積和コストパス

私はパスの複数のエッジがそのタイプのコストを持っている場合、コストの各タイプがパスの総コストで1回しか考慮されないという点で、通常の最短パスとは異なる最小コストパス選択問題を持っています。たとえば、以下の例では、SからDに向かう赤のパスのコストはC(F1)+
C(F2)です。
F1とF2はパスに沿って複数回現れますが、それぞれのF1は1回だけカウントされます。このパスは、他のパスもF3を持つため、コストはC(F1)+
C(F2)+ C(F3)となるため、最小コストパスです。コストは正の実数であり、各項目で知られています。

異なる辺を見ると、パスのコストは、パスの辺に関連付けられたアイテムの和集合のコストの合計です。

この問題は以前に解決されていますか?
(近似アルゴリズムのように)よく似たグラフの問題がありますか?そして、これは難しい問題だと思いますか?

Minimum Union-Sum Cost Path

ベストアンサー

あなたの問題はSet
Coverを一般化していますが、サブモデルの制約を受けた線形コスト関数を最小限に抑えるという古典的問題の特別なケースです。欲張りなSet-Coverアルゴリズムとその対数近似率が自然に拡大する問題です。
1980年代のウォルシー)。その結果、あなたの問題の多時間対数近似があります。(P =
NPを除いて)あなたができる最高です。ここに詳細があります。

あなたの問題のインスタンス$ I $が与えられた場合、$ p $の$ e $を超えるすべてのソースからターゲットへのパス$ p
$の最小値を$ N(I)$と定義します。ラベル$ F_i $、$ e $が持つラベルの数。 P =
NPでない限り、あなたの問題に対して得られる最良の近似比は$ ln
N(I)$(低次の項まで)です。推論は2つのステップで行われます。硬度結果、次にポリタイム$ ln N(I)$ –
近似アルゴリズムです。


硬度の結果は、問題がSet Coverを含むことを示しています。

Lemma 1. Unless P=NP, the problem has no
$((1-epsilon)ln N(I))$-approximation algorithm for any
$epsilon>0$.

Proof. We give an approximation-preserving reduction
from unweighted Set Cover. Given an unweighted Set-Cover instance
$(S_1, S_2, ldots, S_m)$ on a universe $U={1,2,ldots,n}$,
construct a multigraph with vertex set ${1,ldots,n,n+1}$ where,
for each element $iin U$, for each set $S_j$ containing $i$, there
is an edge $(i, i+1)$ with a single label $F_j$. Set $C(F_j) = 1$
for each $j$.

(注:マルチグラフが許されない場合、ラベル$ F_j $を持つ各$(i、i + 1)$をパス$(i、v、 v(i、j)、i +
1)$は新しい頂点であり、エッジ$(i、v(i、j))$はラベル$ F_j $を持ち、エッジ$ …)

頂点$ 1 $から頂点$ n + 1 $までの任意のパス$ p $に対して、$ C(p)= {S_j:F_j text
{サイズは$ p $のコストに等しく、その逆も同様です。また、このインスタンスの$ N(I)$は$ n $と等しくなります。

あなたの問題の$(1- ε) NN(I)$近似アルゴリズムがあれば、Set Coverのための$(1- ε) ln n
$近似アルゴリズムがあります。 P = NP以外の場合は、そのようなアルゴリズムはありません。 $ ~~~ Box $


ここでは上限があり、問題はサブモジュール制約のもとで線形コスト関数を最小化する特殊なケースであることを示しています。

Lemma 2. The problem has an
$H_{N(I)}$-approximation algorithm, where $H_i approx gamma + ln
i$ is the $i$’th Harmonic number.

Proof. Fix an instance $I$ of the given problem. Assume
without loss of generality that each edge in the graph has only one
label. (Otherwise, for any edge having, say, labels $F_{i_1},
F_{i_2},ldots,F_{i_k}$, replace the edge by a path of $k$ edges,
where the $j$th edge has label $F_{i_j}$. This does not change
$N(I)$.)

任意の$ S $ラベルが与えられた場合、ラベルが$にない$ p $の辺の数の、ソースからデスティネーションまでのすべてのパス$
p $の最小値を$ phi(S)$と定義するS $。 $ S $のコストを$ S
$のラベルのコストの合計と定義します。その後、

  • $ phi $はスーパーモジュラです。
  • $ phi( emptyset)= N(I)$、
  • $ S $のラベルのみを使用するソースから宛先へのパスがある場合に限り、

  • $ phi(S)= 0 $
  • $ S $の費用は$ S $のラベルの費用です。

greedy-set-coverアルゴリズムの Wolseyの汎化を適用します(< $ S $ = $
$でほぼ最小コストの集合$ S
$を見つけるために、副次的な制約のもとで線形関数を最小化するそのアルゴリズムは次のとおりです。

  1. $S leftarrow emptyset$
  2. while $phi(S) > 0$:

  3. . . choose label $F_i$ maximizing
    $displaystylefrac{phi(S) –
    phi(Scup{F_i})}{C(F_i)}.$

  4. . . add $F_i$ to $S$
  5. return $S$

このアルゴリズムは、最小$ H_D $のコストの解の$ S $を計算することが知られている。ここで、$ D =
max_ {S、F_i} { phi(S) – phi(S cup {F_i }) le phi(
emptyset)= N(I)$です。

検査により、アルゴリズムは多項式時間で実行するように実施することができる。

そして、$ Sを$ phi(S)= 0 $とすると、$ P $のコストで、ソースから目的地までの経路$ p
$をポリタイムで簡単に計算することができます。 $ ~~ Box $


私はここで何かを見逃しましたか?

ウォルシーのオリジナル論文:

[1] Lです。ウルシー。サブモジュラ集合カバー問題に対する貪欲アルゴリズムの解析。
Combinatorica、2(4):385-393、1982.
を参照)要約はこちらを参照してください)。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です