策划一个和平的聚会
有很多人--有些人恨对方，有些人爱对方，有些人不认识对方.如果(A恨B，A坐在B旁边)或(A爱B和A不坐在B旁边)，那将是一场战争。我正在准备我朋友的生日聚会，所以我不想让派对变成战场，我有这样的清单：
a1讨厌a2
a1喜欢a3
a3喜欢a2
..。
有没有一个有效的算法来安排我朋友的座位，这样我们就不会有战争了？
我目前正在使用nave蛮力解，生成所有排列，以找到可行的安排。
回答 2
Stack Overflow用户
发布于 2014-09-09 13:20:14
您应该将此作为一个图形问题来处理。我以为你想把客人围成一圈。
让V做你的客人。让E是所有顶点对的集合，(A, B)，这样A和B就不互相憎恨了。在这个图中找到一个哈密顿循环已经解决了这样一个问题，那就是憎恨对方的人不能坐在一起，因为这些边不存在。
现在你需要强制要求彼此相爱的人坐在一起。对于每一对顶点(A, B)，如A和B彼此相爱，则添加具有边(A, A')、(B, B')和(A', B')的顶点A'和B'。A'和B'都有度2，所以哈密顿循环必须包含(A', B')。
现在，只要找到哈密顿循环，你就有了座位布局。不幸的是，这个问题是NP完全的，但至少它是很好的研究。
Stack Overflow用户
发布于 2014-09-09 13:01:08
如果您关心的不仅仅是相邻的位置(例如，如果人们不能面对面地坐着)，那么我会亲自使用遗传算法。
你知道什么是好比赛，但很难做到。
伪码警报
假设你有一个人的数据模型
person
+loves : person[]
+hates : person[]
+id : string //typically name, or a b c in your example你有一个函数来计算两个人的适应度
okToSitNextToEachOther(person1 : person, person2 : person)
return (person1.loves.contains(person1) ? 1 : 0) +
(person1.hates.contains(person2) ? -2 : 0); // hate more important than love
//do the same for person2 if hate/love is directional创建表格安排的数据模型。然后，建立一个函数来评估该安排的适合性。
table
-x : int //length of a table side, set in constructor
+seatRow1 : person[x]
+seatRow2 : person[x]
+calculateMatch() : float //you could return int of error count or a percentage
+mutate() : void // randomly swap people who violates your rule around创建一个随机填充x表的管理器(足够用于填充的表)。让经理能够对匹配最少的表的数据进行变异。(变异意味着交换周围的人)。
PartyManager
-people : person[] //pass in constructor
-tables : table[]
+calculateMatch() : float //iterate over all tables and return sum of match
+mutate() : void //iterate over all tables and mutate those who does not suit match requirement
+clone() : PartyManager //clone this 现在，创建许多经理，并将他们都列在一个列表中。循环，直到其中一个经理有一个“足够好”的安排。到那时为止。给每个经理打电话。删除最不成功的，并为您删除的每一个创建一个新的，并使用最成功的种子，然后对这些种子进行变异。
PartyManager match = null
while (true) {
PartyManager bestManager = managers.max( m => m.calculateMatch() ) //find the best match
for each partyManager in managers
if partyManager.calculateMatch() < TOO_BAD
clone = bestManager.clone()
clone.mutate()
managers.add(clone)
managers.remove(partyManager)
else if partyManager.calculateMatch() < GOOD_ENOUGH
partyManager.mutate()
else
match = partyManager // we fount a match
break如果您需要的话，我可以填写更多的信息，但是看看我链接到的wiki。
https://stackoverflow.com/questions/25745120
复制相似问题
腾讯云开发者
