问题
如果问题是安排会议的实际任务，那么在提出问题时会出现一些错误。
这是因为工人的数量，甚至可用的桌子和座位的数量都不是基本的物理常数：
- 有人可能被解雇，无法参加下一次会议；
- HR为新项目增聘了10名工人，所有工人都必须参加下一次会议；
- 下周开始餐厅装修，下个月只有20张桌子。
所以问题听起来是这样的：“我们需要在接下来的 5-10 个工作日安排会议，让尽可能多的人与他们以前没有交谈过的人会面，并尽可能少的人与其他人交谈两次以上”。
因此，问题不在于生成一整套排列。问题是关于下一次 N 次会议的最佳计划。
理论
问题可以归类为一般数学优化问题。对于这类问题，我们的目标是找到最佳解决方案，该解决方案以函数的参数值集的形式呈现，为目标函数提供最大值或最小值。
要制定一个问题，我们必须找到问题的根源：
- 为每个人最大化与会面的人数
- 为每对人最小化会议次数
每个目标都谈论一对人之间的对话，因此我们必须根据“相遇”来制定问题。
表示P为人数，i in [1..P]并表示j in [1..P]为人员索引。
表示M为会议数量和 m in [1 .. M]会议编号。
那么让我们介绍一下a(i,j,m) | i < j, i in [1..P], j in [1..P], m in [1..M]两个人在具体会议上会面的事实。之后，可以为问题制定目标函数和边界条件。
数学方法
请注意，只有在极少数情况下才有可能获得确切的解决方案（任何人在循环结束前只与另一个人见面一次）。
这是 NP 完全类问题，最佳匹配公式是“满足 1 度共度条件的 k 均匀超图中完美匹配的优化问题”。
对于进一步的理论研究，您可以在数学中提出问题或检查可用于 k 均匀超图分区的最新作品，例如“密集超图中的多项式时间完美匹配”
解决方案必须有确切的(P-1)/(T-1)=(320-1)/(8-1)=45.5714285714会议，因为每次一个人遇到 7 个其他人，“其他人”的数量是 319。所以根据问题的条件，可能是 45 次会议，直到某对人遇到两次。
StackOverflow（链接）上已经有一个类似的问题，答案很好。请注意，此算法会留下空白位置，因为要完全放置所有人，它需要seats * prime = person_count41 人作为素数。
以下是使用此解决方案 ( SQLFiddle ) 的查询。
with params as (
select
320 n, -- number of persons
8 k, -- number of seats per table
41 p -- least prime which greather or equal n/k
from dual
),
person_set as (
select level person_id from dual connect by level <= (select n from params)
),
person_map as (
select
person_id,
mod( mod(person_id, p.k * p.p), p.k ) x,
trunc( mod(person_id, p.k * p.p) / p.k ) y
from person_set, params p
),
meetings as (
select (level-1) meeting_no
from dual
connect by level <= (select least(k*p, (n-1)/(k-1)) from params)
),
seats as (
select (level-1) seat_no
from dual
connect by level <= (select k from params)
),
tables as (
select (level-1) table_no
from dual
connect by level <= (select p from params)
),
meeting_plan as (
select --+ ordered use_nl(seats tables)
meeting_no,
seat_no,
table_no,
(
select
person_id
from
person_map
where
x = seat_no
and
y = mod(meeting_no*seat_no + table_no, p.p)
) person_id
from
meetings, seats, tables, params p
)
select
meeting_no,
table_no,
max(case when seat_no = 0 then person_id else null end) seat1,
max(case when seat_no = 1 then person_id else null end) seat2,
max(case when seat_no = 2 then person_id else null end) seat3,
max(case when seat_no = 3 then person_id else null end) seat4,
max(case when seat_no = 4 then person_id else null end) seat5,
max(case when seat_no = 5 then person_id else null end) seat6,
max(case when seat_no = 6 then person_id else null end) seat7,
max(case when seat_no = 7 then person_id else null end) seat8
from meeting_plan
group by meeting_no, table_no
order by meeting_no, table_no
实用方法
从实用的角度来看，我们不需要具有理论证明的完全最优解。如果一个人不止一次遇到另一个人，这没什么大不了的，所以有可能停在几乎最佳的解决方案上。
如果我们开始将人员一个接一个地放置在会议和桌子上，并试图将每对人员的交叉点数量保持在尽可能低的水平，则可以根据经验规则生成这样的解决方案。
有许多可能的放置策略，其中一种如下所示。
出于演示目的，我使用 Oracle，因为该数据库存在于问题标签中，并且可以在SQLFiddle站点上找到。
示例数据库架构设置包括三个表：
person- 带有工人名单的表格；
person_pair- 包含所有唯一工作人员对的列表以及每对工作人员的交集计数，总共floor((P*P)/2) - floor(P/2)行。在P=320 的情况下，它包含 51040 行。
meeting- 每个会议上每个人的位置信息表。
在示例代码中，由于 SQLFiddle 站点上的资源消耗限制并保持结果数据集可观察，因此限制了工作人员的20数量和座位数量。4
下面是方案设置和填充的代码。请查看评论以了解有关表字段的更多信息。
-- List of persons
create table person(
person_id number not null -- Unique person identifier.
);
-- primary key
alter table person add constraint pk_person primary key (person_id) using index;
-- List of all possible unique person pairs
create table person_pair(
person1_id number not null, -- 1st person from pair, refers person table.
person2_id number not null, -- 2nd person from pair, refers person table.
-- person1_id always less than person2_id.
meet_count number -- how many times persons in pair meet each other.
);
-- primary key
alter table person_pair add constraint pk_person_pair primary key (person1_id, person2_id) using index;
-- indexes for search
alter table person_pair add constraint idx_pair2 unique (person2_id, person1_id) using index;
-- Placement information for meetings
create table meeting(
meeting_number number not null, -- sequential meeting number
table_number number not null, -- table number
person_id number not null, -- person placed on that table and meeting
seat_no number -- seat number
);
-- primary key: person can seat on the same table only once in one meeting
alter table meeting add constraint pk_meeting primary key (meeting_number, table_number, person_id) using index;
-- disallow duplicate seats on the same table during one meeting
alter table meeting add constraint miting_unique_seat unique (meeting_number, table_number, seat_no) using index;
-- person can participate in meeting only once
alter table meeting add constraint miting_unique_person unique (meeting_number, person_id) using index;
填充初始数据（SQLFiddle）：
begin
-- Fill persons list with initial data
insert into person(person_id)
select level from dual connect by level <=20;
-- generate person pairs
insert into
person_pair(person1_id, person2_id, meet_count)
select
p1.person_id,
p2.person_id,
0
from
person p1,
person p2
where
p1.person_id < p2.person_id
;
end;
/
select * from person order by person_id
/
select * from person_pair order by person1_id, person2_id
/
生成会议
策略由两部分组成：
1. 按特定顺序选择人员；
2. 将列表中的人一一放在最合适的桌子上。
在选择列表中安排人员是试图将之前多次见面的人员尽可能早地放置在不同的桌子上。
安排人员比较棘手，在那个阶段的主要目的是最大限度地增加第一次会议的次数和最大限度地减少重复会议的次数。因此，它接近于为优化问题构建适当的目标函数的问题，这在大多数现实世界的情况下都是不平凡的。
我选择这个标准：
对于每张桌子计算两个因素：“有吸引力”（A） - 为什么将人放在那张桌子上和“排斥”（R） - 为什么人不能坐在那张桌子上。
这个因素共同构成了决赛桌的安排因素：
-A*A - (if A=0 then 0 else R/2) + R
“有吸引力”因素是指已经被安排在桌子上但当前人以前没有见过的人数。
“排斥”因素计为当前人与所有已经在桌的人的会议次数的总和。
很可能它不是那么好，但足以举例说明。例如，可以扩展公式以考虑自上次会议以来已经过去了多少时间。
您可以尝试建立良好的表达方式来自行选择表格。
接下来是生成会议的代码。
代码（SQLFiddle）
declare
vMeetingNumber number; -- number of current meeting
vNotMeetPairCount number; -- number of pairs not meet before
vTableCapacity number := 4; -- number of places at one table
vTableCount number; -- number of tables
begin
-- get next meeting number for case of continous generation
select nvl(max(meeting_number),0) + 1 into vMeetingNumber from meeting;
-- count minimum required table number
select ceil(count(1)/vTableCapacity) into vTableCount from person;
-- number of remaining pairs who don't meet before
select count(1) into vNotMeetPairCount
from person_pair
where meet_count < 1;
-- Generate new meetings while not all persons meet each other
while (vNotMeetPairCount > 0) loop
-- select list of persons to place
for cPersons in (
with person_meets as (
select
pp.person1_id, pp.person2_id, pp.meet_count,
( row_number() over (
order by pp.meet_count desc, pp.person1_id
)
) row_priority
from
person_pair pp
)
select person_id from (
select person_id, sum(pair_meet_count*pair_meet_count) pair_meetings from (
select person1_id person_id, meet_count pair_meet_count from person_meets
union all
select person2_id person_id, meet_count pair_meet_count from person_meets
)
group by person_id
)
order by pair_meetings desc
) loop
-- add current person to most applicable table
insert into meeting(meeting_number, table_number, person_id, seat_no)
select
vMeetingNumber, table_number, cPersons.person_id, seat_no
from (
with available_tables as (
select
table_number, places_occupied
from (
select
t.table_number,
(
select count(1)
from meeting m
where
m.meeting_number = vMeetingNumber
and
m.table_number = t.table_number
) places_occupied
from (
select level table_number
from dual connect by level <= vTableCount
) t
)
where places_occupied < vTableCapacity
)
select
table_number,
seat_no,
( row_number() over ( order by
-attractor_factor*attractor_factor - decode(attractor_factor,0,0,repellent_factor/2) + repellent_factor
)
) row_priority
from (
select
t.table_number,
t.places_occupied + 1 seat_no,
(
select
count(1)
from
meeting m,
person_pair pp
where
m.table_number = t.table_number
and
m.meeting_number = vMeetingNumber
and
pp.person1_id = least(m.person_id, cPersons.person_id)
and
pp.person2_id = greatest(m.person_id, cPersons.person_id)
and
pp.meet_count = 0
) attractor_factor,
(
select
nvl(sum(meet_count),0)
from
meeting m,
person_pair pp
where
m.table_number = t.table_number
and
m.meeting_number = vMeetingNumber
and
pp.person1_id = least(m.person_id, cPersons.person_id)
and
pp.person2_id = greatest(m.person_id, cPersons.person_id)
and
pp.meet_count > 0
) repellent_factor,
1 random_factor --trunc(dbms_random.value(0,1000000)) random_factor
from
available_tables t
)
)
where
row_priority = 1
;
end loop;
-- Update number of meets
update person_pair
set meet_count = meet_count + 1
where
(person1_id, person2_id) in (
select
m1.person_id person1_id,
m2.person_id person2_id
from
meeting m1,
meeting m2
where
m1.meeting_number = vMeetingNumber
and
m2.meeting_number = vMeetingNumber
and
m1.table_number = m2.table_number
and
m1.person_id < m2.person_id
)
;
-- advice to next meeting
vMeetingNumber := vMeetingNumber + 1;
-- count pairs who don't meet before
select count(1) into vNotMeetPairCount
from person_pair
where meet_count < 1;
end loop;
end;
多一点理论
生成的解决方案可以用作一些多准则优化方法的起点，但要使用它，您必须对问题有良好的正式表述。
希望以上所有内容可以帮助您解决问题。