How do you define problem? What are criteria for defining problem? Compare Constraint Satisfaction Problem and Real World Problem in detail with appropriate example.

A problem is a situation (difficult/easy) experienced by an agent. The problem is solved by a sequence of actions that reduce the difference between the initial situation and the goal.  A problem when defined with its components is called a well-defined problem.

Criteria for defining the problem:

• Initial State: It is the starting state or initial step of the agent towards its goal.
• Actions: It is the description of the possible actions available to the agent.
• Transition Model: It describes what each action does.
• Goal Test: It determines if the given state is a goal state.
• Path cost: It assigns a numeric cost to each path that follows the goal. The problem-solving agent selects a cost function, which reflects its performance measure.

Constraint Satisfaction Problem:

The problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is usable by different researchers to compare the performance of algorithms.

A constraint satisfaction problem (CSP) consists of
➢ a set of variables,
➢ a domain for each variable, and
➢ a set of constraints.
The aim is to choose a value for each variable so that the resulting possible world satisfies the constraints.

Example: Crypto Arithmetic Problem

States: Arrangement of any numbers on the given arithmetic.
Initial State: Unsolved digits.
Actions: Replace the digits with unique numbers.
Transition model: Returns the arithmetic with the added numbers.
Goal test: Checks whether all the bits are replaced.
Path cost: There is no need for path cost because only final states are counted.

Solution:

   A B C

+D E F

=G H I

=>

1. A ≠ B ≠ C ≠ D ≠ E ≠ F ≠ G ≠ H ≠ I
2. C + F = I
C + F = 10 + I (I as carry)
3. B + E = H
B + E = 10 + H
B + E + 1 = H
B + E + 1 =10 + H (H as carry)
4. A + D = G
A + D + 1 = G

Step 1:

Domain of C = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Domain of F = {1, 2, 3, 4, 5, 6, 7, 8, 9}
So,
Domain of I = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Select C = 4 & F = 9 Then I = 3 (Carry = 1)
So,

 A B 4

+D E 9

=G H 3

Step 2:

Domain of B = {1, 2, 5, 6, 7, 8}
Domain of E = {1, 2, 5, 6, 7, 8}
So,
Domain of H = {0, 1, 2, 5, 6, 7, 8}
Select B = 2 & E = 8
Then H = 10+1 {previous carry = 1 + (Carry = 1)}
So,

 A 2 4

+D 8 9

G 1 3

Step 3:

Domain of A = {0, 5, 6, 7}
Domain of D = {0, 5, 6, 7}
So, Domain of G = {5, 6}
Select A = 0 & D = 5 Then G = 6 (with addition of Carry)
So,
Hence, the required solutions are:
A = 0, B = 2, C = 4, D = 5, E = 8, F = 9, G = 6, H = 1, I = 3.

 0 2 4

+5 8 9

6 1 3

Real-World Problem:

Those problem whose solution people actually care about. Such problems tend not to have a single agreed upon description, but we can give the general flavour of their formulations.

Example:

Consider the airline travel problems that must be solved by a travel-planning website:

States: Each state obviously includes a location (like an airport) and the current time. Furthermore, because the cost of an action ( a flight segment) may depend on previous segments, their fare bases, and their status of domestic or international, the state must record extra information about these “historical” aspects.

Initial state: Specified by user’s query.

Actions: Take any flight from current location, in any seat class, leaving after the current time, leaving enough time for within-airport transfer if needed.

Transition model: The state resulting from taking a flight will have the flight’s destination as the current location and the flight’s arrival time as the current time.

Goal test: Are we at the final destination specified by the user?

Path cost: This depends on monetary cost, waiting time, flight time, customs, immigration procedure, seat quality, time of day, type of airplane, frequent-flyer mileage awards and so on.