本教程详细讲解如何使用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开始递增) 寻找一个合适的未使用的比赛，该比赛的两位选手当前都不是疲劳状态。
具体步骤如下：
- 初始化： 维护一个列表，记录每一场已分配 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，算法能够迭代地为每场比赛找到符合条件的选手组合，从而避免选手连续出战。尽管该算法在数据不足时可能产生空比赛场次，但它提供了一个灵活且可配置的解决方案，适用于需要考虑选手休息期的赛事管理场景。开发者可以根据实际需求，在此基础上进行扩展，例如增加更复杂的优化策略或选手优先级规则。
