Modüler aritmetikte en kısa yol

Question

Her biri farklı bir modulo yediye karşılık gelen 7 köşemiz olduğunu varsayalım. Kenar, x + 3 ≡ y mod 7 ise, iki köşe x ve y arasında bulunur. Örneğin, 0 ile 3 arasında bir kenar ve 5 ile 2 arasında bir kenar vardır. 0 ile 1 arasındaki en kısa yolun uzunluğu nedir ?

Cevabı alma yöntemim uygunluk tanımını uygulamaktır. Kenar iff çıkar$7 | x + 3 - y$. Böylece, bir döngüsel grafik aldım ve sonra cevabı 2 aldım. Düğüm 0 ile düğüm 1 arasında en kısa yolu elde edebilmek için modüler aritmetik ile grafik çizmeden oynayabileceğim herhangi bir yöntem var mı?

Answer 1

Sahip olduğunuz daha genel durumu ele alalım. $n$ köşeler ve bağlanırsınız $x,y$ Eğer $x-y \equiv a \pmod{n}$ (Senin durumunda, $n = 7$ ve $a = 3$).

Grafiğiniz, ayrık döngülerin bir birleşimidir. Ne zaman$n$asal (sizin durumunuzda olduğu gibi), bu tek bir döngüdür. Bu yüzden almak istiyorsan$x$ -e $y$Ya eklemeye devam edersin $a$ (modulo $n$), çıkarmaya devam ediyorsun $a$ (modulo $n$). Eklersen$m$ değerin katı $a$ (nerede $m$ muhtemelen olumsuzdur) o zaman $x+ma \equiv y \pmod{n}$, yani, $ma \equiv y-x \pmod{n}$. Şimdi varsayalım ki$(a,n) = 1$ (Örneğin, $n$ asal ve $1 \leq a \leq n-1$). Sonra$m \equiv a^{-1}(y-x) \pmod{n}$.

Yukarıdaki denklemi çözme (varsayım $x \not\equiv y \pmod{n}$), tek bir çözüm olacak $m_+$ aralıkta $1,\ldots,n-1$ ve başka $m_-$ aralıkta $-1,\ldots,-(n-1)$. Mesafe$\min(m_+,-m_-)$.

Senin durumunda, $n = 7$ ve $a = 3$. Hesaplayabiliriz$a^{-1} = 5$. Eğer$x = 0$ ve $y = 1$ sonra $a^{-1}(y-x) = 5$, ve bu yüzden $m_+ = 5$ ve $-m_- = 2$. Yani en kısa yol iki adımda geriye gider:$0 \to 4 \to 1$.

Answer 2

Tamsayı bulmalısın $a$ ve $b$ öyle ki

$3a = 7b + 1$

ve tüm (sonsuz sayıda) değerlerinden $a$ küçülteni istiyorsun $|a|$. Bu durumda, deneme yanılma yoluyla çözüm setinin olduğunu görebiliriz.$a=5+7n$ tamsayı değerleri için $n$ve en aza indirmek için $|a|$ alırız $n=-1$, Böylece $a=-2$ve en kısa yol $0 \to 4 \to 1$.

Genel olarak, sonsuz sayıda çözüm olacaktır. $pa = qb + 1$ olduğu sürece $p$ ve $q$ eş asaldırlar (dışında herhangi bir ortak faktörü paylaşmayın) $1$) ve en küçük pozitif değeri bulmak için Öklid algoritmasını kullanabilirsiniz .$a$. En küçük pozitif değeri$a$ dır-dir $a_0$ sonra değeri $a$ en aza indiren $|a|$ ya $a_0$ veya $a_0 - q$.

Answer 3

Bu problemi kolaylıkla genelleyebiliriz: Sonlu bir G grubu, G'deki iki eleman g ve h ve G'nin bir alt kümesi verildiğinde, köşeleri G'nin elemanları ve kenarları olan grafikte g'den h'ye en kısa yolu bulun. S'nin elemanları veya S'nin elemanlarının karşılık gelen tersleri, yani iki köşe x ve y, ancak ve ancak bazı r için y = xr, yani S'nin bir elemanı veya S'nin bazı elemanlarının tersi ise bitişiktir. Bu grafiğin | G | köşeler ve | S || G | açık veya örtük bir bilgisayar uygulamasında kenarlar. Bu grafikte g tepe noktasından başlayıp h tepe noktasına ulaşıldığında sona eren basit bir enine arama algoritması, O (| G | + | S || G |) = O ( | S || G |) zaman. Dahası, aslında bu grafiği oluşturmamız gerekmiyor; çünkü tüm kenarların ne olduğunu zaten biliyoruz. Sadece en geniş arama algoritmasının her yinelemesinde mevcut grup elemanının komşuları arasında dolaşmalıyız.

Sizin durumunuzda, herhangi bir pozitif tamsayı n için, S = {3 mod n} var ve kalıntı sınıflarının ilave grubunun sırası mod n n'dir, böylece belirtilen herhangi iki kalıntı sınıfı arasındaki en kısa yolu bulabiliriz mod n O (n) = O (n) zamanında.