优化比赛序列生成算法：实现选手出战间隔控制

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

优化比赛序列生成算法：实现选手出战间隔控制

2025-12-03

浏览次数：次

返回列表

优化比赛序列生成算法：实现选手出战间隔控制

本文介绍如何设计并实现一个j*ascript算法，用于生成符合特定规则的比赛序列。核心目标是确保每位选手在两次出战之间保持至少n场比赛的间隔，从而避免连续出战。我们将探讨如何管理选手的疲劳状态，并动态分配比赛场次，以构建一个平衡且符合业务逻辑的赛程表。

在体育赛事编排中，确保选手在连续比赛之间有足够的休息时间至关重要。这不仅关乎选手的身体健康，也影响比赛的公平性和观赏性。本教程将指导您如何使用J*aScript构建一个算法，以实现对比赛序列中选手出战间隔的精确控制，确保每位选手在两次出战之间至少间隔N场比赛。

问题背景与挑战

传统的比赛序列生成方法可能只是简单地按顺序分配比赛场次，导致同一选手可能连续出战。例如，在以下数据结构中，"paul"在第1场和第2场比赛中连续出战，这不符合我们的规则：

const data = [
  {"id":"1","fighter1":"paul","fighter2":"anna","fightNumber":1},
  {"id":"2","fighter1":"jack","fighter2":"paul","fightNumber":2}, // 问题：paul 连续出战
  {"id":"3","fighter1":"roger","fighter2":"law","fightNumber":3},
  // ... 其他比赛
];

我们的目标是生成一个序列，例如：

const new_result= [
  {"id":"1","fighter1":"paul","fighter2":"anna","fightNumber":1},
  {"id":"3","fighter1":"roger","fighter2":"law","fightNumber":2},
  {"id":"7","fighter1":"lee","fighter2":"jack","fightNumber":3},
  {"id":"2","fighter1":"jack","fighter2":"paul","fightNumber":4}, // paul 在第1场和第4场之间有2场间隔 (3-1=2)
  // ...
];

这意味着在"paul"的第1场比赛之后，必须有至少N场其他比赛，他才能再次出战。

现有方法分析与局限性

用户最初尝试的算法通过将比赛按选手分组，然后尝试按顺序分配比赛编号。这种方法的问题在于，它主要关注每个选手的原始比赛顺序，并试图通过微调 fightNumber 来避免冲突，但并未有效追踪和强制执行全局的选手出战间隔。结果是，间隔可能过小（1-2场）或过大（数十场），无法实现精确控制。

// 用户原有代码片段（简化）
const dataGroupedByName = data.reduce(/* ...分组逻辑... */);
let result = [];
let i = 0;
while (true) {
  let done = true;
  for (const groupName in dataGroupedByName) {
    const group = dataGroupedByName[groupName];
    if (i < group.length) {
      const newItem = { ...group[i], fightNumber: String(result.length + 1) };
      // 这里的while循环只是为了避免fightNumber重复，而非控制间隔
      while (usedFightNumbers.has(newItem.fightNumber)) {
        newItem.fightNumber = String(parseInt(newItem.fightNumber) + 0.5);
      }
      result.push(newItem);
      usedFightNumbers.add(newItem.fightNumber);
      done = false;
    }
  }
  if (done) break;
  i++;
}

此方法的问题在于，fightNumber 的分配是基于 result.length + 1，然后通过 +0.5 的方式解决冲突，这并不能保证选手间的休息间隔。它缺乏一个机制来主动检查和避免“疲劳”选手立即出战。

优化算法设计

为了解决上述问题，我们需要一个更具策略性的方法。核心思想是：在确定当前场次的比赛时，我们必须知道哪些选手在最近N场比赛中已经出战过，并将他们标记为“疲劳”状态，暂时不能安排出战。

Playground AI

AI图片生成和修图

99 查看详情 Playground AI

算法步骤：

