Является ли алгоритм Дейкстры детерминированностью c?

Question

Я думаю, что алгоритм Дейкстры определен, так что если вы выберете одну и ту же начальную вершину, вы получите тот же результат (одинаковые расстояния до любой другой вершины). Но я не думаю, что это определено c (что оно определило следующую операцию для каждой операции), потому что это означало бы, что ему не пришлось бы искать самые короткие расстояния.

Я прав? Если я ошибаюсь, не могли бы вы объяснить, почему это определенно c, и, может быть, привести пример?

Answer 1

Я не уверен, что существует универсальное определение детерминизма, но Википедия определяет его как ...

... алгоритм, который, учитывая конкретный вход , всегда будет выдавать один и тот же вывод, при этом базовый компьютер всегда проходит через одну и ту же последовательность состояний.

Так что для этого требуется как детерминизм вывода , так и детерминизм исполнения . Вывод алгоритма Дейкстры детерминирован c независимо от того, как вы на него смотрите, потому что это длина кратчайшего пути, и есть только одна такая длина.

Выполнение алгоритма Дейкстры в абстрактном смысле не детерминированный c, потому что последний шаг :

В противном случае выберите не посещенный узел, помеченный наименьшим предварительным расстоянием, установите его в качестве нового «текущего узла» и go вернитесь к шагу 3.

Если Есть несколько узлов с одинаковым наименьшим предварительным расстоянием, алгоритм может выбрать один произвольно. Это не влияет на вывод, но влияет на порядок операций в алгоритме.

Определенная реализация алгоритма Дейкстры, однако, , вероятно, детерминирован c, потому что узлы будут храниться в детерминированной c структуре данных, такой как минимальная куча. Это приведет к тому, что каждый раз при запуске программы будет выбираться один и тот же узел. Хотя такие вещи, как хешируемые соли, могут также влиять на детерминизм даже здесь.

Answer 2

Позвольте мне остановиться на Ответ Томаса .

Если вы посмотрите на реализацию Dijkstra, такую ​​как этот пример: http://graphonline.ru/en/?graph=NnnNwZKjpjeyFnwx, вы увидите график, подобный этому

В примере графика 0 → 1 → 5, 0 → 2 → 5, 0 → 3 → 5 и 0 → 4 → 5 одинаковой длины. Чтобы найти «кратчайший путь» не обязательно уникален, о чем свидетельствует эта диаграмма.

Используя формулировку в Википедии , в какой-то момент алгоритм инструктирует нас:

выберите не посещаемый узел, который помечен с наименьшим предварительным расстоянием .

Проблема здесь заключается в слове , что предполагает его уникальность. А может и не быть. Для реализации, чтобы фактически выбрать один узел из множества равных кандидатов, требуется дополнительная спецификация алгоритма относительно того, как его выбрать. Но любой такой выбранный кандидат, имеющий требуемое свойство, будет определять путь наименьшей длины. Таким образом, алгоритм не фиксирует. Современный подход к формулировке этого алгоритма заключается в следующем:

выберите любой не посещенный узел, который отмечен наименьшим предварительным расстоянием .

С точки зрения алгоритма математической теории графов этот алгоритм технически будет обрабатывать всех таких кандидатов одновременно в виде мультиверса. Все ответы, которые он может получить, одинаково действительны. И когда доказательство того, что алгоритм работает, мы докажем его для всех таких кандидатов во всех мультиверсах и покажем, что все варианты выбора находятся на пути одинакового расстояния, и что это расстояние является наименьшим возможным расстоянием.

Тогда, если вы хотите использовать алгоритм, чтобы просто вычислить один такой ответ, потому что вы хотите либо A) найти один такой путь, либо B) определить расстояние такого пути, то он остается на ваше усмотрение выбрать одну указанную c ветвь мультивселенной для исследования. Все такие выборки, сделанные в соответствии с определенным алгоритмом, дадут путь, длина которого является наименьшей возможной длиной. Вы можете определить любые дополнительные неконфликтующие критерии, которые вы сделаете sh, чтобы сделать такой выбор.

