Кратчайший путь в модульной арифметике

Question

Предположим, у нас есть 7 вершин, каждый из которых соответствует другому целомую модулю семь.Край существует между двумя вершинами x и y, если x + 3 ≡ y mod 7. Например, существует край между 0 и 3, а край между 5 и 2. Что такое длина кратчайшего пути между 0 и 1?

Мой метод, чтобы получить ответ - применить определение конгруэнции.Край выходит из IFF 7 долларов |x + 3 - y $ .Таким образом, я получил один циклический график, а затем получить ответ 2. Есть ли какой-либо метод, который я могу играть с модульной арифметикой, не рисуя графа, чтобы я мог получить кратчайший путь между узлом 0 и узлом 1?

Answer 1

Давайте рассмотрим более общее дело, в котором у вас есть $ n $ вершины, а вы подключаете $ x, y $ Если $ xy \ equiv a \ pmod {n} $ (в вашем случае, $ n= 7 $ и $ a= 3 $ ).

Ваш график - союз непересекающихся циклов. Когда $ n $ Prime (как в вашем случае) это один цикл. Следовательно, если вы хотите получить от $ x $ на $ y $ , либо вы продолжаете добавлять <класс SPAR= «Математический контейнер»> $ a $ (модуль $ n $ ), вы поддерживаете вычитание $ a $ (модуль $ n $ ). Если вы добавите $ m $ Times Times Times $ a $ (где $ x + ma \ equiv y \ pmod {n} $ , то есть $ ma \ equiv yx \ pmod {n} $ . Давайте теперь предположим, что $ (A, N)= 1 $ (например, $ n $ Prime и $ 1 \ leq a \ leq n-1 $ ). Затем $ m \ equiv a ^ {- 1} (y-x) \ pmod {n} $ .

Решение уравнения выше (при условии, что $ x \ not \ equiv y \ 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 \ до 4 \ до 1 $ .

Answer 2

Вам нужно найти целые числа $ a $ и $ B $ Такое, что

$ 3A= 7b + 1 $

и от всех (бесконечно много) значений $ a $ Вы хотите, чтобы тот, который минимизирует $ | A | $ . В этом случае мы можем увидеть по пробным и ошибкам, что набор решений является $ a= 5 + 7n $ для целочисленных значений $ n $ , а для минимизации $ | A | $ Мы принимаем $ n= -1 $ , так что $ a= -2 $ , а кратчайший путь - $ 0 \ до 4 \ до 1 $ .

В общем, будет бесконечно много решений для $ pa= qb + 1 $ до тех пор, пока $ P $ и $ q $ представляет собой CO-PRIME (не разделяйте никаких общих факторов, кроме $ 1 $ ), и вы можете использовать Евклидовой алгоритм , чтобы найти наименьшее положительное значение <класса Span="Математический контейнер"> $ a $ . Если наименьшее положительное значение $ a $ - $ a_0 $ Тогда значение $ a $ , который минимизирует $ | a | $ - это либо $ a_0 $ или $ a_0 - q $ .

Answer 3

Мы можем легко обобщить эту проблему: учитывая конечную группу g, два элемента g и h в G, а подмножество s g, найдите кратчайший путь от g до h в графе, вершины которых представляют собой элементы g и Кромки чьи элементы S или соответствующие инверсии элементов S, т. Е. Две вершины X и Y соседствуют, если и только тогда, когда y= xr для некоторого r, это либо элемент S, либо является обратным элементом из С. Обратите внимание, что этот график имеет | G | вершины и | S || G | ребра в явном или неявной компьютерной реализации. Простой алгоритм поиска по ширину на этом графике, начиная с вершины G и завершается после достижения вершины H, получает кратчайший путь между G и H во время O (| G | + | S || G |)= O ( | S || g |) время. Более того, мы на самом деле не должны построить этот график; Это потому, что мы уже знаем, что есть все края. Мы просто должны питаться через соседей нынешнего элемента группового элемента при каждой итерации алгоритма поиска первого широта.

В вашем случае, для любого положительного целого числа n, у нас есть S= {3 MOD N}, и что порядок добавки группы классов остатков MOD n представляет собой N, поэтому мы можем найти кратчайший путь между любыми двумя указанными остатками Классы мод n в O (n)= o (n) время.