モジュラー演算の最短経路
7つの頂点があり、それぞれが7を法とする異なる整数に対応するとします。x +3≡ymod7の場合、エッジは2つの頂点xとyの間に存在します。たとえば、0と3の間にエッジがあり、5と2の間にエッジがあります。0と1の間の最短経路の長さはどれくらいですか。 ?
答えを得るための私の方法は、合同の定義を適用することです。エッジは、$7 | x + 3 - y$。したがって、1つの閉路グラフを取得し、答えは2になります。ノード0とノード1の間の最短経路を取得できるように、グラフを描画せずにモジュラー演算で遊ぶことができる方法はありますか?
回答
あなたが持っているより一般的なケースを考えてみましょう $n$ 頂点、そしてあなたは接続します $x,y$ もし $x-y \equiv a \pmod{n}$ (あなたの場合、 $n = 7$ そして $a = 3$)。
あなたのグラフは互いに素なサイクルの和集合です。いつ$n$(あなたの場合のように)素数である、それは単一のサイクルです。したがって、あなたがから取得したい場合$x$ に $y$、どちらかを追加し続ける $a$ (モジュロ $n$)、あなたの $a$ (モジュロ $n$)。追加した場合$m$ 値の倍 $a$ (どこ $m$ おそらく負です)そして $x+ma \equiv y \pmod{n}$、 あれは、 $ma \equiv y-x \pmod{n}$。ここで、$(a,n) = 1$ (例えば、 $n$ 素数であり、 $1 \leq a \leq n-1$)。次に$m \equiv a^{-1}(y-x) \pmod{n}$。
上記の方程式を解く(仮定 $x \not\equiv y \pmod{n}$)、1つの解決策があります $m_+$ 範囲内 $1,\ldots,n-1$ と別の $m_-$ 範囲内 $-1,\ldots,-(n-1)$。距離は$\min(m_+,-m_-)$。
あなたの場合、 $n = 7$ そして $a = 3$。計算できます$a^{-1} = 5$。場合$x = 0$ そして $y = 1$ その後 $a^{-1}(y-x) = 5$、 など $m_+ = 5$ そして $-m_- = 2$。したがって、最短パスは2つのステップで逆方向に進みます。$0 \to 4 \to 1$。
あなたは整数を見つける必要があります $a$ そして $b$ そのような
$3a = 7b + 1$
そして、のすべての(無限に多くの)値から $a$ あなたは最小化するものが欲しい $|a|$。この場合、試行錯誤により、一連のソリューションが次のようになっていることがわかります。$a=5+7n$ の整数値の場合 $n$、および最小化する $|a|$ 私たちは取る $n=-1$、 そのため $a=-2$、および最短経路は $0 \to 4 \to 1$。
一般的に、解決策は無限にあります $pa = qb + 1$ 限り $p$ そして $q$ 互いに素です(以外の共通の要因を共有しないでください $1$)、そしてユークリッドアルゴリズムを使用して、の最小の正の値を見つけることができます$a$。の最小の正の値の場合$a$ です $a_0$ 次にの値 $a$ 最小化する $|a|$ どちらかです $a_0$ または $a_0 - q$。
この問題は簡単に一般化できます。有限群G、Gの2つの要素gとh、およびGのサブセットSが与えられた場合、頂点がGの要素であり、エッジがGの要素であるグラフでgからhへの最短経路を見つけます。 Sの要素またはSの要素のそれぞれの逆関数、つまり2つの頂点xとyは、Sの要素またはSの要素の逆であるrに対してy = xrである場合に限り、隣接します。このグラフには| G |があることに注意してください 頂点と| S || G | 明示的または暗黙的なコンピューター実装のエッジ。このグラフの単純な幅優先探索アルゴリズムは、頂点gで始まり、頂点hに到達すると終了し、時間O(| G | + | S || G |)= O(でgとhの間の最短経路を生成します。 | S || G |)時間。さらに、実際にこのグラフを作成する必要はありません。これは、すべてのエッジが何であるかをすでに知っているためです。幅優先探索アルゴリズムを繰り返すたびに、現在のグループ要素の近傍をループする必要があります。
あなたの場合、任意の正の整数nに対して、S = {3 mod n}があり、残差クラスmod nの加法群の次数はnであるため、指定された2つの残差クラスmodn間の最短経路を見つけることができます。 O(n)= O(n)時間で。