Artificial Intelligence

105 collapsed lines
1
import java.util.*;
2

3
public class UCS<T> {
4
    private final Map<T, Double> costTo;
5
    private final Map<T, T> parent;
6
    private final PriorityQueue<T> pq;
7
    private final Set<T> visited;
8

9
    /**
10
     * A directed edge constructor with a cost.
11
     */
12
    public static class Edge<T> {
13
        T neighbor;
14
        double cost;
15

16
        public Edge(T neighbor, double cost) {
17
            this.neighbor = neighbor;
18
            this.cost = cost;
19
        }
20
    }
21

22
    /**
23
     * Uniform-cost search constructor.
24
     */
25
    public UCS(Map<T, List<Edge<T>>> graph, T startNode) {
26
        costTo = new HashMap<>();
27
        parent = new HashMap<>();
28
        visited = new HashSet<>();
29

30
        for (T node : graph.keySet()) {
31
            costTo.put(node, Double.POSITIVE_INFINITY);
32
            parent.put(node, null);
33
        }
34
        costTo.put(startNode, 0.0);
35

36
        pq = new PriorityQueue<>(Comparator.comparingDouble(costTo::get));
37
        pq.offer(startNode);
38

39
        while (!pq.isEmpty()) {
40
            T currentNode = pq.poll();
41
            visited.add(currentNode);
42

43
            if (costTo.get(currentNode) == Double.POSITIVE_INFINITY) continue;
44

45
            for (Edge<T> edge : graph.get(currentNode)) {
46
                relax(currentNode, edge.neighbor, edge.cost);
47
            }
48
        }
49
    }
50

51
    /**
52
     * Relaxation of an edge.
53
     *
54
     * @param u the source node
55
     * @param v the target node
56
     * @param cost the cost of the edge
57
     */
58
    private void relax(T u, T v, double cost) {
59
        if (costTo.get(v) > costTo.get(u) + cost) {
60
            costTo.put(v, costTo.get(u) + cost);
61
            parent.put(v, u);
62
            pq.offer(v);
63
        }
64
    }
65

66
    /**
67
     * Get the cost to a node.
68
     *
69
     * @param node the target node
70
     * @return the cost to the target node
71
     */
72
    public double getCostTo(T node) {
73
        return costTo.getOrDefault(node, Double.POSITIVE_INFINITY);
74
    }
75

76
    /**
77
     * Check if a path exists to a node.
78
     *
79
     * @param node the target node
80
     * @return true if a path exists, false otherwise
81
     */
82
    public boolean hasPathTo(T node) {
83
        return costTo.get(node) < Double.POSITIVE_INFINITY;
84
    }
85

86
    /**
87
     * Get the path to a node.
88
     *
89
     * @param targetNode the target node
90
     * @return the path to the target node
91
     */
92
    public List<T> getPathTo(T targetNode) {
93
        if (!hasPathTo(targetNode)) {
94
            return null;
95
        }
96

97
        List<T> path = new ArrayList<>();
98
        for (T v = targetNode; v != null; v = parent.get(v)) {
99
            path.add(v);
100
        }
101

102
        Collections.reverse(path);
103
        return path;
104
    }
105
}

40 collapsed lines
1
#ifndef UCS_H
2
#define UCS_H
3

4
#include <unordered_map>
5
#include <unordered_set>
6
#include <vector>
7
#include <queue>
8
#include <limits>
9
#include <algorithm>
10
#include <functional>
11

