重なり合う辺の数を最大にしながら最短経路を見つける

2つの任意のノード間の最短経路問題は、広範囲にカバーされているものであり、解はよく知られている。エッジコストは任意であると考えてください。

次のような変形を考えてみましょう。

任意の2対の任意のノード間の2つの最短経路を見つけるが、コストは経路の長さから正の係数マイナス2パスの共通エッジ数を掛けたものとみなされる。すなわちコストは$
P_1 | + | P_2 | -C | P_1 cap P_2 | $。

この問題はこれまでに対処されていますか?

ベストアンサー

There is a polynomial-time algorithm for this problem in the
case where $C le 2$. There is also a polynomial-time algorithm
when $C > 2$, assuming paths are not required to be simple. If
you require paths to be simple and have $C>2$, the problem is
NP-hard, as
explained by Neal Young
. So in the remainder of this answer I
will assume that either $C le 2$, or $C >2$ and you allow
non-simple paths. I will describe the polynomial-time algorithm
below.

まず、最適解(wlog)において、2つの経路の共通部分は連続していなければならない、すなわち、$ P_2 $と重複する$ P_1
$の1つの連続セグメントが存在し、残りは存在しない。特に、$ s_1 leadsto t_1 $と$ s_2 leadsto
t_2 $の間の最短経路が必要な場合、$ P_1 $が$ s_1 leadsto leadsto
wという形式を持つような頂点$ v、w $が存在しなければなりません leadsto t_1 $と$ P_2 $は$ s_2
leadsto leadsto leadsto t_2 $と$ s_1 leadsto v $と$ w leadsto
t_1 $部分は$ P_2 $と重複しません。 v leadsto w $は両方に共通です。このソリューションのコストは、

$$ | s_1 leadsto v | + | w leadsto t_1 | + | s_2 leadsto v
| + | w leadsto t_2 | +(2-C)| v leadsto w |。$$

したがって、すべてのペアの最短パスとすべてのペアの最長パスを計算します。 $ a $から$ b
$までの距離(最短経路の長さ)を$ d(a、b)$とし、$ d ^ *(a、b)$を最長パス。 $ C le 2
$の場合は、$ v、w $、およびcomputeのすべての選択肢を繰り返し処理します

d(w、t_2)+(2-C)d(v、w)。$$ d(s_1、v)+ d

If $C > 2$, do the same but for the expression

d(s_1、v)+ d(w、t_1)+ d(s_2、v)+ d(w、t_2)+(2-C)d ^ *(v、w)

この最小値(すなわち、すべての$ v、w $に対する最小値)を維持する。それがあなたの問題の解決策になります。
(オーバーラップすると、ソリューションのコストがさらに下がるため、この計算では、$ s_1 leadsto v $と$ s_2
leadsto v $の間に重複がないことを強制する必要はありません)。

時間はすべてのペアの最短経路を計算する時間によって支配されるので、実行時間は$ O(n ^
3)$のようなものです。私はこれが最適であると主張しません。

$ C le 2 $のときにこれを解決する方法を示すNeal
Youngに感謝し、パスが単純かどうかについて私の前提を明確にするのを助けてくれました。

返信を残す

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