Varieties of CSPs

 Varieties of CSPs:

•Discrete variables

–finite domains:

–infinite domains:

•e.g., job scheduling, variables are start/end days for each job

•need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3

•Continuous variables

–e.g., start/end times for Hubble Space Telescope observations

Constraint satisfaction problems (CSPs)

•Standard search problem:

–state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test

•CSP:

–state is defined by variables Xi with values from domain Di

–goal test is a set of constraints specifying allowable combinations of values for subsets of variables

•Simple example of a formal representation language

•Allows useful general-purpose algorithms with more power than standard search algorithms

Question bank

Memory bounded heuristic search

 Memory bounded heuristic search:

•To reduce memory- Iterative deepening to the heuristic search.

•2 memory bounded algorithm:

     1) RBFS (recursive best-first search).

     2) MA* (Memory-bounded A*) and 

         SMA*(simplified memory MA*)

RBFS:

 

•It attempts to mimic the operation of BFS.

•It replaces the f-value of each node along the path with the best f-value of its children.

•Suffers from using too little memory.

•Even if more memory were available , RBFS has no way to make use of it.

SMA*

 

•Proceeds life A*,expands best leaf until memory is full.

•Cannot add new node without dropping an old one. (always drops worst one)

•Expands the best leaf and deletes the worst leaf.

•If all have same f-value-selects same node for expansion and deletion.

•SMA* is complete if  any reachable solution.

Save water:

Espure Water Solution Pvt Ltd 

Chennai,India.

www.espure.in

Mobile: 9944116631 / 9841005335

Effluent Treatment Plant Manufacturer in Chennai

http://enpure.in/effluent-treatment-plant/

Informed search

 Informed search:

•That uses problem-specific knowledge beyond the definition of the problem itself.

•It can find solution more efficiently than uninformed search.

•Informed search – Best First Search.

Best-first search

•Idea: use an evaluation function f(n) for each node

Expand most desirable unexpanded node

•Implementation:

  Order the nodes in fringe in decreasing order of desirability

•Key component – heuristic function h(n)

     h(n) = estimated cost of the cheapest path from node n to goal node.

•Special cases:

–greedy best-first search

–A* search

Uninformed search strategies

•Uninformed search strategies use only the information available in the problem definition(Blind search)

•Breadth-first search

•Uniform-cost search

•Depth-first search

•Depth-limited search

•Iterative deepening search

Search strategies

•A search strategy is defined by picking the order of node expansion

•Strategies are evaluated along the following dimensions:

–completeness: does it always find a solution if one exists?

–time complexity: number of nodes generated

–space complexity: maximum number of nodes in memory

–optimality: does it always find a least-cost solution?