Assignment 3: Solving Problems by Searching

View previous topic View next topic Go down

Assignment 3: Solving Problems by Searching

Post  blacksnake on Sat Jan 22, 2011 6:39 pm

Research on the following uninformed search strategies and explain. (at least 50 words per strategy)
  1. Iterative deepening search
  2. Bidirectional Search
avatar
blacksnake

Posts : 18
Join date : 2010-11-20
Age : 28
Location : Davao

View user profile http://projectblacksnake.blogspot.com/

Back to top Go down

Re: Assignment 3: Solving Problems by Searching

Post  blacksnake on Sat Jan 22, 2011 8:29 pm

  • 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
avatar
blacksnake

Posts : 18
Join date : 2010-11-20
Age : 28
Location : Davao

View user profile http://projectblacksnake.blogspot.com/

Back to top Go down

uninformed search strategies

Post  aqua_pepper214 on Sat Feb 05, 2011 1:34 am

Iterative deepening effectively performs a breadth-first search in a way that requires much less memory than breadth-first search does. Iterative deepening works by running depth-first search repeatedly with a growing constraint on how deep to explore the tree. This gives you a search that is effectively breadth-first with the low memory requirements of depth-first search. This algorithm applies a depth-limited search with increasing limits and combines the advantages of depth-first search (i.e. it saves space/memory) and breadth-first 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 depth-first and breadth-first 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. Very Happy



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
avatar
aqua_pepper214

Posts : 7
Join date : 2011-01-24
Age : 29
Location : Davao City

View user profile

Back to top Go down

Re: Assignment 3: Solving Problems by Searching

Post  deyong on Fri Feb 11, 2011 3:16 pm

  • Iterative Deepening Depth-First 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 depth-first 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+depth-first+search
http://encyclopedia.thefreedictionary.com/bidirectional+search

deyong

Posts : 7
Join date : 2011-01-24

View user profile

Back to top Go down

ASSIGNMENT 3: SOLVING PROBLEMS BY SEARCHING

Post  fjsanico on Sat Feb 12, 2011 10:44 pm

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

fjsanico

Posts : 6
Join date : 2011-02-10

View user profile

Back to top Go down

Re: Assignment 3: Solving Problems by Searching

Post  Honey Lynne Accion on Mon Feb 14, 2011 7:52 pm



Iterative Deepening

Iterative deepening is depth-first search to a fixed depth in the tree being searched. It works by setting a depth of search -say, depth 1- and doing depth-first 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 depth-first 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 breadth-first search would produce but does not require the same memory usage (as for breadth-first 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 brute-force 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/ai-search/bidirectional-search.html
http://en.wikipedia.org/wiki/Bidirectional_search







Honey Lynne Accion

Posts : 8
Join date : 2010-11-30

View user profile

Back to top Go down

Uninformed Search Strategies as I understand

Post  blueacid on Thu Mar 24, 2011 7:50 pm

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.

blueacid

Posts : 10
Join date : 2011-03-14

View user profile

Back to top Go down

uninformed search strategies

Post  lizyl123 on Thu Mar 24, 2011 11:36 pm

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.


lizyl123

Posts : 7
Join date : 2011-03-24

View user profile

Back to top Go down

Re: Assignment 3: Solving Problems by Searching

Post  Sponsored content


Sponsored content


Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum