Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.138.200.66] |
|
Сообщ.
#1
,
|
|
|
Всем привет
Классическая модельная задача, которую обычно решают ДП: Между конечным числом получателей распределяется целое положительное количество какого-то ресурса. Прибыль от вложений ресурса задана табличкой. Требуется эту прибыль максимизировать. К какому классу относится эта задача? |
Сообщ.
#2
,
|
|
|
Первый-на Самое оптимальное решение - дает полный перебор...
Но тут нет никакого инструмента выявления экстремумов. Иными словами - "или все, или ничего". |
Сообщ.
#3
,
|
|
|
Ну вот про рюкзак или про набор суммы заданными слагаемыми(задача тысячелетия!) скоро на заборе будет написано, что они NP-полные, но решаются за псевдополиномиальное время.
А про эту ничего не нашла. |
Сообщ.
#4
,
|
|
|
Цитата swf @ К какому классу относится эта задача? Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе). Решается за полиномиальное время. |
Сообщ.
#5
,
|
|
|
Не вижу НИКАКОГО различия между этой задачей и рюкзаком.
Цитата swf @ Между конечным числом Требуется |
Сообщ.
#6
,
|
|
|
Цитата amk @ Цитата swf @ К какому классу относится эта задача? Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе). Решается за полиномиальное время. В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять. Добавлено Цитата Akina @ Не вижу НИКАКОГО различия между этой задачей и рюкзаком. Цитата swf @ Между конечным числом Требуется Да! конечно. Много рюкзаков. Спасибо, Акина! И решается с помощью ДП рюкзак двойным циклом, а распределение ресурсов - тройным. Скрытый текст Это я щас пишу главку для уч. пособия "Решение NP-полных задач точными методами", нельзя ДП обойти. Задачи решаю по всем правилам науки, прямой и обратной прогонкой |
Сообщ.
#7
,
|
|
|
Нет, это не рюкзак и не много рюкзаков, думаем дальше
Добавлено частный случай задачи распределения из теории расписаний |
Сообщ.
#8
,
|
|
|
Цитата swf @ Кроме поиска максимума линейной функции при линейных ограничениях, задачи, решаемой собственно линейным программированием, есть ещё и несколько дискретных задач вроде транспортной задачи.В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять. По мне, так описание соответствует именно транспортной задаче. |
Сообщ.
#9
,
|
|
|
amk,
в транспортной задаче сколько единиц потока вышло из источника, ровно столько пришло в сток. Есть, правда, потоки с усилением, когда поток, проходя через вершину умножается на коэффициент, что опять линейная функция. А тут от от одной единицы прибыль 10, от двух - 15, от трёх - 16, а от четырёх теоретически может быть меньше 16, никто ведь не обещал, что функция монотонно возрастает. Видимо, надо идти от программы, от того тройного цикла, который я написала. Если каждое число a на входе (величина ресурса, величина прибыли) закодировать как логарифм (log a), то длина входа будет равна (n+M)*log (max a), где n - число заводов, M - количество вариантов объёма ресурса, max a - максимальное входное число. Соответственно, у полиномиального алгоритма выч.сложность ограничена полиномом от длины входа, у псевдополиномиального - неограничена. Ну вот решаем набор суммы ДП, набираем сумму B n слагаемыми, табличка n*B, выч. сложность псевдополиномиальная O(n*B), что не ограничено никаким полиномом от nlog B. А тут что-то не соображу, от чего у меня табличка (количество состояний) зависит: от количества вариантов ресурса или от (максимальной) величины выделяемого ресурса. |
Сообщ.
#10
,
|
|
|
Цитата swf @ Всем привет Классическая модельная задача, которую обычно решают ДП: Между конечным числом получателей распределяется целое положительное количество какого-то ресурса. Прибыль от вложений ресурса задана табличкой. Требуется эту прибыль максимизировать. К какому классу относится эта задача? Спасибо. Пошел по ссылке нашел классный курс ДП на ютуб. Уже посмотрел 34 лекции |
Сообщ.
#11
,
|
|
|
Рассмотрела свои реализации прямой и обратной схемы.
Если решать обратной схемой, то Z[i,j] - прибыль от первых i предприятий, j - остаток средств. Состояние системы описывается имеющимися средствами. Начинаем от всей суммы, заканчиваем 0. Если решать прямой схемой, то Z[i,j] - прибыль от первых i предприятий, j - потраченные средства. Состояние системы описывается потраченными средствами. Начинаем от 0 (ничего не потратили), заканчиваем полной суммой - всё потратили. Пусть i = 1..n, где n -количество предприятий и число строк в табличке; j= 0..M, где M - число различных вариантов выделения средств. Если количество выделяемых средств кратно номеру варианта (например, M = 3: {0, 40, 80, 120}), то столбцы в табличке нумеруем 0..M. Уравнение состояния для обратной схемы: Si = Si-1-Xi, где Xi - управление, Xi*40 - средства, выделенные заводу; для прямой схемы Si = Si-1+Xi. Как только выделенные средства перестают быть линейной функцией номера варианта - всё, в табличке, как для рюкзака или как для набора суммы заданными слагаемыми, нужно столбцы вести не по номерам вариантов а по распределяемой сумме денег. Как верно заметил Акина, получаем рюкзак. Но полиномиальную сводимость рюкзака (или набора суммы) к этой задаче, конечно, нужно доказывать. Поэтому тема остаётся открыта |
Сообщ.
#12
,
|
|
|
swf,
А пример исходных данных можно посмотреть, как задана прибыль от вложений ресурса? Допустимо ее аппроксимировать линейной функцией либо найти другое математическое упрощение? |
Сообщ.
#13
,
|
|
|
Это учебные задачи на динамическое программирование.
Там обычно или без затей 0 ... M, или 0, 40, 80, 120, или как-то линейно от номера варианта прибыли. Для таких входных данных, конечно, класс P. А вот если прибыль - любая точка RM+1, то нигде не сказано, к какому классу относится задача. |
Сообщ.
#14
,
Сообщение отклонено: Akina -
|