uniformkostnadssökning

Uniform Cost Search (UCS), known in Swedish as uniformkostnadssökning, is a graph traversal and pathfinding algorithm used in artificial intelligence and computer science. It systematically explores a graph by expanding the node with the lowest path cost from the start node. UCS guarantees finding the optimal path to a goal node in a weighted graph, meaning it finds the path with the minimum total edge weight.

The algorithm maintains a priority queue of nodes to visit, ordered by their path cost from the start. Initially, the priority queue contains only the start node with a cost of zero. In each step, UCS removes the node with the lowest cost from the priority queue, marks it as visited, and adds its unvisited neighbors to the queue. The cost to reach each neighbor is calculated by adding the cost to reach the current node and the weight of the edge connecting them. If a neighbor is already in the priority queue with a higher cost, its cost is updated to the new, lower cost. This process continues until the goal node is reached or the priority queue is empty, indicating no path exists.

UCS is considered an uninformed search algorithm because it does not use any heuristic information about the goal's location. Its primary advantage is its optimality guarantee, but it can be less efficient than informed search algorithms like A* search in large graphs, as it may explore many suboptimal paths before finding the optimal one. The computational complexity of Uniform Cost Search depends on the number of nodes and edges in the graph, as well as the edge weights.