橋渡り問題の一般化①

合計の時間を \(T\) と置く. \(T\) の最小値として取り得る値を考える.

AからBに移動するのが 3回, BからAに移動するのが 2回なので,
\(k_1+k_2+k_3+k_4=5\) を満たす \(0\)以上の整数 \(k_1,\ k_2,\ k_3,\ k_4\) を用いて

\[T=k_1a+k_2b+k_3c+k_4d\]

と表せる.

\(d\) の人が移動するとき, 必ず \(d\) 分かかるので \(k_4\geq 1\).
さらに, \(d\) の人がBからAに移動出来るとき, \(d\) 以下の人がBに必ずいるので,
\(d\) の人がBからAに移動する必要がない.
よって \( k_4 = 1\) かつ \( k_1+k_2+k_3=4\) .

また, \(a\) の人がAからBに移動するとき, \(b\) 分以上かかるので \(k_1\leq 2\).
\(k_1=0\) の時, 2回のBからAへの移動でどちらも \(b\) 分以上かかっているが,
少なくとも一方は \(a\) の人の移動に変える事が出来て,
そちら方が効率が良い.(詳しくは下の枠線内を参照)
よって \(1\leq k_1\leq 2\).

・ \(k_1 = 1\) のとき

\(k_2+k_3=3\) であるが, \( k_2 = 3,\ k_3=0 \) のときが最小となる.
実際, このときの最短のパターンの１つは以下のように

\(a\) 分の人と \(b\) 分の人が渡る( \(b\) 分)
\(a\) 分の人が戻る( \(a\) 分)
\(c\) 分の人と \(d\) 分の人が渡る( \(d\) 分)
\(b\) 分の人が戻る( \(b\) 分)
\(a\) 分の人と \(b\) 分の人が渡る( \(b\) 分)
で \(T=a+3b+d\)

・ \(k_1 = 2\) のとき

\(k_2+k_3=2\) であり, \( k_2 = 2,\ k_3=0 \) のときが最小となるが,
こうなるように移動することは出来ない.
なぜなら, \( k_2 = 2,\ k_3=0 \) のとき,
BからAに移動するのが 2回とも \(a\) 分の人で,
AからBに移動するのが{\(a\), \(d\)}, {\(a\), \(b\)} , {\(a\), \(b\)} のペア
となるので \(c\) 分の人 がBに移動できないからである.

よって \( k_2 = 1,\ k_3=1 \) のときが最小となり,
実際, このときの最短のパターンの１つは以下のように

\(a\) 分の人と \(d\) 分の人が渡る( \(d\) 分)
\(a\) 分の人が戻る( \(a\) 分)
\(a\) 分の人と \(c\) 分の人が渡る( \(c\) 分)
\(a\) 分の人が戻る( \(a\) 分)
\(a\) 分の人と \(b\) 分の人が渡る( \(b\) 分)
で合計 \(T=2a+b+c+d\)

ここまでは, 最短の移動パターンの取り得る値を探ってきた.
それらの関係を調べる. \( a+3b+d \geq 2a+b+c+d \)
を解くと, \(2b\geq a+c\). ゆえに

\[T=\left\{ \, \begin{aligned} & a+3b+d &( 2b\leq a+c )\\ & 2a+b+c+d &( 2b\geq a+c ) \end{aligned} \right.\]