初始化数据： 将所有比赛的 fightNumber 设置为 null，因为它们将由算法动态分配。
维护“疲劳选手”列表： 创建一个列表 tiredFightersList，用于记录每一场比赛中出战的选手。在确定第 k 场比赛时，我们将查看 tiredFightersList 中最近 gapNumber 场比赛（即 k-gapNumber 到 k-1 场）中出战过的所有选手，将他们加入当前的“疲劳选手”集合。
维护“已安排比赛”索引： 创建一个 compiledIndexes 列表，记录原始 data 数组中哪些比赛已经被安排。
循环分配比赛：
- 对于每一场新的比赛（从 fightNumber = 0 开始递增），首先根据 gapNumber 从 tiredFightersList 中提取出当前处于疲劳状态的选手。
- 从原始 data 数组中寻找一场尚未安排 (compiledIndexes 中不存在) 且其两名选手都不在当前“疲劳选手”集合中的比赛。
- 如果找到这样的比赛，将其 fighter1 和 fighter2 添加到 tiredFightersList 中当前场次的位置，并将其原始索引添加到 compiledIndexes。
- 将该比赛的 fightNumber 设置为当前场次编号。
- 如果找不到合适的比赛，则意味着在当前 gapNumber 限制下，没有符合条件的选手可以出战，此时该场比赛可能暂时为空，或者需要更复杂的调度策略。

算法实现

以下是基于上述设计思想的J*aScript实现。为了便于演示，我们结合一个简单的HTML界面来动态选择间隔数。

HTML 界面：

<label>选择选手出战的最小间隔场次：</label>
<select name="gap" id="gapNumberInput">
  <option value="1">1</option>
  <option value="2">2</option>
  <option value="3">3</option>
  <option value="4">4</option>
</select>
<br>
<button onclick="calculateFight()">生成比赛序列</button>

<br><br><br>
<p>注意：间隔数越大，符合条件的比赛组合越少，可能导致某些场次无法安排选手。</p>
<pre class="brush:php;toolbar:false;" id="output">

J*aScript 代码：

const initialData = [
  { id: "1", fighter1: "paul", fighter2: "anna", fightNumber: null },
  { id: "2", fighter1: "jack", fighter2: "paul", fightNumber: null },
  { id: "3", fighter1: "roger", fighter2: "law", fightNumber: null },
  { id: "4", fighter1: "lee", fighter2: "law", fightNumber: null },
  { id: "5", fighter1: "law", fighter2: "paul", fightNumber: null },
  { id: "6", fighter1: "roger", fighter2: "anna", fightNumber: null },
  { id: "7", fighter1: "lee", fighter2: "jack", fightNumber: null },
  { id: "8", fighter1: "roger", fighter2: "anna", fightNumber: null },
  { id: "9", fighter1: "lee", fighter2: "jack", fightNumber: null },
];

function calculateFight() {
  // 获取用户选择的间隔数
  const gapNumber = parseInt(document.getElementById("gapNumberInput").value);
  // 存储每场比赛中出战的选手，用于判断疲劳状态
  const tiredFightersList = [];
  // 存储原始数据中哪些比赛已经被安排到新的序列中
  const compiledIndexes = [];

  // 复制一份数据，避免修改原始数据
  const dataToProcess = JSON.parse(JSON.stringify(initialData));

  // 遍历并生成新的比赛序列
  const fights = dataToProcess.map((element, index) => {    
    // 计算当前场次（index）之前，需要考虑的疲劳选手范围
    // slice(-gapNumber) 获取最近的 gapNumber 场比赛的出战选手
    const recentFightsForTiredness = tiredFightersList.slice(-gapNumber);

    // 汇总最近N场比赛中所有出战过的选手，作为当前场次的“疲劳选手”
    const tiredFighters = recentFightsForTiredness.reduce((prev, currFighters) => {
      if (currFighters) { // 确保 currFighters 不为空 (例如在序列开头)
        currFighters.forEach(fighter => {
          if (fighter && !prev.includes(fighter)) { // 避免重复添加和空值
            prev.push(fighter);
          }
        });
      }
      return prev;
    }, []);

    let searchIndex = 0;
    let foundMatch = null;

    // 循环查找合适的比赛：
    // 1. 选手不在疲劳列表中
    // 2. 该比赛尚未被安排
    while (searchIndex < dataToProcess.length) {
      const currentFightCandidate = dataToProcess[searchIndex];
      // 检查当前候选比赛的选手是否疲劳，或该比赛是否已安排
      const isFighter1Tired = tiredFighters.includes(currentFightCandidate?.fighter1);
      const isFighter2Tired = tiredFighters.includes(currentFightCandidate?.fighter2);
      const isAlreadyCompiled = compiledIndexes.includes(searchIndex);

      if (currentFightCandidate && !isFighter1Tired && !isFighter2Tired && !isAlreadyCompiled) {
        foundMatch = currentFightCandidate;
        break; // 找到合适的比赛，跳出循环
      }
      searchIndex += 1;
    }

    // 记录当前场次的出战选手，并标记该比赛已被安排
    if (foundMatch) {
      tiredFightersList[index] = [foundMatch.fighter1, foundMatch.fighter2];
      compiledIndexes.push(searchIndex); // 记录原始索引
      return {
        ...foundMatch,
        fightNumber: index + 1 // 比赛编号从1开始
      };
    } else {
      // 如果没有找到合适的比赛，则该场次可能为空
      tiredFightersList[index] = []; // 记录为空，避免影响后续疲劳计算
      return {
        id: null, // 或其他标识，表示该场次未能安排比赛
        fighter1: null,
        fighter2: null,
        fightNumber: index + 1
      };
    }
  });

  document.getElementById("output").textContent = JSON.stringify(fights, null, 2);
  console.log(fights);
}

