Artificial Intelligence (AI)

• A graph is a set of nodes (vertices) joined by edges, which may be weighted and directed. Graphs model routes, relationships, game states and neural networks.
• Dijkstra's algorithm finds the shortest distance from a start node to every other node.
• A* finds the shortest path to one goal using f = g + h, where h is a heuristic estimate of the remaining cost; it usually examines fewer nodes.
• Artificial neural networks: input, hidden and output layers joined by weighted connections; training adjusts the weights.
• Machine learning learns from data; deep learning uses networks with many hidden layers; reinforcement learning learns from rewards and penalties.
• Supervised learning uses labelled data; unsupervised learning finds patterns in unlabelled data.
• Back propagation sends the output error back through the network to adjust the weights; regression predicts a continuous value by fitting a function to data.

Shortest distance to every node

A graph is a collection of nodes (vertices) connected by edges. Edges may have a weight (distance, time, cost) and may be directed (one way). Graphs help AI because many problems can be stated as "move from one state to another at the lowest cost": road networks for route planning, positions in a game, links between people or web pages, and the structure of a neural network itself. Once a problem is a graph, search algorithms can solve it. (You are not asked to write code for graphs.)

Dijkstra's algorithm:

1. Give the start node distance 0 and every other node ∞.
2. Visit the unvisited node with the smallest distance.
3. For each neighbour, calculate (distance of current node + edge weight). If this is smaller than the neighbour's recorded distance, replace it and record the current node as its previous node.
4. Mark the current node visited; repeat from step 2 until every node is visited.

Heuristics: f = g + h

A* searches for the shortest path to one particular goal. For each node it calculates

It always expands the open node with the lowest f, updating g for neighbours when a cheaper route is found, and stops when the goal itself has the lowest f. Because h points the search towards the goal, A* usually examines far fewer nodes than Dijkstra. It is guaranteed to find the shortest path only if the heuristic never overestimates the true remaining cost. Dijkstra is the special case h = 0: it finds the shortest path to every node.