Посмотрите, я отредактировал свой ответ: каждый алгоритм получил более высокие оценки в соответствии с показателями других, что удивительно - поскольку предложенный вами алгоритм получил более низкие оценки по той же метрике, которую он пытался минимизировать.
твует множество S, содержащее N целых чисел, каждое со значением 1 <= X <= 10 ^ 6. Проблема состоит в том, чтобы разбить множество S на k разделов. Значение раздела - это сумма элементов, присутствующих в нем. Разделение должно быть выполнено таким образом, чтобы общее значение множества S было справедливо распределено между k разделами. Математическое значениесправедливо также необходимо определить (например, цель может состоять в том, чтобы минимизировать стандартное отклонение значений разделов от среднего значения набора S (то есть суммы (S) / k))
например S = {10, 15, 12, 13, 30, 5}, k = 3
Хорошее разбиение будет {30}, {10, 15}, {12, 13, 5}
Неверное разбиение будет {30, 5}, {10, 15}, {12, 13}
Первый вопрос - математически выразить условие, чтобы один раздел был лучше другого. Второй вопрос - как решить проблему. Проблема в NP-Hard. Есть ли эвристика?
В задаче, которую я пытаюсь решить, N <= (k * logX) ^ 2 и K варьируется от 2 до 7.
================================================== ================================
Основываясь на других связанных вопросах SO, есть две разумные функции для оценки распределения:
а) Минимизировать значение раздела с максимальным значением.
Во-вторых, это не очень хорошая метрика. Рассмотрим набор {100, 40, 40}, который нужно разделить на три подмножества. Этот показатель не различает следующие два распределения, хотя одно явно лучше другого.
Распределение 1: {100}, {40}, {40} и Распределение 2: {100}, {40, 40}, {}
б) Минимизировать максимум разности любых двух значений в данном разделе, т. е. минимизировать максимум | A-B | для любого А, Б