將人員分配到組中以使他們盡可能少地見面-有解無憂

我一直試圖解決這個問題很長一段時間沒有成功。我還沒有找到（我搜索過）可以在維基百科上幫助我的理論。

這是問題所在。

我有一組 n 名玩家（超過 7 名）我有一個需要 7 名玩家的游戲（對于那些知道的人來說是外交！），一個用于這些角色：E、F、G、I、A、R 和 T（國家在事實）

我想舉辦一場比賽（很多比賽）。

將有 n 場比賽。

(*) 每個玩家進入 7 個不同的游戲，每次扮演不同的角色

(**) 每場比賽都有 7 名不同的玩家

=> 這很容易做到。

然而，當事情變得艱難時，就是你想要限制玩家之間的互動的時候。我想要的是任何玩家最多與其他玩家互動（互動=玩同一游戲）。（換句話說，我想阻止玩家進行這樣的交易：“我在A游戲中幫助你，你在B游戲中幫助我”）

所以：

問題 1：這對哪一個 n 是可能的？（顯然至少 50 個）

問題2：如果有可能，你怎么做？

問題 3：當不可能時最小化這些互動的演算法是什么？

作為記錄，我確實在 python 中實作了一個試錯程式（使用遞回），作業得很好，但我永遠無法獲得限制為 1 的玩家之間的最大互動（無休止的計算）

謝謝你的幫助！

PS這不是功課，它是用于實際設計游戲錦標賽的:-)

uj5u.com熱心網友回復：

我做了一些涂鴉，我想；如果我理解正確，您可以執行以下操作：

28 人完成 7 個角色/7 場比賽，只與其他玩家會面一次。
如果一個人在以下游戲中的位置被分配給不同的角色，那么沒有人在他們玩的游戲中扮演相同的角色。

Python

# -*- coding: utf-8 -*-
"""
https://stackoverflow.com/questions/71143133/an-allocation-problem-of-people-into-groups-getting-them-to-meet-as-little-as-po

Created on Sat Feb 19 21:15:02 2022

@author: paddy3118

By hand to get the algo:
    0 roles, 0 people for 0 interactions
    1 role, 1 person
    2 roles, 3 people: p0 p1, p1 p2
    3 roles,   012, 134, 235 = 6 people
    4 roles,   0123, 1456, 2478, 3579 = 10 people
"""

from itertools import count


def new_person():
    yield from count()

def people_allocation(roles: int=4):
    games, new_p = [], count()
    for i in range(roles):
        game = []
        games.append(game)
        for j in range(i):
            game.append(games[j][i])
        for _ in range(i, roles):
            game.append(next(new_p))
    return games, next(new_p)

for roles in range(8):
    print(f"Roles = {roles}:")
    games, people = people_allocation(roles)
    print(f"  Takes {people} people in the following games")
    print('  ',
          ', '.join(' '.join(f"P{x}" for x in game) for game in games))

輸出

Roles = 0:
  Takes 0 people in the following games
   
Roles = 1:
  Takes 1 people in the following games
   P0
Roles = 2:
  Takes 3 people in the following games
   P0 P1, P1 P2
Roles = 3:
  Takes 6 people in the following games
   P0 P1 P2, P1 P3 P4, P2 P4 P5
Roles = 4:
  Takes 10 people in the following games
   P0 P1 P2 P3, P1 P4 P5 P6, P2 P5 P7 P8, P3 P6 P8 P9
Roles = 5:
  Takes 15 people in the following games
   P0 P1 P2 P3 P4, P1 P5 P6 P7 P8, P2 P6 P9 P10 P11, P3 P7 P10 P12 P13, P4 P8 P11 P13 P14
Roles = 6:
  Takes 21 people in the following games
   P0 P1 P2 P3 P4 P5, P1 P6 P7 P8 P9 P10, P2 P7 P11 P12 P13 P14, P3 P8 P12 P15 P16 P17, P4 P9 P13 P16 P18 P19, P5 P10 P14 P17 P19 P20
Roles = 7:
  Takes 28 people in the following games
   P0 P1 P2 P3 P4 P5 P6, P1 P7 P8 P9 P10 P11 P12, P2 P8 P13 P14 P15 P16 P17, P3 P9 P14 P18 P19 P20 P21, P4 P10 P15 P19 P22 P23 P24, P5 P11 P16 P20 P23 P25 P26, P6 P12 P17 P21 P24 P26 P27

uj5u.com熱心網友回復：

假設 n ≥ 78 左右，以下具有周期性重啟的簡單爬山演算法將回傳一個解決方案。

演算法思想是初始化游戲，其中每個玩家只扮演每個角色一次，然后將沖突的數量驅動到零（其中沖突是一個玩家在一個游戲中扮演兩個角色，或者兩個玩家多次相遇）選擇兩個隨機游戲和一個隨機角色并交換所涉及的玩家。我們每 10 ⁷步重新啟動一次，因為這在實踐中似乎效果很好。

毫無疑問，我們可以通過約束規劃做得更好。

#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>

constexpr int r = 7;

