对于一个小游戏(我有点被迫使用C++,所以基于STL的解决方案在这里很有趣),我遇到了下面的问题.我想知道是否有关于这个主题的文献我可以阅读,或者是巧妙的实施.
唯一项目{E1,E2,E3}的集合S,每个项目E具有一组属性,{P1,P2,P3 ...}
该集合应该在S1,S2,S3,S4中分开.它定义了S1..4必须具有多大的精确度.我们可以假设集合可以正确地分成这些大小以解决问题的其余部分.
现在,对于S1,可以出现许多约束,{C1,C2 ..},它们指定例如,没有具有属性P1的项目可能出现在其中.另一个约束可能是它应该支持具有属性P2的因子为0.8的项(我们可以假设这些类型的约束针对每个属性的所有子集进行了规范化).
"加权"并不难实现.我只是用一些候选数字填充一些数组,权重较高的数组在这个数组中表示得更多.然后我选择数组的随机元素.数组的大小决定了准确性/粒度(在我的例子中,一个小数组就足够了).
问题是禁止出现一些项目.它很容易导致S中的一个项目需要放置在子集S1,S2,S3或S4中的一个中的情况,但是由于子集全部已满或者不满足,因此不再发生这种情况.完全具有此项无法出现在集中的特定约束.所以你必须回溯展示位置.过于频繁地这样做可能会过多地违反加权概率.
如何调用此问题,或者它是否容易映射到另一个(可能是NP)问题？
编辑:示例:
S = {A,B,C,D,E,F,G,H,I,J,K,L,M}
S1 = [0.8有VOWEL的概率,不能有I或K,SIZE = 6]
S2 = [0.2有VOWEL的概率,不能有M,B,E,SIZE = 7]
现在,假设我们开始填写FOR(LETTER IN S):
字母A,根据属性约束(0.8 vs 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
现在,在哪里放置M？我不能被放置在S1中,因为那个已满,并且它不能放在S2中,因为它有一个约束,M不能放在其中.
唯一的方法是回溯一些位置,但是我们可能会过多地加重加权分布(fi,给S2一个S1的元音,它绕着自然分布翻转)
请注意,当更多子集在播放时,这会变得稍微复杂一些(在某种意义上需要更多的回溯),而不是仅仅2.