Обсуждение:Транспортная задача
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Стиль изложения
правитьУважаемые авторы сего творения! Вы сами пробовали это читать? Это тихий ужас! Зачем было приводить теорию двудольных графов, рассказывая о поиске циклов? Думаю, было бы гораздо понятнее, если бы алгоритм был расписан простыми словами и на конкретном примере. Gigabyte-artur 14:51, 12 июня 2009 (UTC)
- А так всегда в Википедии, заходят умники и переписывают все так чтобы понять могли только они. Я написал когда-то пошаговый алгоритм Кода Хемминга, прошло несколько месяцев и статья усложнилась настолько, что мои студенты там ничего не понимают. Ink 06:59, 15 октября 2011 (UTC)
Определение
правитьЗадача является абстрактной и может быть применима к любой области, не только транспортной. Задача рассматривается на примере транспортировки для наглядности (упрощения понимания). А в вступлении (определении) безапелляционно заявлено, что
задача об оптимальном плане перевозок продукта(-ов)
объясните мне причем тут продукты? Где источники (АИ)?! Ink 06:59, 15 октября 2011 (UTC)
- Поправил на основании источников. Ink 07:59, 15 октября 2011 (UTC)
NP?
правитьИли я что-то не понимаю, или классическая транспортная задача, та самая, которая решается методом потенциалов, решается ещё и поиском потока наименьшей стоимости, а это уж никак не NP. 90.157.27.118 05:46, 23 июня 2013 (UTC)Агеев Паша
Касательно NP-сложности.
правитьТранспортная задача полиномиальна. Потоковый алгоритм, венгерский метод, метод потенциалов (с проверкой на зацикливание) - решают за полиномиальное время. Хотелось бы знать, откуда взята фраза о принадлежности её к классу NP, уже многократно растиражированная в рефератах. В английской и немецкой версии статьи такого рода сведения отсутствуют.
Евгений Машеров 07:00, 26 ноября 2013 (UTC)Евгений Машеров
А что не так с принадлежностью классу NP? То, что задача допускает полиномиальный алгоритм, никак не противоречит тому, что она принадлежит классу NP. Ведь NP -- это класс задач распознавания, допускающих полиномиальное по времени решение на недетерминированной машине Тьюринга, и потому полиномиальные задачи распознавания тем более принадлежат NP. По поводу самой статьи, там просто опечатка - по-моему достаточно исправить "Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP." на, например, "Транспортная задача входит в класс сложности P, то есть, допускает полиномиальный по времени алгоритм решения." Ведь сами эти алгоритмы и оценки их сложности приведены ниже в тексте статьи.213.87.133.67 20:56, 27 ноября 2013 (UTC) patzer2097
Тем, что имеющаяся формулировка создаёт преувеличенное представление о трудности задачи. Да, полагаю, хороший адвокат легко докажет, что "NP-сложная" это то же, что "входящая в класс сложности NP", а так как класс P его подмножество, то утверждение верное ("черный это цвет? белый это цвет? значит, ты купил у меня цветной телевизор!"), а те, кто искал в нём ��нформативность и интерпретировал, как "NP-полное" или "NP-трудное", сами виноваты. Но мне бы хотелось, чтобы там была полезная информация. Скажем, о том, что есть достаточно быстрые алгоритмы её решения. Полиномиальной сложности.
Евгений Машеров 11:56, 29 ноября 2013 (UTC) Евгений Машеров
Не очень Вас понял. "NP-сложная" и "NP-трудная" -- это синонимы, а "входящая в класс сложности NP" -- это совсем другое. А "NP-полная" -- это отличается и от одного, и от другого. А о том, что существуют полиномиальные алгоритмы, конечно, надо в первом абзаце надо написать (я это тоже предложил выше). 213.87.137.247 13:57, 30 ноября 2013 (UTC) patzer2097
Маршруты между потребителями, неоднородность продукта, грузоподъемность, вместительность, удельная стоимость перевозки
правитьИли я не достаточно изучил задачу, или она не учитывает все перечисленные параметры. Подскажите пожалуйста есть вариант ее толкования и самое главное, алгоритм решения их учитывающий? Как найти его? Необходим для оптимизации складской логистики.— Александр Шагров (обс.) 03:42, 3 февраля 2021 (UTC)