Constraint Satisfaction problem with example


In real life problem solving and applications, we are asked to provide the best solution keeping certain constraints in mind. Let us consider an example. Each year the National Film Awards jury has to pick a certain film as the best film of that year. How would the assessing Jury arrive at a reasonably good judgement? Do they have to watch each and every single film that year? Simple logic says that if the Jury members decide to watch three films per day it will take them the whole year (India makes over a thousand films each year) to view all of them. How does one handle such a solution demanding situation?

As with all complex problems, we need to use good heuristics in this case because evaluation of all possible entity is simply infeasible. Let us say that at the outset the National Jury need to be provided a list of best fifty films that year which can possible make the final grade. Depending on the size of various regional film industries, the selection number from that industry can be fixed and local film critics/Local Jury member can allocate scores/grades and select the best from that industry. A criteria could be set that LFSR (Local Film Score Rating) should be 0.6 and above on a scale of 1.

Similarly the apex film jury can allocate NFSR (National Film Score Rating) and based on summative score of LFSR & NFSR the best film can be chosen. We may further set additional criteria that NFSR >0.7 and LFSR+NFSR>0.8. These criteria becomes essential to filter and set standards so that the winning film is worthy of the prestigious honor.

Let us assume that the decision is arrived at through the opinion of ten jury members, five at local level represented by LJ1, LJ2, LJ3, LJ4, LJ5 and five at National levels are represented by NJ1, NJ2, NJ3, NJ4 & NJ5 …

So, now we basically have to compute the following:

Maximize (LFSR+NFSR)   where   LJ1+LJ2+LJ3+LJ4+LJ5= LFSR

&      NJ1+NJ2+NJ3+NJ4+NJ5= NFSR

Subject to       (LFSR/5)> 0.6

(NFSR/5)> 0.7



Leave a comment

Filed under Articles, artificial intelligence

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s