Приближенный алгоритм для минимальной переносимости слов

Question

Я ищу эффективный алгоритм (в идеале C-подобный псевдокод), чтобы дать примерное решение следующей проблемы с разделами. Для заданной последовательности S = { a & # x005f; i : i = 1, ..., n } и границы B , определить разбиение S на некоторое число m смежных подпоследовательностей следующим образом. Для каждой k пусть s & # x005f; k будет суммой элементов k -ой подпоследовательности. Раздел должен удовлетворять:

1. с & # x005f; k & # x2264; B для каждого k (предположим, что значения B и a & # x005f; i такой, что это всегда возможно)
2. m минимально (не меньший раздел удовлетворяет # 1);
3. некоторая мера дисперсии (например, дисперсия или максимальная попарная разница между s & # x005f; k ) минимальна для всех разделов размера м .

Я знаю, что это тесно связано с алгоритмом переноса слов минимальной шероховатости . Я ищу что-то, что может дать «достаточно хорошее» решение для небольших значений n (менее 15) без необходимости извлекать тяжелые боеприпасы, такие как динамическое программирование, но также что-то немного более быстрое, чем грубая сила.

Answer 1

Пусть S обозначает сумму всех предметов, а n - количество предметов.Если вы поместите элементы в m строк, вы будете иметь вес не менее S / m для каждой строки.Поскольку S / m ≤ B, вы получаете m ≥ S / B.Я начинаю с потолка (S / B) как значения m, а затем увеличиваю m на единицу, пока не будет найдено решение.

Когда установлено m и задано n, это просто вопрос рекурсивного поискаправильные границы.Вы угадываете границы между строками одна за другой (рекурсивно) и возвращаетесь, когда решение становится невозможным.Если вы найдете решение, вы сохраните его для справки, потому что оно может быть наилучшим с точки зрения дисперсии.В конце концов вы выбираете лучшее решение.Если решений нет, то вы увеличиваете m на единицу и повторяете.

Answer 2

Я закончил простым поиском.Сначала я вычислил m , как описано в antti.huima (эта часть была очень простой и фиксированной m ).Затем я жадно распределял предметы (упаковывая каждую секцию в максимально возможной степени).Наконец, я запустил алгоритм обратного отслеживания, чтобы назначить дельту начальному индексу для каждой границы раздела, начиная с последнего раздела .Каждый delta_j показывает, как далеко назад перемещается начало раздела j из жадного начального положения.Нетрудно показать, что 0 <= delta_j <(размер раздела j-1) для каждого j> 1 (иначе жадный алгоритм вел бы себя по-разному).Это значительно сокращает пространство поиска по сравнению с поиском для заполнения разделов от 1 до m .

Я предполагаю, что некоторый эвристический вариант этого поиска возможен и будет болееэффективный, но я не очень старался найти его.