CSA Heuristics

Heuristics

Popcorn Hack 1:

• Its not weighted and the nodes are the positions where the mouse has to choose to move to. Popcorn Hack 2:
• Use the A* algorithm

Hw

1: D

2: B

3: A* is able to find the shortest path while abiding to known limitations

4: ∣2−7∣+∣3−1∣=5+2=7

5:

import java.util.*;

static class Node implements Comparable<Node> {
    int x, y;
    int costFromStart;
    int estimatedTotalCost;  // For A*
    Node parent;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.costFromStart = Integer.MAX_VALUE;
        this.estimatedTotalCost = Integer.MAX_VALUE;
        this.parent = null;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.estimatedTotalCost, other.estimatedTotalCost);
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Node)) return false;
        Node other = (Node) o;
        return this.x == other.x && this.y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

// Directions: up, down, left, right
private static final int[][] DIRECTIONS = // replace with directions

public static List<Node> dijkstra(int[][] grid, Node start, Node goal) {
    PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(n -> n.costFromStart));
    Map<String, Node> allNodes = new HashMap<>();

    start.costFromStart = 0;
    openSet.add(start);
    allNodes.put(key(start.x, start.y), start);

    while (!openSet.isEmpty()) {
        Node current = openSet.poll();

        if (current.x == goal.x && current.y == goal.y) {
            return reconstructPath(current);
        }

        for (int[] dir : DIRECTIONS) {
            int nx = current.x + dir[0];
            int ny = current.y + dir[1];
            if (!isValid(grid, nx, ny)) continue;

            Node neighbor = allNodes.getOrDefault(key(nx, ny), new Node(nx, ny));
            int newCost = current.costFromStart + 1;

            if (newCost < neighbor.costFromStart) {
                neighbor.costFromStart = newCost;
                neighbor.parent = current;
                allNodes.put(key(nx, ny), neighbor);
                openSet.remove(neighbor);
                openSet.add(neighbor);
            }
        }
    }

    return null; // no path found
}

public static List<Node> aStar(int[][] grid, Node start, Node goal) {
    PriorityQueue<Node> openSet = new PriorityQueue<>();
    Map<String, Node> allNodes = new HashMap<>();

    start.costFromStart = 0;
    start.estimatedTotalCost = heuristic(start, goal);
    openSet.add(start);
    allNodes.put(key(start.x, start.y), start);

    while (!openSet.isEmpty()) {
        Node current = openSet.poll();

        if (current.x == goal.x && current.y == goal.y) {
            return reconstructPath(current);
        }

        for (int[] dir : DIRECTIONS) {
            int nx = current.x + dir[0];
            int ny = current.y + dir[1];
            if (!isValid(grid, nx, ny)) continue;

            Node neighbor = allNodes.getOrDefault(key(nx, ny), new Node(nx, ny));
            int tentativeG = current.costFromStart + 1;

            if (tentativeG < neighbor.costFromStart) {
                neighbor.parent = current;
                neighbor.costFromStart = tentativeG;
                neighbor.estimatedTotalCost = tentativeG + heuristic(neighbor, goal);
                allNodes.put(key(nx, ny), neighbor);
                openSet.remove(neighbor);
                openSet.add(neighbor);
            }
        }
    }

    return null; // no path found
}

private static int heuristic(Node a, Node b) {
    // Manhattan distance
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

private static boolean isValid(int[][] grid, int x, int y) {
    return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0;
}

private static List<Node> reconstructPath(Node end) {
    List<Node> path = new ArrayList<>();
    Node current = end;
    while (current != null) {
        path.add(current);
        current = current.parent;
    }
    Collections.reverse(path);
    return path;
}

private static String key(int x, int y) {
    return x + "," + y;
}

int[][] grid = {
    {0,0,0,0,1,0,0,0},
    {1,1,0,0,1,0,1,0},
    {0,0,0,1,0,0,1,0},
    {0,1,1,0,0,1,0,0},
    {0,0,0,0,0,0,0,1},
    {1,0,1,1,0,1,0,0},
    {0,0,0,0,0,0,0,0},
};

Node start = new Node(0, 0);
Node goal = new Node(6, 7);
long startTime, endTime;
// Dijkstra
startTime = System.nanoTime();
List<Node> pathDijkstra = dijkstra(grid, start, goal);
endTime = System.nanoTime();
System.out.println("Dijkstra's path length: " + (pathDijkstra == null ? "No path" : pathDijkstra.size()));
System.out.println("Dijkstra's time (ms): " + (endTime - startTime)/1_000_000.0);
start = new Node(0, 0);
goal = new Node(6, 7);
startTime = System.nanoTime();
List<Node> pathAStar = aStar(grid, start, goal);
endTime = System.nanoTime();
System.out.println("A* path length: " + (pathAStar == null ? "No path" : pathAStar.size()));
System.out.println("A* time (ms): " + (endTime - startTime)/1_000_000.0);

6:

public class Heuristic {

    private final int cMin; // minimum movement cost on the map

    public Heuristic(int cMin) {
        this.cMin = cMin;
    }

    /**
     * Calculates the heuristic cost estimate from node (x1, y1) to goal (x2, y2)
     * using Manhattan distance multiplied by the minimum movement cost.
     */
    public int estimate(int x1, int y1, int x2, int y2) {
        int dx = Math.abs(x2 - x1);
        int dy = Math.abs(y2 - y1);
        return cMin * (dx + dy);
    }

    public static void main(String[] args) {
        // Example: minimum cost on map is 1
        Heuristic heuristic = new Heuristic(1);
        int h = heuristic.estimate(startX, startY, goalX, goalY);
        System.out.println("Heuristic estimate: " + h);
    }
}

Heuristic heuristic = new Heuristic(1);
int startX = 2, startY = 3;
int goalX = 7, goalY = 8;
int h = heuristic.estimate(startX, startY, goalX, goalY);
System.out.println("Heuristic estimate: " + h);