есть следующая задача:
дан набор объектов которые необходимо обработать на некотором количестве изолированных процессоров (у каждого своя память, в реальности — кластер многопроцессорных машин). Для каждого из объектов на основе исторических данных известно, сколько ресурсов он потребует (ресурсы — память, процессорное время, утилизация сети). Необходимо собрать объекты в кучки такие, чтобы все кучки были примерно одного размера по времени выполнения + минимизировали утилизацию сети + имели ограничение по памяти.
Для меня выглядит как NP задачка, т.к. если мне дадут готовые кучки, я могу легко написать проверочную функцию: просуммировать время, чуть более хитрым образом сложить память, ещё более хитрым образом сложить использование сети (т.к. разные объекты могут хотеть из сети одни и те же данные и это мне тоже заранее известно). Имхо похоже на задачу о рюкзаке, но немного хитрее =)
Не может ли кто-нибудь подсказать, в какую сторону мне почитать, если я хочу проводить такое разбиение максимально быстро, т.е. для меня не так уж принципиально получить идеальное разбиение.
Если важно, то язык — java (м.б. там уже все написано? =) )
Re: Алгоритм распределения ресурсов/задача о рюкзаке(?)
Здравствуйте, Rumata, Вы писали:
R>Не может ли кто-нибудь подсказать, в какую сторону мне почитать, если я хочу проводить такое разбиение максимально быстро, т.е. для меня не так уж принципиально получить идеальное разбиение.
а что если решить в терминах потоков? максимальный поток минимальной стоимости.
сходу не скажу, но похоже можно в ее терминах описать и решить соответствующими методами.
Re[2]: Алгоритм распределения ресурсов/задача о рюкзаке(?)
Здравствуйте, ilnar, Вы писали:
I>а что если решить в терминах потоков? максимальный поток минимальной стоимости. I>сходу не скажу, но похоже можно в ее терминах описать и решить соответствующими методами.
Задача NP-трудная. Здесь говорится, что найти "хоть какое-нибуть решение" можно с помощью эвристики:
The best fit decreasing and first fit decreasing strategies are among the simplest heuristic algorithms for solving the bin packing problem. They have been shown to use no more than 11/9 OPT + 1 bins (where OPT is the number of bins given by the optimal solution).[1] The simpler of these, the First Fit Decreasing strategy, operates by first sorting the items to be inserted in decreasing order by volume, and then inserting each item into the first bin in the list with sufficient remaining space. The sorting step is relatively expensive, but without it we only achieve the looser bound of 17/10 OPT + 2. A more efficient version of FFD uses no more than 71/60 OPT + 1 bins.[2][3] Recently, it was proved that the bound 11/9 OPT + 6/9 for FFD is tight.[4]
Although these simple strategies are often good enough, efficient approximation algorithms have been demonstrated[5] that can solve the bin packing problem within any fixed percentage of the optimal solution for sufficiently large inputs (this is called an asymptotic polynomial-time approximation scheme). This is an advantage the problem has over many other common NP-hard problems, some of which cannot be approximated within any constant factor at all.
Re[3]: Алгоритм распределения ресурсов/задача о рюкзаке(?)
Здравствуйте, Mace, Вы писали:
M>Здравствуйте, ilnar, Вы писали:
I>>а что если решить в терминах потоков? максимальный поток минимальной стоимости. I>>сходу не скажу, но похоже можно в ее терминах описать и решить соответствующими методами.
M>Задача NP-трудная. Здесь говорится, что найти "хоть какое-нибуть решение" можно с помощью эвристики: M>
M>The best fit decreasing and first fit decreasing strategies are among the simplest heuristic algorithms for solving the bin packing problem. They have been shown to use no more than 11/9 OPT + 1 bins (where OPT is the number of bins given by the optimal solution).[1] The simpler of these, the First Fit Decreasing strategy, operates by first sorting the items to be inserted in decreasing order by volume, and then inserting each item into the first bin in the list with sufficient remaining space. The sorting step is relatively expensive, but without it we only achieve the looser bound of 17/10 OPT + 2. A more efficient version of FFD uses no more than 71/60 OPT + 1 bins.[2][3] Recently, it was proved that the bound 11/9 OPT + 6/9 for FFD is tight.[4]
M>Although these simple strategies are often good enough, efficient approximation algorithms have been demonstrated[5] that can solve the bin packing problem within any fixed percentage of the optimal solution for sufficiently large inputs (this is called an asymptotic polynomial-time approximation scheme). This is an advantage the problem has over many other common NP-hard problems, some of which cannot be approximated within any constant factor at all.
точно! пытался вспомнить. тут действительно подходит задача упаковки. но я так понимаю, с несколькими условиями.
если подходить просто, можно все это решить в целочисленном программировании, библиотек полно. lpsolve например
Re[4]: Алгоритм распределения ресурсов/задача о рюкзаке(?)
Здравствуйте, ilnar, Вы писали:
I>>>а что если решить в терминах потоков? максимальный поток минимальной стоимости. I>>>сходу не скажу, но похоже можно в ее терминах описать и решить соответствующими методами.
M>>Задача NP-трудная. Здесь говорится, что найти "хоть какое-нибуть решение" можно с помощью эвристики:
I>точно! пытался вспомнить. тут действительно подходит задача упаковки. но я так понимаю, с несколькими условиями. I>если подходить просто, можно все это решить в целочисленном программировании, библиотек полно. lpsolve например
всем спасибо за ответы!
про потоки идея интересная, я пытался придумать, как ее красиво описать, но у меня честно говоря, не очень получилось: исток, затем плоско все процессоры, затем результат. Не уверен, что в такой постановке какие-то агоритмы для потоков дадут эффект.
про то, что НП трудая я знаю — вроде даже писал в первом посте =)
поэтому я не удивлен, что ее можно свести к не менее НП трудной задаче о потоках =)
про деревья/отсечения я читал, похоже, что все к тому идет, но алгоритм сильно не полиномаильный, чем мне не нравится =(
не хочется попасть на "худший случай"
lpsolve — мне бы для джавы чего-нибудь бы =)
кроме того, он, опять же, работает деревьями а я хочу такую эвристику, которая будет выдавать приемлимый результат за полиномилальное время (типа FFD с вики, но чуть-чуть поразумнее =) )
Re[5]: Алгоритм распределения ресурсов/задача о рюкзаке(?)
Здравствуйте, Rumata, Вы писали:
R>про то, что НП трудая я знаю — вроде даже писал в первом посте =) R>поэтому я не удивлен, что ее можно свести к не менее НП трудной задаче о потоках =)
А кто сказал, что задачи про потоки НП трудные? Другое дело, что даная задача нормально к потоковой не сведется ИМХО.
Re[5]: Алгоритм распределения ресурсов/задача о рюкзаке(?)
Здравствуйте, ilnar, Вы писали:
R>>lpsolve — мне бы для джавы чего-нибудь бы =) I>там кажись есть ява интерфейс
главный его недостаток неполиномиальность, а не то, что он не джава =(
