Я ищу алгоритм для распределения значений из списка, чтобы результирующий список был как можно более «сбалансированным» или «равномерно распределенным» (в кавычках, потому что я не уверен, что это лучший способ описать его ... позже я предоставлю способ измерить, если результат лучше, чем другие).
Итак, для списка:
[1, 1, 2, 2, 3, 3]
Один из лучших результатов после перераспределения значений:
[1, 2, 3, 1, 2, 3]
Могут быть и другие результаты, столь же хорошие, как этот, и, конечно, это становится более сложным с менее однородным набором значений.
Вот как измерить, если результат лучше, чем другие:
Подсчитайте расстояния между каждым предметом и следующим предметом с одинаковым значением.
Рассчитайте стандартное отклонение для этого набора расстояний. Более низкая дисперсия означает лучший результат.
Замечания:
- При расчете расстояния и достижении конца списка без нахождения элемента с таким же значением мы возвращаемся к началу списка. Таким образом, самое большее, тот же элемент будет найден, и расстояние для этого элемента будет длиной списка. Это означает, что список циклический ;
- Типичный список содержит ~ 50 наименований с ~ 15 различными значениями в разных количествах.
Так:
- В результате
[1, 2, 3, 1, 2, 3]
расстояния равны[3, 3, 3, 3, 3, 3]
, а стандартное отклонение равно0
; - В результате
[1, 1, 2, 2, 3, 3]
расстояния равны[1, 5, 1, 5, 1, 5]
, а стандартное отклонение равно2
; - Что делает первый результат лучше второго (чем меньше отклонение, тем лучше).
Учитывая эти определения, я спрашиваю, какие алгоритмы или стратегии мне следует искать.
Ответы:
Я столкнулся с этим вопросом, исследуя аналогичную проблему: оптимальное добавление жидкостей для уменьшения расслоения. Похоже, мое решение будет применимо и к вашей ситуации.
Если вы хотите смешать жидкости A, B и C в пропорции 30,20,10 (то есть 30 единиц A, 20 единиц B и 10 единиц C), вы получите стратификацию, если добавите все A, затем все B, а затем все C. Вам лучше смешивать меньшие единицы. Например, делайте единичные добавления в последовательности [A, B, A, C, B, A]. Это полностью предотвратит расслоение.
Я нашел способ сделать это, рассматривая это как некое слияние, используя очередь с приоритетами. Если я создаю структуру для описания дополнений:
Частота выражается как «один на каждый N». Таким образом, А, который добавляется три раза из шести, имеет частоту 2 (6/3).
И инициализировать кучу, которая изначально содержит:
Теперь я удаляю первый элемент из кучи и выводю его. Затем уменьшите его количество на 1, увеличьте приоритет по частоте и добавьте его обратно в кучу. В результате получается куча:
Затем удалите B из кучи, выведите и обновите ее, затем добавьте обратно в кучу:
Если я продолжу в том же духе, я получу желаемую смесь. Я использую пользовательский компаратор, чтобы гарантировать, что при вставке в кучу равных элементов Приоритета в первую очередь упорядочивается элемент с наибольшим значением частоты (т. Е. С наименьшей частотой).
Я написал более полное описание проблемы и ее решения в своем блоге и представил некоторый работающий код C #, который иллюстрирует ее. См. Равномерное распределение предметов в списке .
Обновление после комментариев
Я думаю, что моя проблема похожа на проблему ОП, и поэтому мое решение потенциально полезно. Я прошу прощения за то, что не сформулировал мой ответ больше в терминах вопроса ОП.
Первое возражение, что мое решение использует A, B и C, а не 0, 1 и 2, легко исправить. Это просто вопрос номенклатуры. Мне легче и менее запутанно думать и говорить «два А», а не «два 1». Но для целей этого обсуждения я изменил свои выводы ниже, чтобы использовать номенклатуру ОП.
Конечно, моя проблема связана с понятием расстояния. Если вы хотите «распределить вещи равномерно», подразумевается расстояние. Но, опять же, это был мой провал из-за того, что я не смог адекватно показать, насколько моя проблема похожа на проблему ОП.
Я провел несколько тестов с двумя примерами, которые предоставил ОП. То есть:
В моей номенклатуре они выражены как [2,2,2] и [4,3,2,1] соответственно. То есть в последнем примере «4 элемента типа 0, 3 элемента типа 1, 2 элемента типа 2 и 1 элемент типа 3».
Я запустил свою тестовую программу (как описано ниже) и опубликовал свои результаты. При отсутствии данных от ОП я не могу сказать, похожи ли мои результаты, хуже или лучше его. Также я не могу сравнить свои результаты с результатами кого-либо еще, потому что никто другой не опубликовал их.
Однако я могу сказать, что алгоритм обеспечивает хорошее решение моей проблемы устранения стратификации при смешивании жидкостей. И, похоже, это дает разумное решение проблемы ОП.
Для результатов, показанных ниже, я использовал алгоритм, который я подробно описал в своей записи в блоге, с начальным приоритетом, установленным на
Frequency/2
, и модификатором кучи, измененным для более частого элемента. Здесь показан измененный код с комментариями к измененным строкам.Запустив мою тестовую программу с первым примером OP, я получаю:
Так что мой алгоритм работает для тривиальной задачи, при которой все числа равны.
За вторую проблему, которую опубликовал ОП, я получил:
Я не вижу очевидного способа улучшить это. Его можно переставить, чтобы сделать расстояния для элемента 0 [2,3,2,3] или некоторого другого расположения 2 и 3, но это изменит отклонения для элементов 1 и / или 2. Я действительно не знаю, что «оптимальный» в этой ситуации. Лучше иметь большее отклонение по более частым или менее частым предметам?
Не имея других проблем в OP, я использовал его описания, чтобы составить несколько своих собственных. Он сказал в своем посте:
Итак, мои два теста были:
И мои результаты:
И для второго примера:
источник
Это "пахнет", как будто это может быть NP-трудно. Итак, что вы делаете, когда у вас NP-трудная проблема? Добавьте к этому эвристику, или алгоритм приближения, или используйте SAT-решатель.
В вашем случае, если вам не нужно абсолютно оптимальное решение, одной разумной отправной точкой может быть попытка смоделированного отжига . Существует естественный способ взять любое решение-кандидат и переместить его в соседнее решение-кандидат: случайным образом выбрать два элемента в списке и поменять их местами. Имитация отжига итеративно попытается улучшить решение. Вы можете найти много ресурсов по моделированию отжига, если вы не знакомы с ним. Вы также можете поэкспериментировать с другими наборами «локальных перемещений», которые вносят небольшие изменения в возможное решение, в надежде постепенно улучшить его (т. Е. Уменьшить стандартное отклонение расстояний).
Но я бы посоветовал вам начать с имитации отжига. Это первое, что я бы попробовал, потому что я думаю, что это может сработать.
источник
Эскиз эвристического алгоритма
У меня нет точного решения этой проблемы. Но поскольку комментарий Рафаэля предполагает, что это похоже на проблему разбиения, для которой были разработаны эвристические алгоритмы, я попробую эвристический подход. Это всего лишь набросок эвристического алгоритма.
Это будет направлять наш алгоритм.
Это может быть значение с очень многими из очень немногих случаев вначале. Я думаю, что на самом деле это не имеет значения, так как ограничения, создаваемые занятыми слотами, пропорциональны количеству размещенных значений (?).
Первое рассматриваемое значение может быть размещено без каких-либо ограничений. Затем остальные значения должны быть размещены таким образом, чтобы минимизировать их вклад в стандартное отклонение, но только в слоты, оставленные свободными от любых значений, которые были размещены ранее.
Размещение вхождений значения в оставшиеся слоты может быть выполнено с помощью алгоритма динамического программирования, чтобы объединить вычисления, которые размещают одинаковое количество значений между двумя позициями, оставляя только те, которые имеют минимальный вклад в стандартное отклонение (т.е. минимальное значение для суммы квадратов их отклонений).
Затем вы помещаете значения синглтона в оставшиеся слоты.
Я считаю, что в целом это должно дать разумное решение, но я пока не знаю, как это доказать или оценить разрыв с оптимальным решением.
источник
[0, 0, 0, 0, 1, 1, 1, 2, 2, 3]
и v4
мы бы поместили сначала значения1
(10/3 = 3.33
ближайший к v), затем2
(10/2 = 5
следующий ближайший), затем0
(10/4 = 2.5
)? Или: не могли бы вы привести пример «уменьшения среднего отклонения расстояния от значения v»?Похоже, я очень опаздываю на вечеринку, но отправляю сообщения на случай, если кто-то столкнется с этим снова. Мое решение похоже на плюс @ babou. Ранее сегодня у меня была проблема планирования во встроенной системе, которая привела меня к этой теме. У меня есть реализация, специфичная для моей проблемы в C, но я решил опубликовать более общее решение в Python здесь (версия C усложняется тем, что я ограничился небольшим стеком фиксированного размера и без памяти распределения, поэтому я выполняю весь алгоритм на месте). Используемая ниже методика сглаживания - это то, что вы можете использовать для рисования линии на экране с 2-битным цветом. Алгоритм здесь достигает более низкого балла (то есть лучше), когда измеряется с использованием суммы стандартного отклонения для входов, используемых Джимом Мишелем, чем это конкретное решение.
Результаты для
Если заданы входные данные в форме, заданной @moraes, можно преобразовать ее в форму, используемую этой функцией, за O (n) шагов, используя биты большой омега (n * log (n)) памяти, где n - количество элементов ( в списке с 255 элементами вам не понадобится больше 255 дополнительных байтов), если хранить параллельный массив с количеством повторений. Альтернативно, можно выполнить пару сортировок на месте с O (1) дополнительной памятью.
PS
Редактировать: я знаю, что это решение не дает оптимальный результат по контрпримеру. Вход
[6, 2, 1]
производит[0, 1, 0, 0, 2, 0, 0, 1, 0]
; лучшее решение есть[0, 0, 1, 0, 2, 0, 0, 1, 0]
.источник
Этот алгоритм работает с массивом целых чисел, где каждое целое представляет отдельную категорию. Он создает отдельные массивы для каждой категории. Например, если начальный массив [1, 1, 1, 2, 2, 3], он создаст три массива, [3], [2, 2], [1, 1, 1].
Оттуда он рекурсивно комбинирует два наименьших массива (в этом примере, [3] и [2,2]) и размещает элементы меньшего массива во втором наименьшем массиве, основываясь в основном на соотношении числа случаев большего против меньших категорий. В этом примере мы получим [2,3,2]. Затем он будет использовать этот массив в качестве меньшего массива, который будет объединен в следующий больший массив, пока не останется только один массив.
источник
Код ANSI C
Этот код работает, представляя прямую линию в n-мерном пространстве (где n - количество категорий), проходящую через начало координат с вектором направления (v1, v2, ..., vi, ... vn), где vi - это число предметы в категории i. Начиная с начала координат, цель состоит в том, чтобы найти следующую ближайшую точку к линии. На примере [0 0 0 0 0 1 1 1 2 2 2 3] получается результат [0 1 2 0 3 1 0 2 0 1 2 0]. Используя пример Лунджа [0 0 0 0 0 0 1 1 2], мы получаем [0 1 0 0 2 0 0 1 0], что в точности совпадает с результатом Лунджа.
Алгоритм стал более эффективным за счет использования только целочисленной арифметики и учета только разницы между расстояниями от каждой точки до прямой.
#define MAXCATEGORIES 100
int main () {int i = 0; int j = 0; int catsize = 0; int vector [MAXCATEGORIES]; int point [MAXCATEGORIES]; int category = 0; int totalitems = 0; int best = 0; длинный d2 = 0L; длинный vp = 0L; long v2 = 0L; длинная дельта = 0L; длинная бета = 0L;
}
источник
мое решение:
источник