Разностные ограничения алгоритма Беллмана-Форда

Предположим, мы хотим использовать метод Беллмана-Форда для минимизации max_i x_i - min_i x_i

над переменными x_1, x_2, ... x_n (всего n число переменных)

с учетом m ограничений вида x_i - x_j ‹= c_{i,j}

где c_{i,j} — заданная константа, которая может быть отрицательной.

Как я могу доказать, что метод Беллмана-Форда можно использовать для решения задач такого типа за время O(n*m)?

Я пробовал следующее:

создать узел i для каждой переменной x_i

сделать исходный узел s

создать ребро с нулевым весом от s до всех остальных узлов

не уверен, что делать после этого... пожалуйста, помогите, спасибо.


algorithm bellman-ford
person Anne    schedule 10.04.2013    source источник
comment
Это похоже на домашнее задание. Пожалуйста, опишите, что вы пробовали. Беллман-форд — это графовой алгоритм, поэтому, если вам приходится его использовать, как вы пытались превратить эту задачу в граф?   -  person Anil Vaitla    schedule 10.04.2013
comment
Что такое m в вашем требовании сложности?   -  person Anil Vaitla    schedule 10.04.2013
comment
m - количество ограничений x_i - x_j ‹= c_{i,j}   -  person Anne    schedule 10.04.2013

Ответы (2)


arrow_upward
2
arrow_downward

Вот мой подход, но я не думаю, что это O(m * n), но он может направить вас в правильном направлении. Хорошо бы попробовать нарисовать картинку, предположим, что у нас есть следующие ограничения:

Набор ограничений

Соответствующий граф ограничений выглядит следующим образом:

введите здесь описание изображения

Теперь обратите внимание, что в вашем случае у вас есть полный набор ограничений, поэтому граф ограничений будет полным графом. Теперь мы рассмотрим путь в графе из вашей задачи. Теперь рассмотрим путь, начинающийся в x_i и заканчивающийся в x_j. Это проходит через точки x_i1, x_i2..., x_ik. Итак, наш путь { x_i, x_i1, ..., x_ik, x_j }. Из-за того, как устанавливаются неравенства, этот путь дает нам новое ограничение (x_i - x_i1) + (x_i1 - x_i2) + ... + (x_ik - x_j) = x_i - x_j.

Здесь происходит то, что хотя у нас есть ограничение x_i - x_j ‹= c[i,j], мы можем найти более жесткие ограничения на x_i и x_j, взяв линейные комбинации других ограничений, которые представлены путями в этом полном графе.

Итак, зафиксируйте любую вершину x_i и найдите ее кратчайшее ограничение, то есть кратчайший путь к любой другой вершине по Беллману Форду. Затем сделайте это для всех i и возьмите минимум.

person Anil Vaitla    schedule 10.04.2013

arrow_upward
0
arrow_downward

В общем случае для этой задачи нельзя использовать алгоритм Беллмана-Форда. Один контрпример, упомянутый в ответе anil (на этой странице). на упомянутом графике в его ответе у нас есть отрицательный круг (sum of weights = -1): x1->x2->x3->x4->x5->x1, поэтому мы не можем использовать алгоритм Беллмана-Форда для этого типа графика и проблемы.

person moksef    schedule 07.03.2016