Graphs,Trees

Property of algorithm:

Completeness: The algorithm guarantees to find a solution when there’s one in a finite time.

Optimal: The algorithm finds the best solution

Tree: Removing an edge disconnects the graph, adding an edge creates a cycle

Uninformed/Blind search

Only knows whether it has reached the goal state. Doesn’t know whether one state is more “promising” than the other.

Breadth-first search

Expands the node with the lowest depth. All the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded.

The root node is expanded first, then all the successors of that node are expanded next, then their successors, and so on. All the nodes are expanded at a given depth before any nodes at the next levels are expanded.

Is complete but not guaranteed to be optimal, and gives optimal results when the path cost is a non-decreasing function of the depth of the node.

Uniform cost search

Expands the node with the lowest path cost, uses a priority queue

vs Dijkstra: (Ref: Click here)

The main difference is that Dijkstra’s algorithm is defined when the numbers of vertices are finite. It says to put all the vertices in a queue. But we can not put all the vertices in a queue when the numbers of vertices tend to be infinite. Uniform Cost Search is defined in a situation like this, where the numbers of vertices are unknown.

This picks the shortest paths first. If there were any other shorter path to a currently picked vertex, v would have been picked before.