使用贪婪方法和船舶最大堆找到最佳路径

Question

我目前正在开发一个 TypeScript 程序，以找到从起点到达岛屿的最快路径。我希望得到一些帮助。以下是我正在使用的参数：

interface Boat {
  autonomy: number;      // the Autonomy of my boat
  departure: string;     // starting island
  arrival: string;       // Island I want to reach
  routes: Record<string, { island: string; travelTime: number }[]>;
}

路线对象表示岛屿之间的链接以及到达它们所需的时间。例如：

 routes: {
    Island1: [
      { island: "Island2", travelTime: 3 },
      { island: "Island3", travelTime: 2 },
    ],

另外，我还有盗版数据相关的参数：

 interface PirateData {
  countdown: number;   // Maximum time I have to reach the desired island 
  pirates: { island: string; day: number }[];   
}

海盗属性表示海盗的行踪以及他们出现在特定岛屿上的日期。例如：

例如：

pirates : [ island: "Island2", day : 3]

我需要考虑到这样一个事实：与海盗共度每一天都会使任务的成功率降低一定的百分比（例如 10%）。而且，在同一个岛上度过的每一天都让我获得一天的自主权。例如，如果我从 4 天的自主权开始，前往 Island3，并在那里停留 1 天，我当前的自主权变为 4 - 2 + 1。

我的目标是找到到达目的地的最佳路径。 我发现与经典的 A* 算法相比，使用贪婪方法和最大堆应该有助于加快算法速度。 我的目标是找到最快的算法来解决这个问题

我在代码上取得了进展，但算法的某些部分没有按预期工作，我正在努力找出问题。我将非常感谢任何帮助完成此代码的帮助。

我想使用“ts-priority-queue”来创建我的队列。

我尝试做这样的事情：

function findOptimalPath(
  start: GraphNode,
  end: GraphNode,
  shipAutonomy: number,
  boatData: Boat
): GraphNode[] | null {
  const queue = new PriorityQueue<{
    node: GraphNode;
    remainingAutonomy: number;
    path: GraphNode[];
    totalTravelTime: number;
  }>({
    comparator: (a, b) => a.totalTravelTime - b.totalTravelTime, // Min heap based on total travel time
  });

  const visited = new Set<GraphNode>();

  queue.queue({
    node: start,
    remainingAutonomy: shipAutonomy,
    path: [start],
    totalTravelTime: 0,
  });

  while (!queue.isEmpty()) {
    const { node, remainingAutonomy, path, totalTravelTime } = queue.dequeue();

    if (node === end) {
      return path;
    }

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    for (const { neighbor, travelTime } of node.neighbors) {
      const newAutonomy = remainingAutonomy - travelTime;

      if (!visited.has(neighbor) && newAutonomy >= 0) {
        queue.queue({
          node: neighbor,
          remainingAutonomy: newAutonomy,
          path: [...path, neighbor],
          totalTravelTime: totalTravelTime + travelTime,
        });
      }
    }
  }

  return null; // No path found
}

Answer 1

该算法 https://www.geeksforgeeks.org/minimize-refills-to-reach-end-of-path/amp/ 仅在您知道到达目的地的路径及其长度后才适用。

这是我建议的算法：

1. 使用 Dijkstra 找到到达目的地的最快路径。它比 A* 更快，并且您可以在这一步忽略燃料和海盗。

2. 使用极客算法优化加油站

3. 检查是否与海盗发生碰撞。如果发生碰撞，您将不得不尝试替代稍微不太理想的路径来避开海盗。 Yen 的算法对此很有帮助。 https://en.wikipedia.org/wiki/Yen%27s_algorithm