Вопрос по algorithm – Почему большинство графовых алгоритмов не так легко адаптируются к отрицательным числам?

8

Руководство по разработке алгоритма говорит:

Most graph algorithms do not adapt so easily to negative numbers. Indeed, shortest path algorithms have trouble with negative numbers, and certainly do not generate the longest possible path using this technique.

Но почему? Когда мы просто добавляем отрицательный- Я думаю, что перед исходным весом большинство графических задач, связанных с весом, можно решать одинаково, верно?

Я думаю, что это скорее проблема семантики. Когда вес указывает, например, длину пути, тогда как длина может быть начальной? superM
В общем случае ребро не обязательно относится к физической длине; во многих случаях ребра могут иметь отрицательную длину (например, моделировать финансовые позиции, когда решение может привести к убыткам или прибыли), поэтому это реальная проблема. Steve Haigh

Ваш Ответ

3   ответа
7

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

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

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

Просто в качестве примера: если у вас есть два узла, соединенных между собой двумя ребрами веса1 а также-2 Вы можете создать цикл между ними, чтобы определить путь с произвольной низкой стоимостью (даже-∞).

Error: User Rate Limit Exceeded Jackson Tale
1

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

Рассмотрим графикG = (V, E) с краями длиныl(e) ≤ 0 для каждого краяe ∈ E, Кратчайший путь вG такой же, как самый длинный путь вG' сl'(e) = - l(e) ≥ 0 ∀e ∈ E. Самая длинная проблема пути Известно, что NP-жесткий в общих графах.Though it can be solved in linear time in DAGs and other classes of graphs.

КакCLS ответилпроблема только с отрицательными циклами иАлгоритм Беллмана-Форда может справиться с некоторыми краями, являющимися отрицательными. Но алгоритм самого длинного пути должен справляться с циклами в графе, и Беллман-Форд не может дать правильный ответ на графах с отрицательными циклами. Поэтому алгоритм Беллмана-Форда можно использовать для вычисления самого длинного пути только в графах без положительных циклов.Mentioning, because that idea is очевидно не редкость.

4

Indeed, shortest path algorithms have trouble with negative numbers,

Это верно дляАлгоритм Дейкстры, но не для алгоритмов кратчайшего пути в целом.Алгоритм Беллмана-Форда может иметь дело с отрицательными весами ребер, если график не содержит отрицательных циклов. Тем не мение:

Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is not reachable from the source.

Похожие вопросы