Причина, по которой я связал реализацию, является детерминированной c и всегда дает один и тот же ответ (очевидно, для одинаковых начального и конечного узлов), потому что сами узлы упорядочены в компьютере. Эта дополнительная информация о порядке узлов не рассматривается для теории графов. Узлы часто помечены, но не обязательно упорядочены. В реализации компьютер полагается на тот факт, что узлы появляются в упорядоченном массиве узлов в памяти, и реализация использует этот порядок для разрешения связей. Возможно, выбрав узел с самым низким индексом в массиве, то есть «первым» кандидатом.

Если реализация разрешает связи путем случайного (не псевдослучайного!) Выбора победителя из равных кандидатов, то это * не быть детерминированным c.

Алгоритм Дейкстры, описанный в Википедии, просто определяет алгоритм для поиска кратчайших путей (обратите внимание на множественное число путей ) между узлами. Любой такой путь, который он находит (если он существует), гарантированно будет иметь кратчайшее возможное расстояние. Вам по-прежнему остается задача выбора между эквивалентными кандидатами на шаге 6 в алгоритме.

Answer 3

По определению c Я так понимаю, вы имеете в виду, что он будет давать один и тот же ответ на один и тот же запрос каждый раз для одних и тех же данных и давать только один ответ, тогда это определено c. Если бы оно не было детерминированным, подумайте о проблемах, которые это может вызвать у тех, кто его использует. Я пишу на Прологе весь день, поэтому я знаю недетерминированные ответы c, когда вижу их.

---

Здесь я только что ввел простую ошибку в Прологе, и ответ не был детерминирован c, а с простым исправлением это детерминирован c.

Недетерминирован c

spacing_rec(0,[]).
spacing_rec(Length0,['  '|T]) :-
    succ(Length,Length0),
    spacing_rec(Length,T).

?- spacing(0,Atom).
Atom = '' ;
false.

Детерминированность c

spacing_rec(0,[]) :- !.
spacing_rec(Length0,['  '|T]) :-
    succ(Length,Length0),
    spacing_rec(Length,T).

?- spacing(0,Atom).
Atom = ''.

Answer 4

Как говорит тэг, обычный термин - "детерминированный c". И алгоритм действительно определен c. Для любого заданного ввода выполняемые шаги всегда идентичны.

Сравните его с более простым алгоритмом, таким как добавление двух чисел multi-di git. Результат всегда одинаков для двух заданных входов, шаги также одинаковы, но вам все равно нужно добавить числа, чтобы получить результат.

Answer 5

Я постараюсь сохранить это кратким и простым, здесь и в Интернете можно найти много хороших объяснений, если, конечно, будет сделано хорошее исследование.

Алгоритм Дейкстры - жадный алгоритм , основная цель алгоритма Дийсктра - найти кратчайший путь между двумя узлами взвешенного графа.

Википедия отлично справляется с объяснением того, что детерминированные c и недетерминированные c алгоритмы и как вы можете «определить», какой алгоритм подпадает под одну из следующих категорий:

Из Википедии Источник:

Детерминированный c Алгоритм:

В компьютерной науке алгоритм детерминированности c - это алгоритм, который, учитывая конкретный ввод всегда будет производить один и тот же вывод, а базовый компьютер всегда проходит через одну и ту же последовательность состояний. Детерминированные c алгоритмы - безусловно, наиболее изученный и знакомый алгоритм, а также один из наиболее практичных, поскольку они могут эффективно выполняться на реальных машинах.

Формально, детерминированный c алгоритм вычисляет математическую функцию; функция имеет уникальное значение для любого входа в своей области, и алгоритм представляет собой процесс, который выдает это конкретное значение в качестве вывода.

Недетерминированный c Алгоритм

В компьютерной науке недетерминированный алгоритм c - это алгоритм, который, даже для одного и того же ввода, может демонстрировать различное поведение на разных прогонах, в отличие от детерминированного алгоритма c. Есть несколько способов, которыми алгоритм может вести себя по-разному от запуска к запуску. Параллельный алгоритм может работать по-разному на разных трассах из-за состояния гонки.

Итак, вернуться к цели алгоритма Дейкстры - все равно что сказать, что я хочу перейти от местоположения X к местоположению Z , но для этого у меня есть варианты, проходящие через более короткий путь. узлы, которые дойдут до моего конца намного быстрее и эффективнее , чем другие более длинные маршруты или узлы ...

Продумывая случаи, когда алгоритм Дийсктра может быть детерминирован c будет хорошая идея.