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.
2. 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.
Let’s walk through an example to see how breadth-first search could find a city on our map.
1- Our search begins in Rochester (Start State), and we want to know if we can get to Wausau (Goal State) from there.
2- The Rochester node is placed on the queue in step 1 in previous algorithm. Next we enter our search loop at step 2. Queue=[ Rochester]
3- We remove Rochester, the first node from the queue. Rochester does not contain our goal state (Wausau) so we expand it by taking each child node in Rochester, and adding them to the back of the queue. Queue= [ Sioux Falls, Minneapolis, LaCrosse, and Dubuque ].
4- We remove the first node from the queue (Sioux Falls) and test it to see if it is our goal state. It is not, so we expand it, adding Fargo and Rochester to the end of our queue, which now contains [Minneapolis, LaCrosse, Dubuque, Fargo, and Rochester].
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|