优化治疗师日程：如何将空时段调整至当日末尾？

一、调整现有递归方法避免循环 #

你的递归思路核心方向正确，但缺少循环检测和状态回溯机制，导致出现预约反复交换的死循环问题。可以通过以下两点修改解决：

1. 加入已访问时段集合防止循环 #

在递归函数中传入一个集合，记录已经处理过的空时段。如果当前要填充的时段已在集合中，说明进入循环，直接返回失败。

2. 增加回溯逻辑恢复状态 #

当递归尝试移动预约后失败，需要将预约时间恢复到原始状态，避免破坏后续的尝试流程。

修改后的代码示例：

emptySlots.forEach((emptySlot: ValidTime) => {
  const swapAppts = (slotToFill: ValidTime, visitedSlots: Set<ValidTime> = new Set()): boolean => { 
    // 成功基准：空时段已移至当日末尾
    if (slotToFill === lastSlot) return true;
    // 循环检测：该时段已处理过，直接返回失败
    if (visitedSlots.has(slotToFill)) return false;
    visitedSlots.add(slotToFill);

    for (let i = 0; i < apptsLastToFirst.length; i++) {
      const appointment = apptsLastToFirst[i];
      // 检查患者在目标时段是否可用
      if (availability[slotToFill].patients[appointment.patient]) {
        const originalTime = appointment.time;
        // 尝试移动预约到空时段
        appointment.time = slotToFill;
        // 重新排序保持数组从晚到早的顺序
        apptsLastToFirst.sort((a, b) => b.time.localeCompare(a.time));
        
        // 递归处理新的空时段，传入新集合避免污染上层状态
        const success = swapAppts(originalTime, new Set(visitedSlots));
        if (success) {
          return true;
        } else {
          // 回溯：恢复预约的原始时间
          appointment.time = originalTime;
          apptsLastToFirst.sort((a, b) => b.time.localeCompare(a.time));
        }
      }
    }
    return false;
  };

  if (swapAppts(emptySlot)) {
    // 更新状态为优化后的预约安排
    // updateState(apptsLastToFirst);
  }
});

二、更优的算法思路：BFS广度优先搜索 #

由于每日仅8个时段，状态空间极小，用BFS替代递归可以更高效地找到可行路径，且天然避免循环问题。

算法逻辑 #

将空时段的位置看作状态，每个状态可通过移动符合条件的预约转换为新状态：

1. 初始化队列，存入初始状态（当前空时段+预约列表副本）
2. 用集合记录已处理过的状态，避免重复操作
3. 每次从队列取出状态，尝试所有能移到当前空时段的预约：
   • 生成新的预约列表（将该预约移动到空时段）
   • 新状态的空时段为原预约的时间
   • 如果新状态的空时段是当日最后一个时段，直接返回该预约列表
   • 如果新状态未被处理过，加入队列和已处理集合

代码示例（简化版） #

interface ScheduleState {
  emptySlot: ValidTime;
  appointments: Appointment[];
}

function moveEmptySlotToEnd(initialEmptySlot: ValidTime, initialAppts: Appointment[], lastSlot: ValidTime, availability: any): Appointment[] | null {
  const queue: ScheduleState[] = [{
    emptySlot: initialEmptySlot,
    appointments: JSON.parse(JSON.stringify(initialAppts)) // 深拷贝避免修改原数据
  }];
  const visited = new Set<string>();
  // 用空时段+预约时间的哈希值作为状态标识
  const getStateKey = (state: ScheduleState) => {
    return `${state.emptySlot}-${state.appointments.map(a => a.time).join(',')}`;
  };

  while (queue.length > 0) {
    const currentState = queue.shift()!;
    const stateKey = getStateKey(currentState);
    
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);

    // 成功条件：空时段已移至末尾
    if (currentState.emptySlot === lastSlot) {
      return currentState.appointments;
    }

    // 尝试所有可移动的预约
    for (let i = 0; i < currentState.appointments.length; i++) {
      const appt = currentState.appointments[i];
      if (availability[currentState.emptySlot].patients[appt.patient]) {
        // 生成新的预约列表
        const newAppointments = [...currentState.appointments];
        const newAppt = {...newAppointments[i]};
        const originalTime = newAppt.time;
        newAppt.time = currentState.emptySlot;
        newAppointments[i] = newAppt;
        // 排序保持从晚到早的顺序（可选，不影响核心逻辑）
        newAppointments.sort((a, b) => b.time.localeCompare(a.time));

        const newState: ScheduleState = {
          emptySlot: originalTime,
          appointments: newAppointments
        };
        queue.push(newState);
      }
    }
  }
  // 无可行优化路径
  return null;
}

// 使用示例
emptySlots.forEach(emptySlot => {
  const optimizedAppts = moveEmptySlotToEnd(emptySlot, apptsLastToFirst, lastSlot, availability);
  if (optimizedAppts) {
    // 更新状态为优化后的预约安排
    // updateState(optimizedAppts);
  }
});

为什么BFS更优？ #

• 天然避免循环：通过visited集合记录所有处理过的状态，不会重复处理同一状态
• 最短路径优先：BFS按层级遍历，第一个到达目标状态的路径就是最少移动次数的方案
• 逻辑清晰：状态转换过程可视化，便于调试和维护

内容的提问来源于stack exchange，提问作者voidfroze