12
template <typename T>
13
class UCS {
14
public:
15
    struct Edge {
16
        T neighbor;
17
        double cost;
18

19
        Edge(T neighbor, const double cost) : neighbor(neighbor), cost(cost) {}
20
    };
21

22
private:
23
    std::unordered_map<T, double> costTo;
24
    std::unordered_map<T, T> parent;
25
    std::priority_queue<T, std::vector<T>, std::function<bool(T, T)>> pq;
26
    std::unordered_set<T> visited;
27

28
public:
29
    UCS(const std::unordered_map<T, std::vector<Edge>>& graph, const T& startNode)
30
        : pq([this](T a, T b) { return costTo[a] > costTo[b]; }) {
31

32
        for (const auto& node : graph) {
33
            costTo[node.first] = std::numeric_limits<double>::infinity();
34
            parent[node.first] = T();
35
        }
36
        costTo[startNode] = 0.0;
37

38
        pq.push(startNode);
39

40
        while (!pq.empty()) {
41
            T currentNode = pq.top();
42
            pq.pop();
43
            visited.insert(currentNode);
44

45
            if (costTo[currentNode] == std::numeric_limits<double>::infinity()) continue;
46

47
            for (const auto& edge : graph.at(currentNode)) {
48
                relax(currentNode, edge.neighbor, edge.cost);
49
            }
50
        }
51
    }
52

53
    void relax(const T& u, const T& v, double cost) {
54
        if (costTo[v] > costTo[u] + cost) {
55
            costTo[v] = costTo[u] + cost;
56
            parent[v] = u;
57
            pq.push(v);
58
        }
59
    }
60

61
    double getCostTo(const T& node) const {
62
        auto it = costTo.find(node);
63
        if (it != costTo.end()) {
64
            return it->second;
65
        }
66
        return std::numeric_limits<double>::infinity();
67
    }
68

69
    bool hasPathTo(const T& node) const {
70
        return getCostTo(node) < std::numeric_limits<double>::infinity();
71
    }
72

73
    std::vector<T> getPathTo(const T& targetNode) const {
74
        if (!hasPathTo(targetNode)) {
75
            return {};
76
        }
77

78
        std::vector<T> path;
79
        for (T v = targetNode; v != T(); v = parent.at(v)) {
80
            path.push_back(v);
81
        }
82

83
        std::reverse(path.begin(), path.end());
84
        return path;
85
    }
86
};
87

88
#endif // UCS_H

56 collapsed lines
1
class Edge:
2
    def __init__(self, neighbor, cost):
3
        """
4
        An edge with a neighbor and a cost.
5
        """
6
        self.neighbor = neighbor
7
        self.cost = cost
8

9
class UCS:
10
    def __init__(self, graph, start_node):
11
        """
12
        Initialize uniform-cost search with a graph and a start node.
13
        'graph' is a dict mapping each node to a list of Edge objects.
14
        """
15
        self.cost_to = {}
16
        self.parent = {}
17
        self.visited = set()
18
        self.adj = graph
19

20
        # Initialize all costs to infinity and parents to None
21
        for node in graph:
22
            self.cost_to[node] = float('inf')
23
            self.parent[node] = None
24

25
        # Start node cost is 0
26
        self.cost_to[start_node] = 0.0
27

28
        # Use a list for priority queue (heapq) instead of PriorityQueue
29
        import heapq
30
        self.pq = []
31
        heapq.heappush(self.pq, (0.0, start_node))
32

33
        # Main loop
34
        while self.pq:
35
            current_cost, current_node = heapq.heappop(self.pq)
36
            if current_node in self.visited:
37
                continue
38

39
            self.visited.add(current_node)
40

41
            # Skip if unreachable
42
            if self.cost_to[current_node] == float('inf'):
43
                continue
44

45
            # Relax edges of current node
46
            for edge in self.adj.get(current_node, []):
47
                self.relax(current_node, edge.neighbor, edge.cost)
48

49
    def relax(self, u, v, cost):
50
        """
51
        Update cost_to[v] (relaxation) if a cheaper path is found.
52
        """
53
        new_cost = self.cost_to[u] + cost
54
        if new_cost < self.cost_to[v]:
55
            self.cost_to[v] = new_cost
56
            self.parent[v] = u
57
            import heapq
58
            heapq.heappush(self.pq, (new_cost, v))
59

60
    def get_cost_to(self, node):
61
        """
62
        Get the cost of the path to 'node'.
63
        """
64
        return self.cost_to.get(node, float('inf'))
65

66
    def has_path_to(self, node):
67
        """
68
        Check if a path to 'node' exists.
69
        """
70
        return self.get_cost_to(node) < float('inf')
71

72
    def get_path_to(self, target_node):
73
        """
74
        Reconstruct the path to 'target_node'.
75
        Returns None if no path exists.
76
        """
77
        if not self.has_path_to(target_node):
78
            return None
79

80
        path = []
81
        current = target_node
82
        while current is not None:
83
            path.append(current)
84
            current = self.parent[current]
85
        return path[::-1]

99 collapsed lines
1
import java.util.*;
2

