25-07-2012, 02:56 PM
Implement BFS and DFS for a given directed graph as adjacency matrix and show output USING GRAPHICS.
Implement BFS and DFS.doc (Size: 232.5 KB / Downloads: 46)
INTRODUCTION
Many of the problems that fall within the purview of artificial intelligence are too complex to be solved by direct techniques rather they must be attacked by appropriate search methods armed with what ever direct techniques available to guide the search. A frame work for describing search methods is provided in this chapter and several general purpose search techniques are given which are called heuristic search. They can be described independently of any particular task or problem domain. But when applied to particular problems their efficacy is highly dependent on the way they eploit domain-specific knowledge since in and of themselves they are unable to overcome the combinational explosion to which search processes are so vulnerable. For this reason , these techniques are often called weak methods.
Adjacency Matrix
This is the n by n matrix, where n is the number of vertices in the graph. If there is an edge from some vertex x to some vertex y, then the element ax, y is 1 (or, in case of weighted graph, the weight of the edge connecting x and y), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph.
DESIGN METHODOLOGY
CONTROL STRATAGIES
During the process of searching for a solution to a problem a question arises of how to decide which rule to apply next when more than one rule will have its left side match the current state. Even without a great deal of though, it is clear that how such decisions are made will have a crucial impact on how quickly and even whether, a problem is finally solved.
• The first requirement of a good control strategy is that it cause motion. Control strategies that do not cause motion will never lead to a solution.
• The second requirement of a good control strategy is that it be systematic. Because the control strategy is not systematic, we may explore a particular useless sequence of operators several times before we finally find a solution. The requirement that a control strategy be systematic corresponds to the need for global motion as well as for local motion .
Uninformed Search
This section contain search strategies that come under the heading of uninformed search also called blind search . The term means that they have no additional information about states beyond that provided in the problem definition . All they can do is generate successors and distinguish a goal state from a non goal state. Strategies that know whether one non goal state is more promising than another are called informed search or heuristic search strategies.
Breadth First Search :
Suppose for any problem a tree is constructed with the initial state as its root. Generate all the offspring of the root by applying each of the applicable rules to the initial state. Now for each leaf node, generate all its successors by applying all the rules that are appropriate. Continue this process until some rule produces a goal state. This process is call breadth first search.
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.