Транспортная задача и NP

[max(Im)]

Доброго дня!
В википедии сказано, что транспортная задача принадлежит классу NP, однако далее приведен алгоритм ее решения через потоки. Ведь алгоритм mincost maxflow полиномиальный, почему же она из NP?

[patzer2097]

max(Im) в сообщении #790177 писал(а):

Ведь алгоритм mincost maxflow полиномиальный, почему же она из NP?

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

Если Вы имеете в виду "почему в википедии написано, что транспортная задача NP-сложна?", то, как мне кажется, там опечатка. Ведь транспортная задача является частным случаем задачи линейного программирования, для которой NP-сложность не известна (более того, для нее известен псевдополиномиальный алгоритм решения).

[Urnwestek]

patzer2097 в сообщении #790209 писал(а):

Ведь транспортная задача является частным случаем задачи линейного программирования

И что из этого следует? Поиск минимального по весу пути в графе — тоже частный случай задачи линейного программирования.

[patzer2097]

Urnwestek в сообщении #790210 писал(а):

patzer2097 в сообщении #790209 писал(а):

Ведь транспортная задача является частным случаем задачи линейного программирования

И что из этого следует? Поиск минимального по весу пути в графе — тоже частный случай задачи линейного программирования.

Я писал к тому, что вряд ли транспортная задача NP-сложна, -- т.к. иначе линейное программирование было бы NP-сложным Не понял, причем здесь поиск минимального пути.

[Urnwestek]

patzer2097 в сообщении #790212 писал(а):

Я писал к тому, что вряд ли транспортная задача NP-сложна, -- т.к. иначе линейное программирование было бы NP-сложным Не понял, причем здесь поиск минимального пути.

Я подумал, что вы из того, что ЛП NP-трудное сделали вывод, что и транспортная задача NP-трудная. (: Недопонимание, вопрос закрыт.

[patzer2097]

Urnwestek в сообщении #790213 писал(а):

Я подумал, что вы из того, что ЛП NP-трудное сделали вывод, что и транспортная задача NP-трудная. (: Недопонимание, вопрос закрыт.

Ага, все совершенно наоборот -- скорее всего, ЛП не является NP-трудным

[Евгений Машеров]

Полагаю, это ошибка. Увы, Википедия источник неавторитетный, хотя и полезный для общего обзора и быстрого поиска. Кроме того, это сведения имеются в русской версии Вики, но не в английской. Вероятно, это недопонимание конкретного редактора. Возможно, он имел в виду какие-то обобщения ТЗ или просто спутал ТЗ и задачу коммивояжёра.

[vjung]

Транспортную задачу и правда можно решить через линейное программирование за полиномиальное время. Загвоздка в том, что формирование этой ЛП задачи из исходной транспортной NP сложно.

[Евгений Машеров]

vjung в сообщении #792380 писал(а):

Транспортную задачу и правда можно решить через линейное программирование за полиномиальное время. Загвоздка в том, что формирование этой ЛП задачи из исходной транспортной NP сложно.

Выписываем n ограничений по поставщикам, m ограничений по потребителям, целевую функцию с mn коэффициентами. Что здесь неполиномиально?!

[vjung]

Цитата:

Выписываем n ограничений по поставщикам, m ограничений по потребителям, целевую функцию с mn коэффициентами. Что здесь неполиномиально?!

согласен. я имел в виду tsp.

[nikvic]

Для задач линейного программирования есть полиномиальный алгоритм получения приближённого решения, если я не ошибаюсь (Погосян?).
Симплекс метод требует, вообще говоря, экспоненты (Ерешко).

Что ещё известно про возможность точного решения?

[Евгений Машеров]

Контр-пример для симплекс метода, в котором обходят экспоненциально зависящее от размерности задачи число вершин, весьма далёк от условий транспортной задачи.
Транспортная задача решаема за полиномиальное время. В русской Вики (и во множестве списанных оттуда рефератов) приведены ложные сведения.

[nikvic]

Евгений Машеров в сообщении #792784 писал(а):

Контр-пример для симплекс метода, в котором обходят экспоненциально зависящее от размерности задачи число вершин, весьма далёк от условий транспортной задачи.

Факт. Мой вопрос - про точное решение ЗЛП.

[Евгений Машеров]

Оставил сообщение в странице обсуждения статьи "Транспортная задача". Ждём-с...

[Gregory G]

Добрый день.
Уважаемые господа, правильно ли я понимаю, что решение транспортной задачи методом потенциалов (модифицированный распределительный метод) должно быть быстрее, чем симплекс-методом? К тому же метод потенциалов обещает решение за конечное число шагов...
Что предпочтительнее на больших размерностях - метод дифференциальных рент или потенциалов?
Имеется ли литература, на которую можно ссылаться, для оценки времени решения ТЗ?
Буду благодарен за любые подсказки.