A* 탐색

언어를 고르면 코드가 열린다

import heapq


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


def a_star(start, goal, w):
    steps = {start: 0}
    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):
            step = steps[cell] + 1
            if step < steps.get(other, float('inf')):
                steps[other] = step
                prev[other] = cell
                heapq.heappush(heap, (step + 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 aStar(start, goal, w) {
  const steps = new Map([[start, 0]]);
  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)) {
      const step = steps.get(cell) + 1;
      if (step >= (steps.get(other) ?? Infinity)) continue;
      steps.set(other, step);
      prev.set(other, cell);
      heap.push(other, step + manhattan(other, goal, w));
    }
  }
  return [];
}

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

int a_star(int start, int goal, int w, int prev[], int steps[], int n,
           MinHeap* heap) {
    for (int i = 0; i < n; i++) { steps[i] = INT_MAX; prev[i] = -2; }
    steps[start] = 0;
    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) continue;
            int step = steps[cell] + 1;
            if (step >= steps[other]) continue;
            steps[other] = step;
            prev[other] = cell;
            heap_push(heap, other, step + 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> a_star(int start, int goal, int w) {
    std::unordered_map<int, int> steps{{start, 0}};
    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)) {
            int step = steps[cell] + 1;
            auto found = steps.find(other);
            if (found != steps.end() && step >= found->second) continue;
            steps[other] = step;
            prev[other] = cell;
            heap.push({step + 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> AStar(int start, int goal, int w) {
    var steps = new Dictionary<int, int> { [start] = 0 };
    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)) {
            int step = steps[cell] + 1;
            if (steps.TryGetValue(other, out int known) && step >= known) {
                continue;
            }
            steps[other] = step;
            prev[other] = cell;
            heap.Enqueue(other, step + 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> aStar(int start, int goal, int w) {
    Map<Integer, Integer> steps = new HashMap<>();
    Map<Integer, Integer> prev = new HashMap<>();
    steps.put(start, 0);
    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)) {
            int step = steps.get(cell) + 1;
            if (step >= steps.getOrDefault(other, Integer.MAX_VALUE)) continue;
            steps.put(other, step);
            prev.put(other, cell);
            heap.add(new int[] {other, step + manhattan(other, goal, w)});
        }
    }
    return List.of();
}