Например, у вас есть несколько списков double, которые вам нужно распределить по нескольким «корзинам» фиксированного размера (размер корзины также равен double). Есть два дополнительных ограничения:
Значения из определенных списков могут поступать только в определенные (предварительно заданные) сегменты:
bucket1 <-\ |--- list1 / / bucket2 <--\ bucket3 <---- list2 bucket4 <--/ bucket5 <--- list3Результирующее распределение должно быть как можно более равномерным (чтобы все ковши имели коэффициент загрузки, например,
0.5).
Конкретный пример такой проблемы: представьте, что у вас есть несколько блоков питания («ведер») и несколько плат ламп. Каждый блок питания подключается к одной или нескольким платам, каждый блок питания имеет разную мощность, лампы потребляют разное количество энергии. Если какая-то плата подключена к нескольким блокам питания, то можно «назначить» часть ламп на первый источник питания, часть - на второй и т. Д.
Сделать это с помощью грубой силы быстро становится невозможным для большого количества элементов.
Есть действенный подход?
РЕДАКТИРОВАТЬ: Я разработал следующий подход, который, кажется, довольно быстро приводит к нужному результату. Идея такая:
- Сначала для каждого списка я распределяю элементы по разрешенным сегментам, используя эвристику наименее загруженных сегментов.
- Then, I do the following:
- for each list:
- remove the items corresponding to the list from the buckets
- распределить их снова, используя ту же самую наименее загруженную эвристику
- рассчитать отношение размера максимально загруженного ковша к минимально загруженному (для разрешенных ковшей)
- завершите цикл, если коэффициент меньше некоторой константы (я взял
1.02) или если прошло слишком много шагов.
- for each list:
Общая идея состоит в том, чтобы «сгладить» сегменты до тех пор, пока распределение не станет достаточно ровным, что обычно означает, что мы достигли необходимой цели.
Это хороший алгоритм?
