Sự cố
Nếu vấn đề là nhiệm vụ thực sự để lên lịch cuộc họp thì có một số sai lầm khi đặt câu hỏi.
Đó là bởi vì số lượng người lao động và thậm chí là một số bảng có sẵn và ghế không phải là một hằng số vật lý cơ bản:
- ai đó có thể bị sa thải và không thể tham gia vào các cuộc họp tiếp theo;
- Nhân sự đã thuê thêm 10 công nhân cho dự án mới và tất cả họ phải tham gia cuộc họp tiếp theo;
- Vào tuần tới, bắt đầu cải tạo phòng ăn và chỉ có 20 bàn sẽ có sẵn cho tháng tiếp theo.
Vì vậy, vấn đề có vẻ như sau: "Chúng tôi cần lên lịch cuộc họp trong vòng 5-10 ngày làm việc theo cách sao cho càng nhiều người có thể gặp gỡ với những người mà họ không nói trước và với người thấp có thể nói chuyện với người khác hai lần và nhiều hơn nữa ".
Do đó, sự cố không phải là tạo ra tập hợp đầy đủ các hoán vị. Vấn đề là về quy hoạch tối ưu cho các cuộc họp N tiếp theo.
Lý thuyết
Sự cố có thể được phân loại là chung mathematical optimization problem. Đối với loại vấn đề đó, chúng tôi có mục tiêu tìm giải pháp tối ưu được trình bày dưới dạng bộ giá trị đối số cho (các) hàm cung cấp giá trị lớn nhất hoặc tối thiểu cho (các) hàm mục tiêu.
Để xây dựng một vấn đề chúng ta phải tìm ra gốc rễ của câu hỏi:
- cho mỗi người phát huy tối đa một số người để đáp ứng với
- cho mỗi cặp người giảm thiểu một số cuộc họp
Mỗi mục tiêu đó nói về các cuộc hội thoại giữa một cặp người để chúng ta phải xây dựng một vấn đề về "đáp ứng".
Biểu thị P là số người và i in [1..P] và j in [1..P] làm chỉ mục người.
Biểu thị M làm số lượng cuộc họp và m in [1 .. M] làm số cuộc họp.
Sau đó, hãy giới thiệu a(i,j,m) | i < j, i in [1..P], j in [1..P], m in [1..M] như là một thực tế của cuộc họp giữa hai người trong cuộc họp cụ thể. Sau đó có thể xây dựng một hàm mục tiêu và giới hạn các điều kiện cho vấn đề.
cách tiếp cận Math
Xin lưu ý, rằng giải pháp chính xác (bất cứ ai gặp một người khác chỉ có một thời gian cho đến khi chu kỳ hoàn thành) có thể chỉ trong những trường hợp rất hiếm.
Đây là vấn đề lớp NP hoàn chỉnh và công thức phù hợp nhất là "vấn đề tối ưu hóa kết hợp hoàn hảo trong các hình ảnh siêu đồng nhất k thỏa mãn điều kiện mức độ 1 độ".
Để tìm hiểu thêm về lý thuyết, bạn có thể đặt câu hỏi tại số Mathematics hoặc kiểm tra latest works available để phân vùng siêu đồng nhất k, ví dụ: "Polynomial-time perfect matchings in dense hypergraphs"
Giải pháp phải có chính xác (P-1)/(T-1)=(320-1)/(8-1)=45.5714285714 cuộc họp vì mỗi lần gặp 7 người khác và "người khác" là 319. Vì vậy, có thể 45 cuộc họp theo các điều kiện của câu hỏi trước khi một số người gặp hai lần.
Có một câu hỏi tương tự với câu trả lời hay đã có trên StackOverflow (link). Lưu ý rằng thuật toán này để lại các vị trí trống, bởi vì cho vị trí đầy đủ của tất cả những người nó yêu cầu để seats * prime = person_count và 41 được chọn làm nguyên tố.
Dưới đây là truy vấn sử dụng giải pháp này (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
cách tiếp cận thực tiễn
Từ quan điểm thực tế chúng ta không cần giải pháp chính xác tối ưu với bằng chứng lý thuyết. Nếu một người gặp nhau nhiều hơn một lần thì đó không phải là vấn đề lớn, vì vậy có thể dừng lại ở giải pháp gần như tối ưu.
Giải pháp như vậy có thể được tạo ra trên cơ sở các quy tắc thực nghiệm nếu chúng ta bắt đầu đặt từng người một đến các cuộc họp và các bảng cố giữ số giao lộ cho mỗi cặp người càng thấp càng tốt.
Có nhiều chiến lược để có thể đặt và một trong số chúng được minh họa bên dưới.
Vì mục đích minh họa, tôi sử dụng Oracle vì cơ sở dữ liệu này có trong thẻ câu hỏi và có sẵn tại trang web SQLFiddle.
Ví dụ thiết lập giản đồ cơ sở dữ liệu bao gồm ba bảng:
person - bảng với danh sách của người lao động;
person_pair - bảng có danh sách tất cả các cặp công nhân độc đáo và số điểm giao nhau cho mỗi cặp, hoàn toàn là floor((P*P)/2) - floor(P/2) hàng. Trong trường hợp P = 320, nó chứa 51040 hàng.
meeting - bảng có thông tin vị trí cho từng người trong mỗi cuộc họp.
Ví dụ mã số công nhân được giới hạn ở 20 và số lượng chỗ ngồi đến 4 do giới hạn tiêu thụ tài nguyên trên trang web SQLFiddle và để giữ cho các tập dữ liệu kết quả có thể quan sát được.
Dưới đây là mã để thiết lập lược đồ và điền. Vui lòng xem qua các nhận xét để tìm hiểu thêm về các trường bảng.
-- 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;
Điền dữ liệu ban đầu (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
/
Tạo cuộc họp
Chiến lược bao gồm 2 phần:
1. Chọn người để cụ thể;
2. Đặt người từ danh sách từng người một vào bảng thích hợp nhất.
Sắp xếp người trong danh sách lựa chọn là cố gắng đặt những người gặp trước nhiều lần trước khi càng sớm càng tốt và đặt nó ở các bảng riêng biệt.
Việc đặt người là mục đích chính và khó khăn hơn ở giai đoạn đó là tối đa hóa số cuộc họp đầu tiên và giảm thiểu số cuộc họp lặp lại. Vì vậy, nó gần với vấn đề xây dựng các chức năng khách quan phù hợp cho vấn đề tối ưu hóa, những gì là không tầm thường trong hầu hết các trường hợp thế giới thực.
tôi chọn tiêu chí này:
Đối với mỗi bảng tính hai yếu tố: "hấp dẫn" (A) - tại sao nơi trực tiếp tại bảng đó và "thấm" (R) - tại sao người không thể ngồi trên bàn mà .
Yếu tố này bao gồm toghether để có hệ số sắp xếp bảng cuối cùng:
-A*A - (if A=0 then 0 else R/2) + R
Yếu tố "hấp dẫn" được tính là số người hiện tại không gặp trước đó.
Yếu tố "không thấm" được tính là tổng số cuộc họp của người hiện tại với tất cả những người đã có mặt tại bàn.
Rất có thể nó không tốt đến mức có thể, nhưng đủ cho các mục đích ví dụ. Ví dụ, công thức có thể được mở rộng để tính đến thời gian đã trôi qua kể từ lần họp cuối cùng.
Bạn có thể thử nghiệm với việc xây dựng biểu thức tốt để tự chọn bảng.
Tiếp theo là mã để tạo các cuộc họp.
Mã (SQLFiddle)
Một chút hơn lý thuyết
giải pháp tạo ra có thể được sử dụng như điểm khởi đầu cho một số multicriteria optimization methods, nhưng để sử dụng nó, bạn phải có một công thức chính thức tốt về vấn đề.
Hy vọng rằng tất cả các điều đã nêu ở trên sẽ giúp bạn giải quyết vấn đề.
DBMS nào? Trong MSSQL, nó có thể thực hiện được với một đệ quy CTE – Jaloopa
Xin lỗi, Microsoft Access và IBM Informix. Tôi sẽ chỉnh sửa câu hỏi của mình để bao gồm DBMS. –
@Jalopy: Nó có thể được thực hiện chỉ với ANSI SQL sao cho không quan trọng DBMS nào? –