Разделение входных данных на наборы на основе атрибута

Question

Привет!

Мне кажется, что эта проблема связана с проблемой упаковки бинов, а также с проблемой разделения секций ... Я просто хочу отослать это кому-то, прежде чем идти слишком глубоко по пути.

У меня есть входные данные (в файле данных) следующим образом:

entry_one 55
entry_two 56
entry_three 61
entry_four 62
entry_five 62
entry_six 68
entry_seven 72
entry_eight 73
entry_nine 78
entry_ten 79
entry_eleven 84
entry_twelve 85
entry_thirteen 91
entry_fourteen 92
entry_fifteen 99
entry_sixteen 100
entry_seventeen 121
entry_eighteen 125
entry_nineteen 127
entry_twenty 161

С этими данными я хочу иметь алгоритм, который: группирует записи в группы таким образом, чтобы связанные с ними числовые значения записей в пределах группы находились в пределах X (в моем случае, X равно 16.) Так, например, одно расположение может быть :

group one:
 entry_one
 entry_two
 entry_three
 entry_four
 entry_five
 entry_six

group two:
 entry_seven
 entry_eight
 entry_nine
 entry_ten
 entry_eleven
 entry_twelve

group three:
 entry_thirteen
 entry_fourteen
 entry_fifteen
 entry_sixteen

group four:
 entry_seventeen
 entry_eighteen
 entry_nineteen

group five:
 entry_twenty

Эта конкретная договоренность была достигнута с использованием наивного жадного алгоритма, в котором я начал с самого низкого значения (entry_one's 55), и позволил всем значениям, которые были ниже 55 + 16, быть частью этой группы. Затем я начал со следующей записи, которой не было в этой группе (entry_seven's 72), и разрешил всем значениям, которые были ниже 72 + 16, входить в группу этой (группа два) и т. Д. заказ.

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

Какие-нибудь мысли, модули, алгоритмы, примеры кода, которые могут предложить люди?

Спасибо!

РЕДАКТИРОВАТЬ: Я подумал, что я должен добавить, как это отличается от проблемы упаковки бункера. В задаче упаковки бинов оптимизация такова: «учитывая эти ячейки фиксированного размера, с этими объектами фиксированного размера, как я могу вставить большую часть этих объектов фиксированного размера в эти ячейки, не переполняя каждую ячейку». В моем случае у меня есть ячейки размером бесконечного , но с фильтрованной записью, так что если объект «соответствует» подписи для ячейки, он может быть вставлен в указанную ячейку, но мы хотим, чтобы минимизировать общее количество бинов, которые нам нужно создать.

Answer 1

1. Начало в точке, ближайшей к средней точке
2. выбрать все значения в пределах половины диапазона
3. Используйте свое существующее решение, выходя в обоих направлениях.
4. Повторите с шага 2, используя все остальные точки в исходном выделении.
5. выберите лучший результат.

---

В худшем случае это проблема O(n2), поскольку вы можете заменить шаг 4 на «повторить со всеми точками».

Answer 2

Если я правильно понимаю проблему, то жадный алгоритм на самом деле оптимален. Пусть G - жадное решение, а S - любое решение. Рассмотрим первую группу, где G отличается от S. Поскольку G - жадное решение, группа G больше, чем S. Например,

G : [1, 2, 3][4, 5, 6, 7][8, 9, 10][11, 12]...
S : [1, 2, 3][4, 5, 6][7, 8, 9][10, 11, 12]...

Мы можем вывести новое решение S 'из S, которое согласуется с G по более длинному префиксу, без введения новой группы. Просто украдите несколько предметов из следующей группы. Результирующие группы действительны, потому что одна уже находится в G, а другая является подгруппой допустимой группы.

S': [1, 2, 3][4, 5, 6, 7][8, 9][10, 11, 12]...

Из индукции следует, что G на самом деле оптимальна.