Для небольшой игры (для которой я немного вынужден использовать C ++, поэтому решения на основе STL могут быть здесь интересны) я столкнулся со следующей изящной проблемой. Мне было интересно, есть ли какая-нибудь литература по этому предмету, которую я мог бы прочитать, или умные реализации.
Коллекция S уникальных предметов {E1, E2, E3}, каждый предмет E имеет набор свойств, {P1, P2, P3 ...}
Эта коллекция должна быть разделена на S1, S2, S3, S4. Определяется, насколько большим должен быть S1..4. Мы можем предположить, что коллекция может быть правильно разделена на эти размеры до конца проблемы.
Теперь для S1 может появиться ряд ограничений {C1, C2 ..}, которые указывают, что, например, никакие элементы со свойством P1 не могут появляться в нем. Другое ограничение может заключаться в том, что он должен отдавать предпочтение элементам со свойством P2 с коэффициентом 0,8 (мы можем предположить, что эти типы ограничений нормированы для всех подмножеств на свойство).
«Взвешивание» не так сложно реализовать. Я просто заполняю какой-либо массив номерами кандидатов, в этом массиве больше представлены те, которые имеют больший вес. Затем я выбираю случайный элемент массива. размер массива определяет точность / гранулярность (в моем случае достаточно небольшого массива).
Проблема в том, что некоторые элементы не отображаются. Это может легко привести к ситуации, когда один элемент в S необходимо поместить в одно из подмножеств S1, S2, S3 или S4, но этого больше не может быть, потому что подмножества либо полностью заполнены, либо те, которые не являются У full есть определенное ограничение, что этот элемент не может появиться в наборе. Таким образом, вы должны отказаться от размещения. Это слишком часто может слишком сильно нарушить взвешенную вероятность.
Как называется эта проблема или она легко сопоставляется с другой (возможно, NP) проблемой?
РЕДАКТИРОВАТЬ: Пример:
S = {A, B, C, D, E, F, G, H, I, J, K, L, M}
S1 = [0,8 вероятность наличия гласного, не может иметь I или K, размер = 6]
S2 = [0,2 вероятности наличия ГЛАВНОГО, НЕ МОЖЕТ ИМЕТЬ, B, E, РАЗМЕР = 7]
Теперь предположим, что мы начинаем заполнение FOR (LETTER IN S):
ПИСЬМО А, создать массив заливки на основе ограничений свойств (0,8 против 0,2):
[1, 1, 1, 1, 1, 1, 1, 2, 2].
Выберите случайный элемент из этого массива: 1.
Теперь поместите A в S1.
Например, для буквы I единственным кандидатом будет 2, поскольку у S1 есть ограничение, которое я не могу в нем указать.
Продолжайте делать это, в конце концов вы можете получить:
C = {M} // еще одна буква для раздачи
S1 = A, B, D, E, F, G
S2 = C, F, G, I, K, L
Теперь, где разместить М? Я не могу быть помещен в S1, так как тот заполнен, и его нельзя поместить в S2, потому что он имеет ограничение, что M не может быть помещен в него.
Единственный способ - откатить назад какое-то размещение, но тогда мы можем слишком много возиться с взвешенным распределением (например, давая S2 один гласный из S1, который переворачивает естественное распределение)
Обратите внимание, что это становится немного более сложным (в том смысле, что потребуется больше возвратов), когда в игре задействовано больше поднаборов, а не только 2.