JavaScript实现带有间隔约束的赛事调度算法教程-js教程-PHP中文网

JavaScript实现带有间隔约束的赛事调度算法教程

本教程详细讲解如何使用javascript实现一个智能赛事调度算法，确保选手在连续参赛之间保持设定的休息间隔。通过引入“疲劳选手”机制和迭代查找可用赛事的方法，该算法能有效避免选手连续出战，并允许灵活配置休息场次。文章将深入解析代码实现，并探讨其应用场景及潜在局限。

理解赛事调度中的间隔约束

在许多竞技或娱乐赛事中，为了保证公平性、选手健康或观赏性，通常需要为选手设定一定的休息间隔，避免其连续出战。例如，在拳击比赛中，一位选手在完成一场比赛后，可能需要休息3-4场比赛才能再次登场。

传统的顺序分配 fightNumber 的方法，如简单地按照原始数据顺序或分组后顺序分配，往往无法满足这种间隔约束。这可能导致同一选手在极短的 fightNumber 间隔内多次出战，或者由于复杂的分配逻辑导致间隔过大，使得调度效率低下。

我们的目标是设计一个算法，能够根据预设的“休息场次间隔” (gapNumber)，为一系列潜在的比赛分配 fightNumber，确保任何选手在两次出战之间至少有 gapNumber 场比赛的休息时间。

考虑以下原始比赛数据结构，其中 fightNumber 初始时可以视为待分配：

立即学习“Java免费学习笔记（深入）”；

const data = [
  { 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 },
];

登录后复制

期望的输出结果是 fightNumber 重新排序，并满足间隔约束，例如：

const new_result= [
  {"id":"1","fighter1":"paul","fighter2":"anna","fightNumber":0}, // 示例中从0开始，与目标输出的1对应
  {"id":"3","fighter1":"roger","fighter2":"law","fightNumber":1},
  {"id":"7","fighter1":"lee","fighter2":"jack","fightNumber":2},
  {"id":"2","fighter1":"jack","fighter2":"paul","fightNumber":3}, // paul在此处再次出战，与fightNumber 0之间有2场比赛的间隔
  // ... 其他比赛
];

登录后复制

核心调度算法设计

为了实现间隔约束，我们引入“疲劳选手”的概念。当一名选手参加完一场比赛后，他会在接下来的 gapNumber 场比赛中被视为“疲劳”状态，不能再次出战。算法的核心思想是迭代地为每一场比赛 (fightNumber 从0开始递增) 寻找一个合适的未使用的比赛，该比赛的两位选手当前都不是疲劳状态。

Dreamina

字节跳动推出的AI绘画工具，用简单的文案创作精美的图片

436

查看详情

具体步骤如下：

初始化： 维护一个列表，记录每一场已分配 fightNumber 的比赛所涉及的选手，以及一个集合，记录哪些原始比赛已被使用。
迭代分配： 从 fightNumber = 0 开始，依次为每场比赛进行分配。
识别疲劳选手： 对于当前的 fightNumber，根据 gapNumber 查找最近 gapNumber 场已分配比赛中涉及的所有选手，将他们标记为“疲劳选手”。
寻找可用比赛： 遍历原始的比赛列表，寻找第一个满足以下条件的比赛：
- 该比赛尚未被分配。
- 该比赛的两位选手都不在当前的“疲劳选手”列表中。
分配与更新：
- 如果找到符合条件的比赛，将其分配给当前的 fightNumber。
- 将该比赛的选手记录下来，以便在未来的迭代中识别疲劳选手。
- 将该原始比赛标记为已使用。
- 如果未找到符合条件的比赛，则当前 fightNumber 对应的比赛将为空（表示无法安排）。

实现细节与代码解析

下面是实现上述算法的JavaScript代码，并结合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="calculatreFight()">计算调度</button>

<br><br><br>
<p>请注意，休息间隔越大，可能找到的解决方案越少，从而导致某些场次无法安排选手。</p>
<pre id="output"></pre> <!-- 用于显示结果 -->

登录后复制

JavaScript 代码:

