Problem Solving using Search
The breadth-first algorithm spreads out in a uniform manner from the start node. From the start, it looks at each node one edge away. Then it moves out from those nodes to all nodes two edges away from the start. This continues until either the goal node is found or the entire tree is searched.
Characteristics of breadth-first algorithm
• Breadth-first search is complete; It will find a solution if one exists.
• But it is neither optimal in the general case (it won’t find the best solution, just the first one that matches the goal state),
• It doesn’t have good time or space complexity (it grows exponentially in time and memory consumption).
Example
A map like the one in Figure below can be naturally represented by a graph data structure, where the cities names are the nodes, and the major roadways between cities are the links or edges of the graph. So, from a programming perspective, our problem is to traverse a graph data structure in a systematic way until we either find the goal city or exhaust all possibilities. Hopefully having the entire state-space shown on a map will make understanding the operations of the search algorithms easier. In more complex problems, all we have is the single start state and a set of operators which are used to generate more and more new states. The search algorithms work the same way, but conceptually, we are growing or expanding the graph, instead of having it specified at the start. Map of midwestern U.S. cities is illustrated below:-
The breadth-first algorithm spreads out in a uniform manner from the start node. From the start, it looks at each node one edge away. Then it moves out from those nodes to all nodes two edges away from the start. This continues until either the goal node is found or the entire tree is searched.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|