3
public class AStarSearch {
4
    public static class Node implements Comparable<Node> {
5
        int x, y;
6
        double f, g, h;
7
        Node parent;
8

9
        public Node(int x, int y) {
10
            this.x = x;
11
            this.y = y;
12
        }
13

14
        @Override
15
        public int compareTo(Node other) {
16
            return Double.compare(this.f, other.f);
17
        }
18

19
        @Override
20
        public boolean equals(Object obj) {
21
            if (this == obj) return true;
22
            if (!(obj instanceof Node other)) return false;
23
            return this.x == other.x && this.y == other.y;
24
        }
25

26
        @Override
27
        public int hashCode() {
28
            return Objects.hash(x, y);
29
        }
30
    }
31

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

38
    // Manhattan distance
39
    private static double heuristic(Node a, Node b) {
40
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
41
    }
42

43
    public static List<Node> aStar(int[][] grid, Node start, Node goal) {
44
        PriorityQueue<Node> openSet = new PriorityQueue<>();
45
        Set<Node> closedSet = new HashSet<>();
46

47
        start.g = 0;
48
        start.h = heuristic(start, goal);
49
        start.f = start.g + start.h;
50
        openSet.add(start);
51

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

55
            if (current.equals(goal)) {
56
                return reconstructPath(current);
57
            }
58

59
            closedSet.add(current);
60

61
            int[][] directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
62
            for (int[] dir : directions) {
63
                int newX = current.x + dir[0];
64
                int newY = current.y + dir[1];
65
                if (!isValid(grid, newX, newY))
66
                    continue;
67

68
                Node neighbor = new Node(newX, newY);
69
                if (closedSet.contains(neighbor))
70
                    continue;
71

72
                double tentativeG = current.g + 1;
73

74
                boolean inOpenSet = openSet.contains(neighbor);
75
                if (!inOpenSet || tentativeG < neighbor.g) {
76
                    neighbor.parent = current;
77
                    neighbor.g = tentativeG;
78
                    neighbor.h = heuristic(neighbor, goal);
79
                    neighbor.f = neighbor.g + neighbor.h;
80

81
                    if (!inOpenSet) {
82
                        openSet.add(neighbor);
83
                    }
84
                }
85
            }
86
        }
87
        return null;
88
    }
89

90
    private static List<Node> reconstructPath(Node current) {
91
        List<Node> path = new ArrayList<>();
92
        while (current != null) {
93
            path.add(current);
94
            current = current.parent;
95
        }
96
        Collections.reverse(path);
97
        return path;
98
    }
99
}

113 collapsed lines
1
#ifndef ASTARSEARCH_H
2
#define ASTARSEARCH_H
3

4
#include <vector>
5
#include <queue>
6
#include <cmath>
7
#include <algorithm>
8
#include <utility>
9

10
struct Node {
11
    int x, y;
12
    double f, g, h;
13
    Node* parent;
14

15
    Node(const int x, const int y) : x(x), y(y), f(0), g(0), h(0), parent(nullptr) {}
16

17
    bool operator==(const Node& other) const {
18
        return x == other.x && y == other.y;
19
    }
20
};
21

22
struct CompareNode {
23
    bool operator()(const Node* a, const Node* b) const {
24
        return a->f > b->f;
25
    }
26
};
27

