Search in Artificial Intelligence (기초)

Search in A.I.

• Definition :

The Process that solve the problem or find the path to reach a solution by computer itself.

• The essential and fundamental way in solving the problem of A.I.
• Techniques of solving problems
  
• Direct Method : (ex : The Tower of Hanoi)
  
• State Space : (ex : Puzzle Problem)
     - Initial state -> Operation (operator) -> Goal state
• The Basic Search Techniques
  
• BMA(British Museum Algorithm) : Random Search
  
• Depth-first Search : The Searching to a deep point, gradually. (vertically)
      * Merit : Save memory. Find the solution fast, though the solution is in the deep point.
      * Fault : Possibly go wrong way.  The solution is always not the best solution.
  
• Breath-first Search : The method that search horizontally until meeting the goal node.
      * Merit : Find the best solution always.
      * Fault : Need much time and memory, the step is going deeper.

• Heuristic Techniques :

It is based on human intuition but cannot be proved by logically and mathematically. (The Techniques that explained previous page are named a algorithmic Techniques.)

• So closed to the human thought. Using a experiential knowledge.
      * Merit : Save much time and storage space.
      * Fault :  Always not the best solution.
  

Simple Example - Traveling Salesman Problem

[The distance between two cities]

* The Answer by Heuristics : C-D-B-A-C

* This solution is not best but acceptable.

Application : Games(ex. Chess, Janggi), Natural language context processing, NP-Problem