const data = [
  { 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 calculatreFight() {
  // 获取用户选择的休息间隔
  const gapNumber = parseInt(document.getElementById("gapNumberInput").value);

  // tiredFightersList: 存储每场比赛的选手，用于判断哪些选手当前是疲劳的
  // 结构如：[[fighter1_0, fighter2_0], [fighter1_1, fighter2_1], ...]
  const tiredFightersList = []; 

  // compiledIndexes: 存储原始data数组中已被使用的比赛的索引
  const compiledIndexes = []; 

  // 使用 map 方法迭代，为每一场比赛 (fightNumber 从 0 到 data.length - 1) 进行调度
  const scheduledFights = data.map((_, index) => {    
    // 计算当前“疲劳”的选手列表
    // slice(-gapNumber) 获取最近的 gapNumber 场比赛的选手数据
    // reduce 扁平化数组并去重，得到所有疲劳选手
    const tiredFighters = tiredFightersList.slice(-gapNumber).reduce((prev, curr) => {
      // 确保 curr 存在且是数组，处理可能为空的情况
      if (curr) {
          curr.forEach(fighter => {
              if (fighter && !prev.includes(fighter)) {
                  prev.push(fighter);
              }
          });
      }
      return prev;
    }, []);

    let searchIndex = 0; // 用于在原始 data 数组中查找可用比赛的索引
    // 循环查找符合条件的比赛：
    // 1. 比赛的 fighter1 或 fighter2 不能是疲劳选手
    // 2. 该比赛不能已经被调度过 (compiledIndexes.includes(searchIndex))
    while (searchIndex < data.length && (
           tiredFighters.includes(data[searchIndex]?.fighter1) ||
           tiredFighters.includes(data[searchIndex]?.fighter2) ||
           compiledIndexes.includes(searchIndex)
    )) {
      searchIndex += 1;
    }

    let currentFight = null;
    if (searchIndex < data.length) {
      // 找到可用比赛，记录其选手和索引
      currentFight = data[searchIndex];
      tiredFightersList[index] = [currentFight.fighter1, currentFight.fighter2];
      compiledIndexes.push(searchIndex);
    } else {
      // 未找到可用比赛，当前场次为空，但仍需在 tiredFightersList 中占位，防止后续计算出错
      tiredFightersList[index] = [null, null]; 
    }

    // 返回调度后的比赛对象
    return {
      ...currentFight, // 如果 currentFight 为 null，这里会是空对象
      fightNumber: index // 赋予当前的 fightNumber
    };
  });

  // 将结果输出到页面
  document.getElementById("output").textContent = JSON.stringify(scheduledFights, null, 2);
}

登录后复制

代码解析：

data 数组： 初始数据，fightNumber 设置为 null，表示这些是待分配的比赛。
calculatreFight() 函数：
- gapNumber： 从页面 select 元素获取用户设定的休息间隔。
- tiredFightersList： 这是一个关键数据结构。它是一个二维数组，tiredFightersList[i] 存储了 fightNumber 为 i 的比赛中的两位选手。这样，我们就可以通过 slice(-gapNumber) 轻松获取最近 gapNumber 场比赛的所有选手，从而判断哪些选手是“疲劳”的。
- compiledIndexes： 记录 data 数组中哪些原始比赛已经被分配了 fightNumber。使用数组存储索引，避免重复使用。
- data.map((_, index) => { ... })： 这是一个迭代过程，index 从 0 递增到 data.length - 1，它代表了我们正在为第 index 场比赛 (fightNumber: index) 寻找匹配。
  - tiredFighters 计算： tiredFightersList.slice(-gapNumber) 截取 tiredFightersList 的最后 gapNumber 个元素（即最近 gapNumber 场比赛的选手信息）。然后通过 reduce 方法将这些选手扁平化并去重，得到当前所有疲劳选手的列表。
  - while 循环查找： searchIndex 从 0 开始遍历原始 data 数组。while 循环的条件判断当前 data[searchIndex] 是否可用：
    - tiredFighters.includes(...)：检查比赛的两位选手是否在疲劳列表中。
    - compiledIndexes.includes(searchIndex)：检查该原始比赛是否已被调度。
    - 如果任何条件为真，则 searchIndex 递增，继续查找下一个原始比赛。
  - 分配比赛：
    - 如果 searchIndex < data.length，说明找到了一个可用的原始比赛 (data[searchIndex])。
    - 将该比赛的选手添加到 tiredFightersList[index] 中，以便后续计算。
    - 将 searchIndex 添加到 compiledIndexes 中，标记该原始比赛已使用。
    - 构建并返回包含新 fightNumber 的比赛对象。
    - 如果 searchIndex >= data.length，表示在原始 data 中找不到符合条件的比赛。此时，currentFight 将保持为 null，返回的对象中 fighter1 和 fighter2 将为 null，fightNumber 仍然是 index。tiredFightersList[index] 也会被设置为 [null, null] 以保持数组长度和索引的对应关系。

注意事项与局限性

数据耗尽与空比赛： 当 gapNumber 设置得较大，或者原始比赛数据中的选手种类和数量不足以支撑调度时，算法可能无法为某些 fightNumber 找到合适的比赛。在这种情况下，输出结果中会包含 fighter1 和 fighter2 为 null 的比赛条目，这表示该场次未能成功安排比赛。用户界面中的提示信息强调了这一点。
贪婪算法特性： 该算法采用了一种贪婪策略，即在每个 fightNumber 迭代时，它会选择在原始 data 数组中找到的第一个符合条件的比赛。这种方法简单有效，但在某些复杂场景下，可能不是最优的（例如，如果存在多种选择，选择不同的比赛可能导致后续的调度更容易或更困难）。
原始 fightNumber 的作用： 在本算法中，原始 data 数组中的 fightNumber 字段被完全忽略，并被视为待分配。算法会从 0 开始重新分配 fightNumber。
可配置性： 通过 gapNumberInput 元素，用户可以灵活地调整休息间隔，观察不同间隔对调度结果的影响。

总结

本教程介绍了一种基于“疲劳选手”机制的JavaScript赛事调度算法，能够有效地在分配比赛 fightNumber 时强制执行选手休息间隔。通过维护 tiredFightersList 和 compiledIndexes，算法能够迭代地为每场比赛找到符合条件的选手组合，从而避免选手连续出战。尽管该算法在数据不足时可能产生空比赛场次，但它提供了一个灵活且可配置的解决方案，适用于需要考虑选手休息期的赛事管理场景。开发者可以根据实际需求，在此基础上进行扩展，例如增加更复杂的优化策略或选手优先级规则。

以上就是JavaScript实现带有间隔约束的赛事调度算法教程的详细内容，更多请关注php中文网其它相关文章！