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

  • Answered by oriattic
  • 0 Comments
  • 12 months ago

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.

 

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

s
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments