본문 바로가기

개발&컴퓨터/알고리즘

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


반응형