Best First Search

Best first Search

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.

Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function  which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.

Some authors have used "best-first search" to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first. This specific type of search is called greedy best-first search or pure heuristic search.

Efficient selection of the current best candidate for extension is typically implemented using a priority queue.

other Search Techniques like hill Climbing, 

Depth First Search Techniques

How do we search a graph?
At a particular vertices, where shall we go next?
Two common framework:  

• the depth-first search (DFS)
• the breadth-first search (BFS) and 

In DFS, go as far as possible along a single path until reach a dead end (a vertex with no edge out or no neighbor unexplored) then backtrack
In BFS, one explore a graph level by level away (explore all neighbors first and then move on)

Color Scheme

• Vertices initially colored white
• Then colored gray when discovered
• Then black when finished

Time Stamp

• Discover time d[u]:  when u is first discovered 
• Finish time f[u]: when backtrack from u
• d[u] < f[u]

Application 

• Topological Sort
• Strongly Connected Component

Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. 

• Search for all vertices  that are directly reachable from the root (called level 1 vertices)
• After mark all these vertices, visit all vertices that are directly reachable from any level 1 vertices (called level 2 vertices), and so on.
• In general, level k vertices are directly reachable from a level k – 1 vertices

1. White vertices have not been discovered ( All vertices start out white )
2. Grey vertices are discovered but not fully explored ( They may be adjacent to white vertices)
3. Black vertices are discovered and fully explored (They are adjacent only to black and gray vertices)
4. Explore vertices by scanning adjacency list of grey vertices

Applications:
Breadth-first search can be used to solve many problems in graph theory, for example:

• Copying garbage collection, Cheney's algorithm
• Finding the shortest path between two nodes u and v (with path length measured by number of edges)
• Testing a graph for bipartiteness 
• (Reverse) Cuthill–McKee mesh numbering
• Ford–Fulkerson method for computing the maximum flow in a flow network
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
• Construction of the failure function of the Aho-Corasick pattern matcher.

Characteristics of Production Systems

Production system:

Production system is useful to structure AI programs in a way that is facilitates describing and performing the search process.  Don’t confuse of the word production such as to describe is done in factories.

•            A production system is consist of a set of rules. Left side (a pattern) that determines the applicability of the rule and right side that describes the operation to be performed if the rule is applied.
•           One or more knowledge / data bases that contain whatever information is appropriate for the particular task. 
•       A control strategy that specifies the order in which the rules will be compared to the database and way of resolving the conflict that arise when several rules match at once.
•        A rule applier. 

1    Requirements of a good control strategy:
                 How to decide which rule is apply is next during the process of searching for a solution to a problem  

• The first requirement is that it can cause motion: Consider the water jug problem. Suppose we implemented the simple control strategy of starting each time at the top of the list of rules and choosing the first applicable one.
•  The second requirement is that it be systematic: The requirement that a control strategy be systematic corresponds to the need for global motion as well as for local motion.

Production System Characteristics:

We have argued that production systems are a good way to describe the operations that can be performed in a search for a solution to a problem.

•  Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
•  If  so,  what relationships are  there  between  problem  types and the types  of  production  system  best suited  to solving the problems?

Artificial Intelligence : Introduction , Various types of production systems

Introduction of Artificial Intelligence :

Artificial intelligence (AI) is the intelligence exhibited by machines or software. It is also the name of the academic field of study which studies how to create computers and computer software that are capable of intelligent behavior. Major AI researchers and textbooks define this field as "the study and design of intelligent agents", in which an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success.

Various types of production systems:

Various Types of Soft Computing Techniques and Application of Soft Computing

Various types of soft computing techniques: 
Soft computing consist several computing paradigms  mainly are :

• Neural Network
• Fuzzy Logic
• Genetic Algorithm    

Application of Soft Computing:

• A Fusion Approach of Multi spectral Images with SAR (Synthetic Aperture Radar).
• Optimization of traveling Salesman Problem using Genetic Algorithm Approach.
• Genetic algorithm base Internet search technique.
• Hybrid fuzzy Controllers based on Soft Computing.
• Rocket Engine control based on Soft Computing.
• Architectural design and development of new approaches combining fuzzy logic, neural networks, evolutionary computation, and other recent computational intelligence methods in the SC paradigm.
• Comparative theoretical and empirical studies on SC techniques, with validation through convincing computational experiments, performance measures, and convergence proof.
• Application of SC techniques (e.g., big data, smart systems, semantic web, sustainable development, cloud computing, dynamic processes, and other domains in science and engineering)