基于贪心算法与最大堆的游戏船只最优路径求解技术问询

你的问题本质是三维状态空间下的多目标路径规划（需同时优化到达时间、任务成功率，满足燃料、倒计时约束），普通Dijkstra/Bellman-Ford无法适配是因为它们只考虑单一节点状态，而你的问题需要追踪「当前岛屿+当前天数+当前燃料」三个维度的状态。下面是具体的算法选型和实现思路：

核心算法：改进版Dijkstra（带优先级队列） #

由于所有操作的时间消耗、燃料消耗都是非负值，Dijkstra算法的贪心特性依然适用，但需要扩展状态维度，并重新定义优先级规则。

1. 状态定义 #

每个节点状态为三元组：

(currentIsland: string, currentDay: number, currentFuel: number)

同时记录该状态下的任务成功率和路径轨迹，用于后续筛选最优解。

2. 优先级规则 #

优先级队列（最大堆）的排序依据需同时满足：

• 到达时间越早（currentDay越小）越优先
• 任务成功率越高越优先

可以用组合值作为优先级：优先级 = (-currentDay) * 100 + successRate，确保更早到达且成功率高的状态被优先处理。

3. 状态转移逻辑 #

（1）航行转移

从当前岛屿出发，遍历所有可达岛屿：

• 检查当前燃料是否≥航线的travelTime（航行耗时=燃料消耗）
• 到达后，currentDay += travelTime，currentFuel -= travelTime，成功率不变（航行过程不会遇到海盗）
• 若到达目标岛屿且currentDay ≤ countdown，记录为候选解

（2）停留转移

在当前岛屿停留1天：

• currentDay += 1，currentFuel = min(初始燃料, currentFuel + 1)（燃料不超过船只初始上限）
• 检查停留当天该岛屿是否有海盗：若有，成功率按比例降低（如乘以0.9）
• 停留天数不能超过countdown

4. 状态剪枝 #

为避免无效计算，维护一个状态缓存visited，键为${currentIsland}-${currentDay}-${currentFuel}，值为该状态下的最高成功率：

• 若新状态的成功率≤缓存中记录的最高值，直接跳过
• 若currentDay > countdown，直接丢弃该状态

TypeScript核心实现示例 #

// 预处理海盗数据：岛屿→出现天数集合，快速查询
const pirateMap: Record<string, Set<number>> = {};
pirates.forEach(p => {
  if (!pirateMap[p.island]) pirateMap[p.island] = new Set();
  pirateMap[p.island].add(p.day);
});

// 优先级队列元素类型
interface QueueItem {
  priority: number; // 负数天数+成功率，越大越优先
  island: string;
  day: number;
  fuel: number;
  successRate: number;
  path: string[];
}

// 初始化队列：出发岛屿，第0天，初始燃料，100%成功率
const queue: QueueItem[] = [{
  priority: 0 * (-1) + 100,
  island: boat.departure,
  day: 0,
  fuel: boat.fuel,
  successRate: 100,
  path: [boat.departure]
}];

// 状态缓存：记录每个(岛屿-天数-燃料)的最高成功率
const visited: Record<string, number> = {};
let bestSolution: { path: string[], successRate: number, day: number } | null = null;

// 注意：实际项目请用真正的最大堆实现，避免每次sort的性能损耗
while (queue.length > 0) {
  // 取出优先级最高的状态
  queue.sort((a, b) => b.priority - a.priority);
  const current = queue.shift()!;

  // 到达目标岛屿，更新最优解
  if (current.island === boat.arrival) {
    if (current.day <= countdown) {
      if (!bestSolution || 
          current.successRate > bestSolution.successRate || 
          (current.successRate === bestSolution.successRate && current.day < bestSolution.day)) {
        bestSolution = {
          path: current.path,
          successRate: current.successRate,
          day: current.day
        };
      }
    }
    continue;
  }

  // 超过时限，跳过
  if (current.day > countdown) continue;

  // 状态已存在更优解，跳过
  const stateKey = `${current.island}-${current.day}-${current.fuel}`;
  if (visited[stateKey] && visited[stateKey] >= current.successRate) continue;
  visited[stateKey] = current.successRate;

  // 处理航行转移
  const adjacentIslands = routesData.routes[current.island] || [];
  for (const route of adjacentIslands) {
    const { island: nextIsland, travelTime } = route;
    if (current.fuel >= travelTime) {
      const nextDay = current.day + travelTime;
      if (nextDay > countdown) continue;
      const nextFuel = current.fuel - travelTime;
      const nextSuccessRate = current.successRate;
      const nextPath = [...current.path, nextIsland];
      const nextPriority = (-nextDay) * 100 + nextSuccessRate;

      const nextStateKey = `${nextIsland}-${nextDay}-${nextFuel}`;
      if (!visited[nextStateKey] || nextSuccessRate > visited[nextStateKey]) {
        queue.push({ priority: nextPriority, island: nextIsland, day: nextDay, fuel: nextFuel, successRate: nextSuccessRate, path: nextPath });
      }
    }
  }

  // 处理停留转移
  const nextDay = current.day + 1;
  if (nextDay > countdown) continue;
  const nextFuel = Math.min(boat.fuel, current.fuel + 1);
  let nextSuccessRate = current.successRate;
  if (pirateMap[current.island]?.has(nextDay)) {
    nextSuccessRate *= 0.9;
    nextSuccessRate = Math.round(nextSuccessRate * 100) / 100; // 保留两位小数
  }
  const nextPath = [...current.path, `${current.island}(停留1天)`];
  const nextPriority = (-nextDay) * 100 + nextSuccessRate;

  const nextStateKey = `${current.island}-${nextDay}-${nextFuel}`;
  if (!visited[nextStateKey] || nextSuccessRate > visited[nextStateKey]) {
    queue.push({ priority: nextPriority, island: current.island, day: nextDay, fuel: nextFuel, successRate: nextSuccessRate, path: nextPath });
  }
}

// 输出结果
if (bestSolution) {
  console.log(`最优路径：${bestSolution.path.join(" -> ")}`);
  console.log(`到达天数：${bestSolution.day}`);
  console.log(`任务成功率：${bestSolution.successRate}%`);
} else {
  console.log("无符合时限要求的可行路径");
}

优化建议 #

1. 堆结构优化：不要用sort模拟堆，自己实现或使用成熟的堆库，提升大场景下的性能。
2. 多目标权重调整：若游戏需要更侧重时间或成功率，可修改优先级公式中的权重（如把(-currentDay)*100改为(-currentDay)*200，增加时间的优先级）。
3. 回溯逻辑支持：若需要允许回溯到前一岛屿，只需确保航线是双向的（邻接表中互相添加），算法会自动处理回溯状态。

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