Assignment 3: Solving Problems by Searching

Research on the following uninformed search strategies and explain. (at least 50 words per strategy)

1. Iterative deepening search
   
2. Bidirectional Search

• Iterative deepening search
  Iterative deepening search or depth-first search (IDDFS) is a state space strategy in which the depth-limited search is run repeatedly. To make this possible, calculate the specific depth to be iterated though depth-limited 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 depth-limited 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 graph-based 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 single-core processor or other processing medium.
  

References:
http://en.wikipedia.org/wiki/Bidirectional_search
http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

http://wiki.answers.com/Q/What_is_the_advantage_of_iterative_deepening_search_over_depth-first#ixzz1D0kNUJbn
http://matthias.jimdo.com/downloads/iterative-deepening-search/
http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Bidirectional_Search
http://intelligence.worldofcomputing.net/ai-search/bidirectional-search.html

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 depth-first 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

As I understand on briefly reading the book and visiting my "Memory", Iterative Deepening Search is similar if not the same with Depth-First Search. This was taught to us during our "Analysis of Algorithm" subject so I'm going to refer to what I was taught. Depth-First 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.

Iterative deepening effectively performs a breadth-first search in a way that requires much less memory than breadth-first search does.
It works by running depth-first search repeatedly with a growing constraint on how deep to explore the tree. This gives you you a search that is effectively breadth-first with the low memory requirements of depth-first 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.