Jalur terpendek dalam aritmatika modular
Misalkan kita memiliki 7 simpul, yang masing-masing berhubungan dengan tujuh modulo integer yang berbeda. Sisi ada di antara dua simpul x dan y jika x + 3 ≡ y mod 7. Misalnya, ada sisi antara 0 dan 3, dan sisi antara 5 dan 2. Berapa panjang jalur terpendek antara 0 dan 1 ?
Metode saya untuk mendapatkan jawabannya adalah dengan menerapkan definisi kongruensi. Tepi keluar iff$7 | x + 3 - y$. Jadi, saya mendapat satu grafik siklik dan kemudian mendapatkan jawabannya adalah 2. Apakah ada metode yang bisa saya mainkan dengan aritmatika modular tanpa menggambar grafik sehingga saya bisa mendapatkan jalur terpendek antara node 0 dan node 1?
Jawaban
Mari kita pertimbangkan kasus yang lebih umum yang Anda miliki $n$ simpul, dan Anda terhubung $x,y$ jika $x-y \equiv a \pmod{n}$ (dalam kasus Anda, $n = 7$ dan $a = 3$).
Grafik Anda adalah gabungan siklus terputus-putus. Kapan$n$adalah bilangan prima (seperti dalam kasus Anda), ini adalah satu siklus. Karenanya jika Anda ingin mendapatkan dari$x$ untuk $y$, baik Anda terus menambahkan $a$ (modulo $n$), Anda terus mengurangkan $a$ (modulo $n$). Jika Anda menambahkan$m$ dikalikan nilainya $a$ (dimana $m$ mungkin negatif) kemudian $x+ma \equiv y \pmod{n}$, itu adalah, $ma \equiv y-x \pmod{n}$. Mari kita asumsikan sekarang$(a,n) = 1$ (sebagai contoh, $n$ adalah bilangan prima dan $1 \leq a \leq n-1$). Kemudian$m \equiv a^{-1}(y-x) \pmod{n}$.
Memecahkan persamaan di atas (dengan asumsi $x \not\equiv y \pmod{n}$), akan ada satu solusi $m_+$ dalam jangkauan $1,\ldots,n-1$ dan lainnya $m_-$ dalam jangkauan $-1,\ldots,-(n-1)$. Jaraknya$\min(m_+,-m_-)$.
Dalam kasus Anda, $n = 7$ dan $a = 3$. Kami bisa menghitung$a^{-1} = 5$. Jika$x = 0$ dan $y = 1$ kemudian $a^{-1}(y-x) = 5$, sehingga $m_+ = 5$ dan $-m_- = 2$. Jadi jalur terpendek mundur untuk dua langkah:$0 \to 4 \to 1$.
Anda perlu menemukan bilangan bulat $a$ dan $b$ seperti yang
$3a = 7b + 1$
dan dari semua nilai (yang sangat banyak) $a$ Anda menginginkan yang meminimalkan $|a|$. Dalam hal ini, kita dapat melihat dengan coba-coba bahwa kumpulan solusi adalah$a=5+7n$ untuk nilai integer $n$, dan untuk meminimalkan $|a|$ kami ambil $n=-1$, yang seperti itu $a=-2$, dan jalur terpendek adalah $0 \to 4 \to 1$.
Secara umum, akan ada banyak solusi untuk itu $pa = qb + 1$ selama $p$ dan $q$ adalah co-prime (jangan berbagi faktor umum selain $1$), dan Anda dapat menggunakan algoritme Euclidean untuk menemukan nilai positif terkecil$a$. Jika nilai positif terkecil dari$a$ adalah $a_0$ lalu nilai $a$ yang meminimalkan $|a|$ baik $a_0$ atau $a_0 - q$.
Kita dapat dengan mudah menggeneralisasi masalah ini: Diberikan grup berhingga G, dua elemen g dan h di G, dan subset S dari G, temukan jalur terpendek dari g ke h dalam grafik yang simpulnya adalah elemen G dan yang tepinya adalah elemen S atau invers masing-masing elemen S, yaitu, dua simpul x dan y berdekatan jika dan hanya jika y = xr untuk beberapa r yang merupakan elemen S atau merupakan kebalikan dari beberapa elemen S. Perhatikan bahwa grafik ini memiliki | G | simpul dan | S || G | tepi dalam implementasi komputer eksplisit atau implisit. Algoritme pencarian luas-pertama yang sederhana pada grafik ini dimulai dari puncak g dan berakhir setelah simpul h tercapai akan menghasilkan jalur terpendek antara g dan h dalam waktu O (| G | + | S || G |) = O ( | S || G |) waktu. Selain itu, kami sebenarnya tidak harus membuat grafik ini; ini karena kita sudah tahu apa semua edge itu. Kita hanya perlu melakukan perulangan melalui tetangga dari elemen grup saat ini pada setiap iterasi dari algoritme penelusuran luas-pertama.
Dalam kasus Anda, untuk bilangan bulat positif n, kita memiliki S = {3 mod n} dan urutan kelompok aditif kelas residu mod n adalah n, sehingga kita dapat menemukan jalur terpendek antara dua kelas residu yang ditentukan mod n dalam waktu O (n) = O (n).