أقصر طريق في الحساب المعياري

Question

لنفترض أن لدينا 7 رؤوس، كل منها يتوافق مع وجود مودولو عددا صحيحا مختلفين.يوجد الحافة بين رأيتين X و Y إذا كانت X + 3 ≡ MoD 7. على سبيل المثال، هناك حافة بين 0 و 3، وحافة بين 5 و 2. ما هو طول أقصر المسار بين 0 و 1

طريقةي للحصول على الإجابة هي تطبيق تعريف التطابق.يخرج الحافة IFF 7 دولارات |X + 3 - Y $ .وبالتالي، حصلت على رسم بياني دوري واحد، ثم احصل على الإجابة هو 2. هل هناك طريقة يمكنني لعبها مع حسابي وحددي دون رسم رسم بياني حتى أتمكن من الحصول على أقصر مسار بين العقدة 0 و Node 1؟

Answer 1

اسمحوا لنا بالنظر في الحالة الأكثر عمومية التي لديك $ n $ certices، وتوصيل $ x، y $ إذا كان $ xy \ equiv a \ pmod {n} $ (في حالتك، $ n= 7 $ و $ a= 3 $ ).

الرسم البياني الخاص بك هو اتحاد دورات فكها. عندما $ n $ هي PRIME (كما في حالتك)، إنها دورة واحدة. وبالتالي، إذا كنت ترغب في الحصول على من $ x $ to $ y $ ، إما يمكنك الاستمرار في إضافة $ $ (modulo $ n $ )، يمكنك الاستمرار في طرح $ $ (modulo $ n $ ). إذا أضفت $ m $ أضعاف القيمة $ $ (حيث $ m $ أمر سلبي ربما) ثم $ x + ma \ equiF y \ pmod {n} $ ، أي $ ma \ equiv yx \ pmod {n} $ . دعونا الآن نفترض أن $ (a، n)= 1 $ (على سبيل المثال، $ n $ هو رئيس و $ 1 \ leq a \ leq n-1 $ ). ثم $ m \ equiang a ^ {- 1} (y-x) \ pmod {n} $ .

حل المعادلة أعلاه (على افتراض $ x \ not \ pmod \ pmod {n} $ )، سيكون هناك حل واحد $ 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} (yx)= 5 $ ، وهكذا $ m_ += 5 $ و $ - m_-= 2 $ . لذا فإن أقصر المسار يذهب إلى الوراء لخطوتين: $ 0 \ to 4 \ to 1 $ .

Answer 2

تحتاج إلى العثور على أعداد صحيحة $ $ و $ B $ مثل

3A $= 7B + 1 $

ومن كل القيم (بلا حدود وغير ذلك) القيم $ $ تريد المرء الذي يقلل $ | $ . في هذه الحالة، يمكننا أن نرى عن طريق المحاكمة والخطأ أن مجموعة الحلول هي $ A= 5 + 7N $ لقيم عدد صحيح من $ N $ ، وتقليل $ | $ | $ نحن نأخذ $ n= -1 $ ، بحيث $ A= -2 $ ، وأقصر المسار هو $ 0 \ to 4 \ to 1 $ .

بشكل عام، سيكون هناك العديد من الحلول بلا حدود ل $ PA= QB + 1 $ طالما $ P $ و $ Q $ هي المشارك (لا تشارك أي عوامل شائعة غير $ 1 $ )، ويمكنك استخدام خوارزمية Euclidean للعثور على أصغر قيمة إيجابية من $ $ . إذا كانت أصغر قيمة إيجابية من $ $ هي $ a_0 $ ثم قيمة $ $ تقلل $ | $ | $ هو $ a_0 $ أو $ a_0 - q $ .

Answer 3

يمكننا تعميم هذه المشكلة بسهولة: بالنظر إلى مجموعة محدودة G، فإن عناصرين G و H في G، ومجموعة فرعية S من G، ابحث عن أقصر مسار من G إلى H في الرسم البياني الذي هي عناصر G و من أن الحواف هي عناصر S أو Interses المعنيين لعناصر S، أي، مقترين X و Y مجاورة إذا كان Y= XR لبعض ص أي عنصر من عناصر S أو عكس عنصر معين من S. لاحظ أن هذا الرسم البياني لديه | G | رؤوس و | S || G | حواف في تنفيذ الكمبيوتر الصريح أو الضمني. سيتم الوصول إلى خوارزمية البحث البسيطة الأولى على هذا الرسم البياني على هذا الرسم البياني عند Vertex G والإنهاء بمجرد الوصول إلى Vertex H قد تحقق من أقصر المسار بين G و H في الوقت المناسب O (| G | + | S || G |)= O ( | S || G |) الوقت. علاوة على ذلك، نحن لسنا فعلا بناء هذا الرسم البياني؛ هذا لأننا نعرف بالفعل ما هي جميع الحواف. علينا فقط حلقة من خلال جيران عنصر المجموعة الحالي عند كل تكرار خوارزمية البحث الأولى في البحث.

في قضيتك، لأي عدد صحيح إيجابي N، لدينا S= {3 MOD N} وأن ترتيب المجموعة المضافة لفئات بقايا MOD N هي N، حتى نجد أقصر مسار بين أي بقايا محددة فصول وزارة الدفاع N في O (n)= O (n) الوقت.