Assignment 3: Solving Problems by Searching
Page 1 of 1 • Share
Assignment 3: Solving Problems by Searching
Research on the following uninformed search strategies and explain. (at least 50 words per strategy)
 Iterative deepening search
 Bidirectional Search
blacksnake Posts : 18
Join date : 20101120
Age : 30
Location : Davao
Re: Assignment 3: Solving Problems by Searching
 Iterative deepening search
Iterative deepening search or depthfirst search (IDDFS) is a state space strategy in which the depthlimited search is run repeatedly. To make this possible, calculate the specific depth to be iterated though depthlimited search like only 3 nodes for this search. Then calculate the total depth of the node and the divided by the number of nodes set based on the depthlimited search which resulted to number of iterations in integer. For example, the node depth is 9 and the limited depth per search is 3 so therefore, it requires up to 3 iterations to make search possible.  Bidirectional Search
Bidirectional Search is a graphbased search algorithm that finds the shortest path from initial vertex to goal vertex (for directed graphs), and searches some indexes more efficiently. The process run in two simultaneous searches: one forward from the initial state and one backward from the goal state. The advantages are the searching time cuts into half from the search time in linear search and increasing searching efficiency. But there are drawbacks; it uses more processing and overhead in completing the search that compromises performances in a singlecore processor or other processing medium.
References:
http://en.wikipedia.org/wiki/Bidirectional_search
http://en.wikipedia.org/wiki/Iterative_deepening_depthfirst_search
blacksnake Posts : 18
Join date : 20101120
Age : 30
Location : Davao
uninformed search strategies
Iterative deepening effectively performs a breadthfirst search in a way that requires much less memory than breadthfirst search does. Iterative deepening works by running depthfirst search repeatedly with a growing constraint on how deep to explore the tree. This gives you a search that is effectively breadthfirst with the low memory requirements of depthfirst search. This algorithm applies a depthlimited search with increasing limits and combines the advantages of depthfirst search (i.e. it saves space/memory) and breadthfirst search (i.e. it expands by layers which guarantee that the shortest path is found).
So, the Iterative Deepening performs very well since it applies the advantages between depthfirst and breadthfirst search.
Bidirectional search is an algorithm that uses two searches occurring at the same time to reach a target goal. Bidirectional Search, as the name implies, searches in two directions at the same time: one forward from the initial state and the other backward from the goal.
The beautiful about Bidirectional search is its speed. It also requires less memory.
So, the Iterative Deepening performs very well since it applies the advantages between depthfirst and breadthfirst search.
Bidirectional search is an algorithm that uses two searches occurring at the same time to reach a target goal. Bidirectional Search, as the name implies, searches in two directions at the same time: one forward from the initial state and the other backward from the goal.
The beautiful about Bidirectional search is its speed. It also requires less memory.
http://wiki.answers.com/Q/What_is_the_advantage_of_iterative_deepening_search_over_depthfirst#ixzz1D0kNUJbn
http://matthias.jimdo.com/downloads/iterativedeepeningsearch/
http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Bidirectional_Search
http://intelligence.worldofcomputing.net/aisearch/bidirectionalsearch.html
aqua_pepper214 Posts : 7
Join date : 20110124
Age : 31
Location : Davao City
Re: Assignment 3: Solving Problems by Searching
 Iterative Deepening DepthFirst Search