int main() {
  int n;
  std::cin >> n;
  if (n <= r * (r - 1)) {
    return EXIT_FAILURE;
  }
  std::uniform_int_distribution<int> uniform_game(0, n - 1);
  std::uniform_int_distribution<int> uniform_role(0, r - 1);
  std::random_device device;
  std::default_random_engine engine(device());
  while (true) {
    std::vector<std::array<int, r>> games(n);
    for (int i = 0; i < n; i  ) {
      for (int j = 0; j < r; j  ) {
        games[i][j] = (i   j) % n;
      }
    }
    int badness = 0;
    std::vector<std::vector<int>> pair_counts(n, std::vector<int>(n, 0));
    auto count = [&badness, &games, &pair_counts](int i, int j, int increment) {
      for (int k = 0; k < r; k  ) {
        if (k == j) continue;
        auto [a, b] = std::minmax(games[i][j], games[i][k]);
        badness -= pair_counts[a][b] > (a != b ? 2 : 0);
        pair_counts[a][b]  = increment;
        badness  = pair_counts[a][b] > (a != b ? 2 : 0);
      }
    };
    for (int i = 0; i < n; i  ) {
      for (int j = 0; j < r; j  ) {
        count(i, j, 1);
      }
    }
    for (long t = 0; t < 10000000; t  ) {
      int i1;
      int i2;
      do {
        i1 = uniform_game(engine);
        i2 = uniform_game(engine);
      } while (i1 == i2);
      int j = uniform_role(engine);
      auto swap_players = [&]() {
        count(i2, j, -2);
        count(i1, j, -2);
        std::swap(games[i1][j], games[i2][j]);
        count(i1, j, 2);
        count(i2, j, 2);
      };
      int old_badness = badness;
      swap_players();
      if (old_badness < badness) {
        swap_players();
      } else if (badness < old_badness) {
        std::cerr << badness << '\n';
      }
      if (badness <= 0) {
        for (int i = 0; i < n; i  ) {
          for (int j = 0; j < r; j  ) {
            if (j) std::cout << ' ';
            std::cout << games[i][j];
          }
          std::cout << '\n';
        }
        return EXIT_SUCCESS;
      }
    }
  }
}

樣本輸出：

21 38 61 75 77 2 22
70 31 75 7 15 59 69
28 52 29 73 59 23 40
61 45 16 65 35 15 55
12 72 44 45 46 14 10
57 1 3 38 11 6 49
20 6 7 26 0 74 18
54 73 67 58 6 55 75
73 77 63 36 3 0 45
37 57 55 28 34 43 7
17 46 36 66 16 7 48
74 9 24 22 17 73 15
36 50 4 69 28 65 6
59 62 12 32 24 20 51
38 8 59 17 10 19 39
6 53 21 70 13 71 56
55 33 49 59 5 27 36
15 71 33 54 43 18 29
60 36 8 40 71 51 67
19 49 9 34 45 53 60
41 26 73 21 72 35 19
14 64 42 15 57 63 62
44 11 23 27 9 16 21
2 7 68 9 63 52 54
35 18 2 3 60 64 17
29 17 50 41 31 61 57
47 10 32 25 75 28 35
30 48 64 6 32 39 44
46 22 71 35 20 31 11
43 76 41 11 47 60 14
56 2 1 33 74 10 37
51 41 39 0 33 70 34
32 5 18 31 23 76 68
65 43 53 8 27 46 73
63 44 26 5 70 24 28
62 75 66 71 44 3 41
16 69 54 13 22 41 5
58 19 52 57 36 22 70
42 25 22 44 55 56 76
4 30 35 51 76 13 9
72 13 17 62 40 77 43
53 16 10 68 50 58 64
64 47 70 55 38 40 20
50 59 14 48 1 9 71
40 63 19 76 69 1 12
24 35 69 56 68 57 27
67 34 15 72 56 66 32
68 3 46 37 25 21 59
77 54 47 19 4 44 31
76 67 38 46 52 50 33
25 15 77 1 51 26 23
3 61 40 4 53 5 74
45 51 74 29 48 68 47
75 0 57 23 30 8 72
13 27 28 14 19 67 2
9 20 72 42 65 33 3
49 58 48 20 41 37 77
22 12 37 67 39 47 53
26 42 11 61 37 36 13
1 60 5 39 29 75 46
48 40 65 10 54 34 26
23 66 60 50 42 54 24
8 74 13 63 49 32 50
27 29 58 12 7 38 42
7 4 45 24 64 25 8
71 24 30 47 2 49 16
31 28 56 60 12 48 0
10 23 62 49 67 69 61
34 21 31 30 58 62 1
66 70 27 18 61 30 25
0 37 76 64 66 29 65
69 39 43 2 26 45 58
39 65 25 74 62 11 52
5 56 20 52 14 17 30
33 68 6 77 8 12 66
11 55 51 53 18 72 63
52 32 0 43 21 42 4
18 14 34 16 73 4 38

uj5u.com熱心網友回復：

最終我想我解決了這個問題。我在這里解釋它以幫助任何其他面臨此類問題的人。

我使用了兩種“經典”演算法。

嘗試和錯誤以獲得低質量的第一個配置，迭代首先嘗試那些具有最少干擾并且已經在更多游戲中的玩家
爬山以提高配置質量（在沖突和不沖突的玩家之間進行交換，或者如果所有玩家都沖突，則在兩個沖突的玩家之間進行交換）并隨機選擇，僅在提高質量時才保留交換結果 - 質量是最差的沖突數量（2通常）和出現次數）

我得出以下結論：

總是高于 100 的解決方案
從來沒有低于 90 的解決方案

感謝您提供的所有支持！

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/435889.html

標籤：算法 recursion math theory np

上一篇：p5.j??s如何正確計算點相對于原點的3D旋轉

下一篇：在畫廊幻燈片中隱藏額外的影像