AI Problem Solving and Graph Representation

AI Problem

• An AI problem has an initial configuration, called the initial state (s°), which is a starting point.
• The goal of an AI problem is to reach a desired state, called the goal state (G).
• To solve the problem, you apply actions to the initial state (s°) step-by-step, creating new states until the goal state (G) is achieved.

Problem Solving in AI

• Problem solving aims to reach the goal state (G) starting from the initial state (s°).
• A search space is formed by all possible actions applied to any state (si) in the problem, leading to new states (sj).

Problem Solving in AI - Graph Representation

• Problem solving can be represented as a graph where nodes represent states and edges represent actions.
• All nodes in this graph collectively define the search space, which represents every possible state of the problem.

Representation of Search Problems - Graphs and Trees

• A search problem can be represented using a directed graph where:
  • Nodes represent the states.
  • Arcs represent the allowed actions.
• An undirected graph implies that the edges do not have a direction, they connect two nodes without a specific direction.
• A weighted graph has edges with weights (costs) associated with them, representing the cost of applying a specific action.
• A path is a sequence of edges or nodes.
• A loop, also known as a cycle, exists where a sequence of edges lead back to the original node.
• A graph is considered connected if there is a path between any two nodes.