Representation and problem solving:
In the field of AI,o fr all new problem there is a solution to be taken into account in the field of AI.
1. Definition of a problem:
The problem is the situation where there are no immediate solutions. a person feels that there is a problem when he is in a situation where he wants something objective but he does not know what actions to do to get there immediately.
2. The role of good representation:
A good representation of the problem plays an essential role, because it allows:
- Situation Clarification: Transforming a complex problem into understandable and manageable elements.
- Identifying Underlying Causes: Breaking down the problem to better understand its origins and impacts.
- Focusing on Relevant Solutions: A clear representation helps explore appropriate strategies.
- Reducing Confusion: Avoiding misinterpretations by structuring information logically.
- Facilitating Decision Making: With a clear vision, it becomes easier to evaluate the available options.
- Effective Communication: Helping to share the problem with others (colleagues, teams, partners) for better collaboration.
Example : Algorithm that calculates the sum of n first integers.
Computer modeling
Lire ( n )
S:= 0;
For i:=1 to n faire
S:=S+i;
End.
Mathematical modelling:
Lire( n );
S=n(n+1)/2
Ecrire(s)
3. Complexity:
Algorithmic complexity is the evaluation of resources required to execute an algorithm, based on the size of the input. It allows to estimate the efficiency of an algorithm in terms of:
- Time: Number of operations performed (time complexity).
- Memory: Amount of space required (spatial complexity).
Complexity classes:
Example: Calculate the complexity of the sequential search algorithm in a table:
read( x );
b := false;
i:=1;
while(i<=n) and not b do
if [i]=x then do b:=true;
i:=i+1;
fin;
C( n ) = 1 + 1 + 1 + n + n + 1 + n + 1 = 3 n + 5 = O( n )
4. Formalization of problems:
A problem can be represented by a quadruplet (I, O, R, S), where each element plays a key role in the formulation of the problem:
I (Inputs): The input data needed to solve the problem.
O (Outputs): The expected results or the solution to be achieved.
R (Rules or Constraints): The conditions or restrictions to be respected to find the solution.
S (Strategy or Method): The actions or steps to follow to go from inputs to outputs.
Example:
Place 8 queens on a standard 8x8 chessboard such that:
No two queens attack each other.
Solution:
I (Inputs): empty chess table
O (Outputs): chess table containing 8 queens
R (Rules or Constraints): 8 queens must not be in the same line; colomn; diagonal
S (Strategy or Method): design tree for diffrent solutions
4. Representation of a problem by a state graph
Definition:
Directed graph G = (N,A)
N is a set of nodes (or vertices)
A is a set of edges, A ⊆ N × N
Tree :
A tree is a connected graph without cycles.
Example of tree representation (teasing):