Iterative Deepening Search is a graph search algorithm that will find the shortest path based with some given property, even if the graph includes cycles. When searching for a path through a graph, starting at a given initial node, where the path or its end node has some desired property, a depthfirst search may never find a solution if it enters a cycle in the graph.
 Bidirectional Search
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to an end vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state and one backward from the end, stopping when the two meet in the middle. The reason for this approach is that in many cases it is faster.
References:
http://encyclopedia2.thefreedictionary.com/Iterative+deepening+depthfirst+search
http://encyclopedia.thefreedictionary.com/bidirectional+search
deyong Posts : 7
Join date : 20110124
ASSIGNMENT 3: SOLVING PROBLEMS BY SEARCHING
Iterative Deepening
Iterative Deepening is an approach used in many AI algorithms to start with an approximate answer, then make it more accurate. The idea is to recompute the elements of the frontier rather than storing them. Each recomputation can be a depthfirst search, which thus uses less space.
When implementing an iterative deepening search, you have to distinguish between
• failure because the depth bound was reached and
• failure that does not involve reaching the depth bound.
Bidirectional Search
The idea of a bidirectional search is to reduce the search time by searching forward from the start and backward from the goal simultaneously. When the two search frontiers intersect, the algorithm can reconstruct a single path that extends from the start state through the frontier intersection to the goal. But the problem with this type of search is on how to ensure that the two frontiers will meet.
http://cs.ubc.ca/~poole/aibook/html/ArtInt_62.html
http://cs.ubc.ca/~poole/aibook/html/ArtInt_65.html
http://theory.stanford.edu/~amitp/GameProgramming/Variations.html
Iterative Deepening is an approach used in many AI algorithms to start with an approximate answer, then make it more accurate. The idea is to recompute the elements of the frontier rather than storing them. Each recomputation can be a depthfirst search, which thus uses less space.
When implementing an iterative deepening search, you have to distinguish between
• failure because the depth bound was reached and
• failure that does not involve reaching the depth bound.
Bidirectional Search
The idea of a bidirectional search is to reduce the search time by searching forward from the start and backward from the goal simultaneously. When the two search frontiers intersect, the algorithm can reconstruct a single path that extends from the start state through the frontier intersection to the goal. But the problem with this type of search is on how to ensure that the two frontiers will meet.
http://cs.ubc.ca/~poole/aibook/html/ArtInt_62.html
http://cs.ubc.ca/~poole/aibook/html/ArtInt_65.html
http://theory.stanford.edu/~amitp/GameProgramming/Variations.html
fjsanico Posts : 6
Join date : 20110210
Re: Assignment 3: Solving Problems by Searching
Iterative Deepening
Iterative deepening is depthfirst search to a fixed depth in the tree being searched. It works by setting a depth of search say, depth 1 and doing depthfirst search to that depth. If a solution is found then the process stops otherwise, increase the depth by, say, 1 and repeat until a solution is found. It is a form of depthfirst search with a lower bound on how deep the search can go. Iterative deepening terminates if there is a solution. It can produce the same solution that breadthfirst search would produce but does not require the same memory usage (as for breadthfirst search).
When implementing an iterative deepening search, you have to distinguish between
• failure because the depth bound was reached and
• failure that does not involve reaching the depth bound.
In the first case, the search must be retried with a larger depth bound. In the second case, it is a waste of time to try again with a larger depth bound, because no path exists no matter what the depth. We say that failure due to reaching the depth bound is failing unnaturally, and failure without reaching the depth bound is failing naturally.
Bidirectional Search
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph.
Bidirectional Search searches in two directions at the same time: one forward from the initial state and the other backward from the goal. This is usually done by expanding tree with branching factor b and the distance from start to goal is d. The search stops when searches from both directions meet in the middle. It is a bruteforce search algorithm that requires an explicit goal state instead of simply a test for a goal condition. Once the search is over, the path from the initial state is then concatenated with the inverse of the path from the goal state to form the complete solution path. It still guarantees optimal solutions.
Reference:
http://www.comp.lancs.ac.uk/computing/research/aaiaied/people/paulb/old243prolog/subsection3_6_4.html
http://www.cs.ubc.ca/~poole/aibook/html/ArtInt_62.html
http://intelligence.worldofcomputing.net/aisearch/bidirectionalsearch.html
http://en.wikipedia.org/wiki/Bidirectional_search
Honey Lynne Accion Posts : 8
Join date : 20101130
Uninformed Search Strategies as I understand
As I understand on briefly reading the book and visiting my "Memory", Iterative Deepening Search is similar if not the same with DepthFirst Search. This was taught to us during our "Analysis of Algorithm" subject so I'm going to refer to what I was taught. DepthFirst Search traverses the tree until it reaches the deepest node it could find. It does not usually checks the traversal cost when deciding what node to visit next. Its main goal or happiness is go as deep as it could.
As I understand again by briefly reading the book and again visiting my "Memory", Bidirectional Search is a search wherein nodes has two connections. A node in a bidirectional search is connected to a another node while that other node is connected to our previous node. This is usually applied when you need to traverse a graph which could detect "Dead Ends" and traverse back to another route. It also used to optimize searching by starting a search at the start node and simultaneously another search is starting from all the end nodes and wait until both searches meet each other somewhere in the middle.
As I understand again by briefly reading the book and again visiting my "Memory", Bidirectional Search is a search wherein nodes has two connections. A node in a bidirectional search is connected to a another node while that other node is connected to our previous node. This is usually applied when you need to traverse a graph which could detect "Dead Ends" and traverse back to another route. It also used to optimize searching by starting a search at the start node and simultaneously another search is starting from all the end nodes and wait until both searches meet each other somewhere in the middle.
blueacid Posts : 10
Join date : 20110314
uninformed search strategies
Iterative deepening effectively performs a breadthfirst search in a way that requires much less memory than breadthfirst search does.
It works by running depthfirst search repeatedly with a growing constraint on how deep to explore the tree. This gives you you a search that is effectively breadthfirst with the low memory requirements of depthfirst search.
Different applications call for different types of search, so there's not one that is always better than any other.
On the other hand, Bidirectional search is a neat trick that can often take an exponential algorithm and make it run on problems that are twice the size of those it could previously solve. It uses two searches occurring at the same time to reach a target goal: search generally appears to be an efficient graph search because instead of searching through a large tree, one search is conducted backwards from the goal and one search is conducted forward from the start.
It works by running depthfirst search repeatedly with a growing constraint on how deep to explore the tree. This gives you you a search that is effectively breadthfirst with the low memory requirements of depthfirst search.
Different applications call for different types of search, so there's not one that is always better than any other.
On the other hand, Bidirectional search is a neat trick that can often take an exponential algorithm and make it run on problems that are twice the size of those it could previously solve. It uses two searches occurring at the same time to reach a target goal: search generally appears to be an efficient graph search because instead of searching through a large tree, one search is conducted backwards from the goal and one search is conducted forward from the start.
lizyl123 Posts : 7
Join date : 20110324
Similar topics
» Roadmaster climate control/ HVAC problems
» Problems with ST70
» Field Maple problems
» sphere homework assignment #5
» Assignment 5: Interview Questions Due Feb 13
» Problems with ST70
» Field Maple problems
» sphere homework assignment #5
» Assignment 5: Interview Questions Due Feb 13
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum

