Artificial Intelligence

import java.util.*; class Node implements Comparable<Node> { String state; Node parent; int cost; public Node(String state, Node parent, int cost) { this.state = state; this.parent = parent; this.cost = cost; } @Override public int compareTo(Node other) { return Integer.compare(this.cost, other.cost); } } public class UCS { public static List<String> uniformCostSearch(Map<String, Map<String, Integer>> graph, String start, String goal) { PriorityQueue<Node> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(new Node(start, null, 0)); Set<String> explored = new HashSet<>(); while (!priorityQueue.isEmpty()) { Node current = priorityQueue.poll(); if (current.state.equals(goal)) { List<String> path = new ArrayList<>(); while (current != null) { path.add(current.state); current = current.parent; } Collections.reverse(path); return path; } explored.add(current.state); Map<String, Integer> successors = graph.getOrDefault(current.state, Collections.emptyMap()); for (Map.Entry<String, Integer> entry : successors.entrySet()) { String successor = entry.getKey(); int cost = entry.getValue(); Node successorNode = new Node(successor, current, current.cost + cost); if (!explored.contains(successor)) { boolean inQueue = false; for (Node n : priorityQueue) { if (n.state.equals(successor)) { inQueue = true; if (n.cost > successorNode.cost) { priorityQueue.remove(n); // Remove higher cost node priorityQueue.offer(successorNode); // Add lower cost node break; // Important: Exit loop after updating } } } if (!inQueue) { priorityQueue.offer(successorNode); } } } } return null; // No path found } }

#include <iostream> #include <queue> #include <vector> #include <unordered_map> #include <unordered_set> #include <functional> struct Node { int state; Node* parent; int cost; explicit Node(const int s, Node* p = nullptr, const int c = 0) : state(s), parent(p), cost(c) {} // Comparison operator for priority queue (min-heap) bool operator>(const Node& other) const { return cost > other.cost; } }; std::vector<int> uniform_cost_search(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start, int goal) { std::priority_queue<Node, std::vector<Node>, std::greater<>> priority_queue; priority_queue.emplace(start); std::unordered_set<int> explored; while (!priority_queue.empty()) { Node current_node = priority_queue.top(); priority_queue.pop(); if (current_node.state == goal) { std::vector<int> path; const Node* current = &current_node; while (current) { path.push_back(current->state); current = current->parent; } std::reverse(path.begin(), path.end()); return path; } explored.insert(current_node.state); if (graph.contains(current_node.state)) { for (const auto&[fst, snd] : graph.at(current_node.state)) { int successor = fst; const int cost = snd; if (!explored.contains(successor)) { Node successor_node(successor, &current_node, current_node.cost + cost); // Use pointer to current_node bool in_queue = false; std::vector<Node> temp_queue; while(!priority_queue.empty()){ Node queue_node = priority_queue.top(); priority_queue.pop(); if (queue_node.state == successor){ in_queue = true; if (queue_node > successor_node){ temp_queue.push_back(successor_node); } else { temp_queue.push_back(queue_node); } } else{ temp_queue.push_back(queue_node); } } for (const auto& node : temp_queue){ priority_queue.push(node); } if (!in_queue) { priority_queue.push(successor_node); } } } } } return {}; }

import heapq class Node: def __init__(self, state, parent=None, cost=0): self.state = state self.parent = parent self.cost = cost def __lt__(self, other): return self.cost < other.cost def uniform_cost_search(graph, start, goal): priority_queue = [] heapq.heappush(priority_queue, Node(start)) explored = set() while priority_queue: current_node = heapq.heappop(priority_queue) if current_node.state == goal: path = [] while current_node: path.append(current_node.state) current_node = current_node.parent return path[::-1] explored.add(current_node.state) for successor, cost in graph.get(current_node.state, {}).items(): # Directly access successors and costs successor_node = Node(successor, current_node, current_node.cost + cost) if successor not in explored: in_queue = False for i, node in enumerate(priority_queue): if node.state == successor: in_queue = True if node.cost > successor_node.cost: priority_queue[i] = successor_node heapq.heapify(priority_queue) break if not in_queue: heapq.heappush(priority_queue, successor_node) return None