代码解析

initialData: 原始比赛数据，fightNumber 初始设为 null，等待算法分配。
gapNumber: 用户通过下拉菜单选择的最小间隔场次。
tiredFightersList: 这是一个二维数组，tiredFightersList[i] 存储了第 i 场比赛中出战的选手。它的作用是记录历史出战情况。
compiledIndexes: 存储了 initialData 数组中，哪些比赛的索引已经被选中并安排到新的序列中。这确保每场原始比赛只被安排一次。
fights = dataToProcess.map((element, index) => { ... }):
- 我们使用 map 方法来遍历并生成新的 fights 数组，index 即为当前正在安排的比赛的编号（从0开始）。
- recentFightsForTiredness = tiredFightersList.slice(-gapNumber)：获取 tiredFightersList 中最近 gapNumber 场比赛的记录。
- tiredFighters = recentFightsForTiredness.reduce(...)：将这些最近比赛中的所有选手汇总到一个 tiredFighters 集合中。这些选手在当前场次是“疲劳”的，不能出战。
- 寻找匹配的比赛 (while 循环)：
  - searchIndex 从 0 开始遍历 dataToProcess 数组。
  - currentFightCandidate 是 dataToProcess[searchIndex]。
  - 检查条件：
    - currentFightCandidate 存在。
    - currentFightCandidate.fighter1 和 currentFightCandidate.fighter2 都不在 tiredFighters 列表中。
    - searchIndex 不在 compiledIndexes 中（表示该比赛尚未被安排）。
  - 一旦找到符合条件的比赛 (foundMatch)，就跳出循环。
- 安排比赛并更新状态：
  - 如果找到了 foundMatch，则将其选手添加到 tiredFightersList[index]，并将其原始索引 searchIndex 添加到 compiledIndexes。
  - 返回一个包含新 fightNumber (index + 1) 的比赛对象。
  - 如果未找到 foundMatch，则返回一个空比赛对象，表示该场次暂时无法安排。

注意事项与总结

数据不足问题：当 gapNumber 设置较大时，如果 initialData 中的比赛数量或选手组合不够丰富，算法可能无法为所有场次找到合适的选手，导致某些 fightNumber 对应的比赛为空（fighter1: null, fighter2: null）。这是调度问题本身的限制，而非算法缺陷。
效率考虑：当前算法在每次分配比赛时，都需要遍历 dataToProcess 数组来寻找合适的比赛。对于非常庞大的数据集，这可能导致性能瓶颈。优化方向可以包括：
- 预处理 dataToProcess，例如按选手分组，以便更快地查找。
- 使用更高效的数据结构来管理 tiredFighters 和 compiledIndexes。
公平性：此算法倾向于优先安排 initialData 中靠前的、符合条件的比赛。如果需要更复杂的公平性策略（例如，确保所有选手都有大致相同的出战频率），则需要进一步的调度逻辑。
可配置性：通过 gapNumberInput，用户可以灵活调整间隔要求，使得该算法具有良好的适应性。