贪心最佳优先

选一种语言就能看到代码

import heapq


def manhattan(cell, goal, w):
    return abs(cell % w - goal % w) + abs(cell // w - goal // w)


def greedy_best_first(start, goal, w):
    prev = {start: -1}
    heap = [(manhattan(start, goal, w), start)]
    while heap:
        _, cell = heapq.heappop(heap)
        if cell == goal:
            return path_to(prev, goal)
        for other in neighbors(cell):
            if other not in prev:
                prev[other] = cell
                heapq.heappush(heap, (manhattan(other, goal, w), other))
    return []

function manhattan(cell, goal, w) {
  const dx = Math.abs((cell % w) - (goal % w));
  const dy = Math.abs(Math.floor(cell / w) - Math.floor(goal / w));
  return dx + dy;
}

function greedyBestFirst(start, goal, w) {
  const prev = new Map([[start, -1]]);
  const heap = new MinHeap();
  heap.push(start, manhattan(start, goal, w));
  while (heap.size > 0) {
    const [cell] = heap.pop();
    if (cell === goal) return pathTo(prev, goal);
    for (const other of neighbors(cell)) {
      if (prev.has(other)) continue;
      prev.set(other, cell);
      heap.push(other, manhattan(other, goal, w));
    }
  }
  return [];
}

static int manhattan(int cell, int goal, int w) {
    return abs(cell % w - goal % w) + abs(cell / w - goal / w);
}

int greedy_best_first(int start, int goal, int w, int prev[], int n,
                      MinHeap* heap) {
    for (int i = 0; i < n; i++) prev[i] = -2;
    prev[start] = -1;
    heap_push(heap, start, manhattan(start, goal, w));
    while (heap->size > 0) {
        int cell = heap_pop(heap);
        if (cell == goal) return 1;
        for (int d = 0; d < 4; d++) {
            int other = neighbor(cell, d);
            if (other < 0 || prev[other] != -2) continue;
            prev[other] = cell;
            heap_push(heap, other, manhattan(other, goal, w));
        }
    }
    return 0;
}

static int manhattan(int cell, int goal, int w) {
    return std::abs(cell % w - goal % w) + std::abs(cell / w - goal / w);
}

std::vector<int> greedy_best_first(int start, int goal, int w) {
    std::unordered_map<int, int> prev{{start, -1}};
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<>> heap;
    heap.push({manhattan(start, goal, w), start});
    while (!heap.empty()) {
        int cell = heap.top().second;
        heap.pop();
        if (cell == goal) return path_to(prev, goal);
        for (int other : neighbors(cell)) {
            if (prev.count(other) > 0) continue;
            prev[other] = cell;
            heap.push({manhattan(other, goal, w), other});
        }
    }
    return {};
}

static int Manhattan(int cell, int goal, int w) {
    return Math.Abs(cell % w - goal % w) + Math.Abs(cell / w - goal / w);
}

static List<int> GreedyBestFirst(int start, int goal, int w) {
    var prev = new Dictionary<int, int> { [start] = -1 };
    var heap = new PriorityQueue<int, int>();
    heap.Enqueue(start, Manhattan(start, goal, w));
    while (heap.Count > 0) {
        int cell = heap.Dequeue();
        if (cell == goal) return PathTo(prev, goal);
        foreach (int other in Neighbors(cell)) {
            if (prev.ContainsKey(other)) continue;
            prev[other] = cell;
            heap.Enqueue(other, Manhattan(other, goal, w));
        }
    }
    return new List<int>();
}

static int manhattan(int cell, int goal, int w) {
    return Math.abs(cell % w - goal % w) + Math.abs(cell / w - goal / w);
}

static List<Integer> greedyBestFirst(int start, int goal, int w) {
    Map<Integer, Integer> prev = new HashMap<>();
    prev.put(start, -1);
    PriorityQueue<int[]> heap =
        new PriorityQueue<>(Comparator.comparingInt(entry -> entry[1]));
    heap.add(new int[] {start, manhattan(start, goal, w)});
    while (!heap.isEmpty()) {
        int cell = heap.poll()[0];
        if (cell == goal) return pathTo(prev, goal);
        for (int other : neighbors(cell)) {
            if (prev.containsKey(other)) continue;
            prev.put(other, cell);
            heap.add(new int[] {other, manhattan(other, goal, w)});
        }
    }
    return List.of();
}