Задача про упаковке/оптимизации

У нас это всё изучалось в курсе "Методы оптимизации". Поищи по этому словусочетанию.

А также "исследование операций".

чтобы было проще задача примерно такая :
есть N типов сигналов,
на общем входе M сигналов (M>>N) многие сигналы однотипны;
есть порядка десятка разных хреновин каждая может обрабатывать несколько типов сигналов и для каждого типа имеет несколько входов.
Плюс она(хреновина) имеют габариты (по крайней мере длинну); 
Надо минимизировать кол-во хреновин, и вписать всё в общий габарит.

Теория оптимизации (применительно с dif уравнениями, a-la градиентнтый спуск) вряд-ли тут имеет место быть :(

У нас это читалось в курсе "Теории Оптимального Планирования и Упраления", которая есть часть "Исследования операций".

Это что-то вроде задачи об укладке ранца. Дискретное программирование.

Думать лень, честно говоря :(

Формализуй это более подробно. Тогда и нужный метод будет понятен. Хреновины равнозначны (кроме размера и входов)?

По крайней мере, генетическим алгоритмом можно сделать (он зело универсальный). Но при этом решение может быть не оптимальным.

> чтобы было проще задача примерно такая :
Непонятно совершенно какая задача. Что конкретно надо оптимизировать? Добрать минимум хреновин так чтобы все сигналы могли быть обслужены и при этом сумма габаритов хреновин была наименьшая? При этом неважно что некоторые хреновины будут дублировать обслуживание? Ну тогда "жадным" или динамическим алгоритмом просто добирай хреновины и выбери наилучший вариант. Возможно динамическое программирование позволит убежать из n! в какое-нибудь n^3. Динамический алгоритм наверное будет напрашиваться из рюкзаковой проблемы, возможно добавиться какое-нибудь *n^k в сложности. А возможно будет сложнее потому что сигнал имеет идентификатор а не просто является единицей "веса". Возможно это приведет к тому что динамическое программирование будет слишком замороченно. Помедитируй в тетрадке.

Динамическое программирование описано в любой книжке про алгоритмы, например Томас Кормен и ко "Введение в алгоритмы", наверняка в каком-то томе Кнута.

Задача просится на олимпиадные конкурсы.

Или вероятность прихождения сигналов известна (или может быть проанализированна) и не равномерна? Ну тогда все сложнее.

dif уравнения, методы Ньютона и прочий градиентный спуск тут по-моему непричем.

PS Дай конкретную задачу может люди что-то придумают. Еще в фиде есть конфа RU.ALGORITHMS там не смотря на то что фидо все мрет мрет и никак не умрет есть какой-то траффик и если грамотно и точно задать вопрос, то можно получить ответ.

При малом количестве хреновин и слотов на них можно пробовать решать проблему начиная из подхода в n^2 в примерно таком ключе:

1. Вот беру я хреновину. Вот поставлю я ее в слот #. Вот имею я X слотов. Куда хреновину могу поставить? В каждый слот. Вот туда ее и ставлю. Во все слоты. В каждом слоте два варианта с хреновиной и без.

2. Вот беру я вторую хреновину. А вот засуну я ее во все слоты и посмотрю что будет.

3. Вот беру я третью хреновину.

Отсюда следует какая-то таблица XxY, в которой что-то происходит, в процессе брания хреновин и умещения их в слоты можно считать какие-то локальные минимумы и на их основании делать какие-то выводы, это и есть динамическое программирование.

Задача совершенно не ясна. Чтобы ее решить, для начала необходимо ее точно и четко сформулировать и узнать какие максимальные данные могут быть на входе. Если у тебя 100 хреновин то вохможно какое-нибудь брутальное n*n тебя вполне устроит.

Ключевые слова: динамическое программирование, жадные алгоритмы, вычислительная сложность.

более детально : есть лаб.шкаф, там есть рейки для установки аппаратуры - хреновин, в шкаф идёт пучёк разнотипных проводов (по эл.х-кам разнотипных), номенклатура хреновин весьма обширна, например одна имеет 5 разъёмов для 5 Hz сигналов и 3 разъема чисто логических (есть 5V на входе или нет)..в шкаф зашло к примеру 20 проводов с несущей частотой, 15 логических и 6 ещё каких-то (например потенциальных), надо минимизировать число хреновин для полного приёма/комутации всех сигналов. Да - размеры хреновин к сожалению измеряются не в слотах, а в милиметрах :(

при переходе от лаб.шкафа к реальным вещам цены и кол-во хреновин кусаются :)

Понятно, что алгоритм жадный, понятно что искать его наверное надо на стыке теории графов и комбинаторики - но ведь явный велосипед..Такое должно было быть решено и описано в немеренном числе раз :)

В идеале хотелось бы найти схожую проблему и её решение. Или хотя-бы подходы к решению.

Ну начни с этакого жадного DFS'а (как я понимаю простой DFS не может быть из-за большого количества хреновин). Надо обслужить все провода. Берем первый провод и придумываем какую-нибудь структуру данных которая позволяет быстро выбрать для этого провода минимальную по цене хреновину. Берем эту хреновину и выкидываем из множества проводов то что она обслуживает. Отнимаем также от миллиметров то что заняла хреновина.

Следом берем из покоцанного множества проводов (или непокоцанного если хреновина обслуживает кучу ненужного нам шыта) следующий провод и повторяем для него также.

В итоге придем к ситуации в которой или мы обслужили все провода или кончилось место. Если кончилось место то в ближайшем к концу места рекурсивном шаге выбираем хреновину чуть подороже (но с меньшим местом).

Можно при выборе хреновины ориентироваться не просто на цену а на сумму цена + количество занятых миллиметров либо на количество проводов которые обслуживает хреновина.

Это самое простое что приходит в голову, проще только вообще брутальный DFS. Генетические алгоритмы позволяют этакие DFS'ы ускорить, но это все слишком сложно и муторно и имеет смысл только для огромных по данным проблем.

Если попробовать это дело привести к динамическому программированию то можно подумать в такую сторону:

Если бы параметр у хреновин был один (цена или миллиметры) то все банально:

хреновина1 хреновина 2 ....
провод.1 | | |
провод.2 | | |
провод,3 | | |

Попросту бери минимумы для заданноного количества проводов и все. Поскольку параметра у тебя два то наверное от чего-то DFS'оватого не уйти.

Можно попробовать подумать над этой таблицей в таком ключе: в ней находится информация о выборе хреновины для каждого провода. Находясь в конкретном row можно ли выбрать несколько подороже хреновину ориентируюясь на предыдущее row'ы? По-моему нет потому что ты не знаешь что выберешь в следующих row'ах и соотв. не знаешь влезешь ли ты в доступное место или нет.

По-моему от DFS'а описанного выше не дется + heuristics основанная на том что выбираем не первую попавшуюся хреновину а например самую дешевую хреновину или хреновину обслуживающую наибольшее количество проводов.

По-моему тут ничего не выдумаешь, но это просто первый взгляд после трех пив. Спроси в соответсвующих форумах (как предложенный выше RU.ALGORITHMS в фиде).

То есть динамическое программирование напрашивается само собой если бы не факт что параметра оценки у тебя два. Соответсвенно динамическое программирование которое просто говорит: мой текущий выбор основан на текущей ситуации, а предыдущий min а тяну из выбора для текущий-1 элементов предудщих, тебе не поможет потому что какой min ты хочешь тянуть? Да минимум выбора хреновины для провода n это минимум выбора хреновины для провода n отдельно от всего + минимум выбора n-1 предыдущих проводов, но критериев оценки у тебя два следовательно выберай одну за основную а по другой едь DFS'ом или вводи в DFS heuristics основанный на них обоих.

Посмотри на форуме сайта http://algolist.manual.ru, там было обсуждение решения дискретных задач, и даже была рабочая программа, которая решала их генетикой, в том числе задачу о рюкзаке.

> при переходе от лаб.шкафа к реальным вещам цены и кол-во хреновин кусаются :)

Конкретизируй пожалуйста, минимаизация количества хреновин при ограничении на общий размер или
минимизация цены за эти хреновины при том же ограничении?

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