2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Транспортная задача и NP
Сообщение18.11.2013, 22:43 


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение19.11.2013, 00:14 
Заслуженный участник


14/03/10
867
max(Im) в сообщении #790177 писал(а):
Ведь алгоритм mincost maxflow полиномиальный, почему же она из NP?

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

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение19.11.2013, 00:24 
Аватара пользователя


03/10/13
449
patzer2097 в сообщении #790209 писал(а):
Ведь транспортная задача является частным случаем задачи линейного программирования

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение19.11.2013, 00:29 
Заслуженный участник


14/03/10
867
Urnwestek в сообщении #790210 писал(а):
patzer2097 в сообщении #790209 писал(а):
Ведь транспортная задача является частным случаем задачи линейного программирования

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

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение19.11.2013, 00:30 
Аватара пользователя


03/10/13
449
patzer2097 в сообщении #790212 писал(а):
Я писал к тому, что вряд ли транспортная задача NP-сложна, -- т.к. иначе линейное программирование было бы NP-сложным :-) Не понял, причем здесь поиск минимального пути.

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение19.11.2013, 00:33 
Заслуженный участник


14/03/10
867
Urnwestek в сообщении #790213 писал(а):
Я подумал, что вы из того, что ЛП NP-трудное сделали вывод, что и транспортная задача NP-трудная. (: Недопонимание, вопрос закрыт.

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение19.11.2013, 08:31 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение25.11.2013, 05:24 


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение25.11.2013, 08:11 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
vjung в сообщении #792380 писал(а):
Транспортную задачу и правда можно решить через линейное программирование за полиномиальное время. Загвоздка в том, что формирование этой ЛП задачи из исходной транспортной NP сложно.


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение25.11.2013, 20:56 


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


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение25.11.2013, 21:17 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение26.11.2013, 09:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение26.11.2013, 10:20 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Евгений Машеров в сообщении #792784 писал(а):
Контр-пример для симплекс метода, в котором обходят экспоненциально зависящее от размерности задачи число вершин, весьма далёк от условий транспортной задачи.

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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение27.11.2013, 12:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Транспортная задача и NP
Сообщение13.09.2018, 22:09 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group