28
namespace AStar {
29
    // Manhattan distance heuristic
30
    inline double heuristic(const Node* a, const Node* b) {
31
        return std::abs(a->x - b->x) + std::abs(a->y - b->y);
32
    }
33

34
    // Check if cell (x, y) is valid and walkable in the grid
35
    inline bool isValid(const std::vector<std::vector<int>>& grid, int x, int y) {
36
        return (x >= 0 && x < grid.size() &&
37
                y >= 0 && y < grid[0].size() &&
38
                grid[x][y] == 0);
39
    }
40

41
    // Reconstruct the path from goal to start by following parent pointers.
42
    inline std::vector<std::pair<int, int>> reconstructPath(Node* current) {
43
        std::vector<std::pair<int, int>> path;
44
        while (current != nullptr) {
45
            path.emplace_back(current->x, current->y);
46
            current = current->parent;
47
        }
48
        std::ranges::reverse(path);
49
        return path;
50
    }
51

52
    // A* search algorithm.
53
    // Note: For simplicity, this example does not free allocated memory.
54
    inline std::vector<std::pair<int, int>> aStar(const std::vector<std::vector<int>>& grid, Node* start, const Node* goal) {
55
        std::priority_queue<Node*, std::vector<Node*>, CompareNode> openSet;
56
        std::vector<Node*> closedSet;
57

58
        start->g = 0;
59
        start->h = heuristic(start, goal);
60
        start->f = start->g + start->h;
61
        openSet.push(start);
62

63
        constexpr int directions[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
64

65
        while (!openSet.empty()) {
66
            Node* current = openSet.top();
67
            openSet.pop();
68

69
            // Goal check
70
            if (*current == *goal) {
71
                return reconstructPath(current);
72
            }
73

74
            closedSet.push_back(current);
75

76
            // Explore neighbors
77
            for (const auto direction : directions) {
78
                const int newX = current->x + direction[0];
79
                const int newY = current->y + direction[1];
80

81
                if (!isValid(grid, newX, newY))
82
                    continue;
83

84
                auto neighbor = new Node(newX, newY);
85

86
                // Skip if neighbor is in closedSet
87
                bool skip = false;
88
                for (const Node* closedNode : closedSet) {
89
                    if (*closedNode == *neighbor) {
90
                        skip = true;
91
                        break;
92
                    }
93
                }
94
                if (skip) {
95
                    delete neighbor;
96
                    continue;
97
                }
98

99
                const double tentativeG = current->g + 1;
100

101
                neighbor->parent = current;
102
                neighbor->g = tentativeG;
103
                neighbor->h = heuristic(neighbor, goal);
104
                neighbor->f = neighbor->g + neighbor->h;
105
                openSet.push(neighbor);
106
            }
107
        }
108

109
        return {};
110
    }
111
}
112

113
#endif // ASTARSEARCH_H

84 collapsed lines
1
import heapq
2

3
class Node:
4
    def __init__(self, x, y):
5
        self.x = x
6
        self.y = y
7
        self.f = 0.0
8
        self.g = 0.0
9
        self.h = 0.0
10
        self.parent = None
11

12
    def __lt__(self, other):
13
        return self.f < other.f
14

15
    def __eq__(self, other):
16
        if other is None:
17
            return False
18
        return self.x == other.x and self.y == other.y
19

20
    def __hash__(self):
21
        return hash((self.x, self.y))
22

23
def is_valid(grid, x, y):
24
    return (0 <= x < len(grid) and
25
            0 <= y < len(grid[0]) and
26
            grid[x][y] == 0)
27

28
def heuristic(a, b):
29
    return abs(a.x - b.x) + abs(a.y - b.y)
30

31
def a_star(grid, start, goal):
32
    open_set = []
33
    closed_set = set()
34

35
    start.g = 0
36
    start.h = heuristic(start, goal)
37
    start.f = start.g + start.h
38
    heapq.heappush(open_set, (start.f, start))
39

40
    while open_set:
41
        current_f, current_node = heapq.heappop(open_set)
42
        if current_node == goal:
43
            return reconstruct_path(current_node)
44

45
        closed_set.add(current_node)
46

47
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
48
        for dir_x, dir_y in directions:
49
            new_x = current_node.x + dir_x
50
            new_y = current_node.y + dir_y
51
            if not is_valid(grid, new_x, new_y):
52
                continue
53

54
            neighbor = Node(new_x, new_y)
55
            if neighbor in closed_set:
56
                continue
57

58
            tentative_g = current_node.g + 1
59

60
            in_open_set = False
61
            for _, node_in_open_set in open_set:
62
                if node_in_open_set == neighbor:
63
                    in_open_set = True
64
                    break
65

66
            if not in_open_set or tentative_g < neighbor.g:
67
                neighbor.parent = current_node
68
                neighbor.g = tentative_g
69
                neighbor.h = heuristic(neighbor, goal)
70
                neighbor.f = neighbor.g + neighbor.h
71

72
                if not in_open_set:
73
                    heapq.heappush(open_set, (neighbor.f, neighbor))
74
                else:
75
                    pass
76

77
    return None
78

79
def reconstruct_path(current_node):
80
    path = []
81
    while current_node:
82
        path.append(current_node)
83
        current_node = current_node.parent
84
    return path[::-1]