• 탐색

  • 상태공간 내에서
  • 시작상태에서 목표상태까지의 경로를 찾는 것
  • 각 상태를 생성하는 것을 연산자 라고 함

• 상태, 연산자, 그리고 상태 트리를 이용해 답을 찾아나가는 것

  • 물론 이를 직접 프로그래밍 하지는 않으며, DFS/BFS 를 사용해 풀어나감

• 알고리즘

  • 맹목적인 탐색
    • 임의의 경로: BFS, DFS
    • 최적의 경로: 균일 비용 탐색
  • 경험적 탐색(휴리스틱)
    • 임의의 경로: 언덕오르기, 최적 우선
    • 최적 경로: A* 알고리즘

• 이를 8-Puzzle 예제를 통해 보도록 하겠다

• 8-puzzle에서의 시작, 목표 상태는 다음과 같음

• 연산자는 총 4개가 있으며, 다음과 같음
  • UP: 공백을 위로
  • RIGHT: 공백을 우측으로
  • BOTTOM: 공백을 아래로
  • LEFT: 공백을 좌측으로

• Stack을 이용
  • 알고리즘 보면 알겠지만, FIFO

// define arrays
open := [start]
closed := []

while (open != []) { // while open has items
  item := open.unshift() // get item (when left end of open)

  if (item == goal) { // check item is goal state
    return SUCCESS
  }

  closed.push(item) // put item on closed

  for(generated_item : generate_children(item)) { // generate children of item
    if ((open or closed) not contain generated_item) { // check duplicated
      open.shift(generated_item) // left end of open
    }
  }
}

1. 맨왼쪽의 open item 얻어내고
2. 이를 goal state와 비교하고
3. 아니면 children generate하고
4. closed와 비교해 중복제거하며 open의 왼쪽에 넣고
5. 마지막으로 item을 closed에 넣어주고

• Queue 이용하는 것
  • LIFO

open := [start]
closed := []

while (open != []) {
  item := open.unshift()

  if (item == goal) {
    return SUCCESS
  }

  closed.push(item)

  for (generated_item : generate_children(item)) {
    if ((open or closed) not contain generated_item) {
      open.push(generated_item) // right end of open
    }
  }
}

1. 알고리즘 나머지 다 같고
2. 단지 generated_item을 open의 right에 넣는다는 차이점 만 있다
3. 이건 LIFO로 구현해야 하니 이러하게 된 것

• 효율은 BFS가 더 좋다

• 그러나 이들은 가능한 노드를 모두 탐색해대니 느릴 수 밖에 없다

  • 경험적 탐색은 경험적(휴리스틱) 정보 를 사용해 좀 더 효율적인 동작이 가능하다

• 8-puzzle에 대한 휴리스틱 정보는 다음 두 가지로 나눌 수 있다

  • h1: 현재 제 위치에 있지 않은 타일의 개수
  • h2: 각 타일의 목표 위치까지의 거리

• 이들을 이용해 각각의 휴리스틱 탐색을 진행할 수 있는 것

  • 휴리스틱 정보. 즉, 평가함수의 값을 원하는 상태(goal)로 향하도록 진행하는 탐색
  • 가령 h1은 값이 낮은 방향으로 진행하는... 그런 것을 말한다
  • 이렇게 평가함수는 문제에 따라 종속적이라고 할 수 있음

• 이는 언덕오르기 알고리즘 을 이용해 진행한다

  • 자신이 목표로 하는 상태에 더 가까운 것을 선택하는 알고리즘
  • 선택되지 않은 상태는 저장되지 않음 = 중복허용
  • 더 이상 선택할 것이 없을 때, 그 곳을 정상이라고 판단
    • 이 때문에, local maxima 이슈가 발생될 수 있고

• 알고리즘은 다음과 같음

open := [{ start, eval_value }]
closed := []

while (open != []) {
  item :=  open.unshift()

  if (item == goal) {
    return SUCCESS
  }

  closed.push(item)

  for (generated_item : generate_children(item)) {
    if ((open or closed) not contain generated_item) {
      eval_value := calc_eval(generated_item) // calc eval_function value

      open.push({ generated_item, eval_value })

      open.sort('eval_value') // sort by 'eval_value'
    }
  }
}

• 그러나 local maxima같은 문제가 발생하게 된다

• 너무 깊이는 들어가지 않도록 하는 것

  • 평가함수 f(n) = g(n) + h(n)
  • h(n): 현재 노드에서 목표까지의 거리
  • g(n): 초기 상태에서 현재까지의 비용(깊이)

• 알고리즘은 비슷한

open := [{ start, eval_value }]
closed := []

while (open != []) {
  item := open.unshift()

  if (item == goal) {
    return SUCCESS
  }

  closed.push(item)

  for (generated_item : generate_children(item)) {
    if ((open or closed) not contain generated_item) {
      // eval_value = h + g
      eval_value := calc_h(generated_item) + calc_g(gengerated_item)

      open.push({ generated_item, eval_value })

      open.sort('eval_value') // sort by 'eval_value'
    }
  }
}

• 지금까지 한 탐색은 '전향추론'

  • 전향추론: 초기상태 => 목표상태 탐색
  • 후향추론: 목표상태 => 초기상태 탐색

• 문제에 따라 후향추론이 더 알맞은 경우도 있다

• 두 명 이상의 상대가 서로 겨룰 때 사용할 수 있는 알고리즘

  • depth를 진행할 때 마다 서로 번갈아가며
  • 자신에게 최적인(자신이 원하는) 결과를 취하도록 한다
  • 위의 그림에서는 짝수는 Max, 홀수는 min 값을 취하도록 함

• 마지막 node에 도착해야만이 중간 node의 값을 알 수 있음

  • 아래부터 올라오는 구조이기 때문
  • 따라서 비효율적
  • 또한, 너무 깊이 들어갈 수가 있기에 max-depth를 잡곤 함

• a, b를 이용해 가지쳐서 Mini-Max 알고리즘을 좀 더 빠르게 진행할 수 있도록 하는 방법

  • a는 Max (init: a := -inf)
  • b는 min 을 가리킴 (init: b := inf)

• 진행하며 가지치는 것

  • 방법은 유튜브 참고

• 생성규칙: IF-THEN 으로 표현한 문장

  • IF: 조건
  • THEN: 결과

• 전문가 시스템은 info와 생성 규칙을 이용하는 것

  • 정보(info): 의미가 있게 체계화된 것
  • 데이터: 의미가 없는 그냥 사실
  • 지식(knowledge): 더욱 일반화되고 모호해진, 정제된 정보

• 이런 전문가 시스템은 사실로 새로운 사실을 만들어 내는 것이기에

  • 결과에 대한 이유를 설명할 수 있다

• 전문가 시스템의 세 파트

  • 지식 베이스
  • 추론엔진
  • 인터페이스

• 다음과 같이 동작하는 것

• 점화를 이용해 추론을 진행하는데
  • 이 떄, 순방향/역방향이 가능

• 사실 Z를 찾는다고 하자
  • 초기값은 다음과 같다고 가정하고
  • 찾는 과정은 아래와 같음

1. 기반지식 위에서부터 하나씩 진행한다
   • Y & D랑 X & B & E 이거 세 개는 없어서 건너뛴거
2. 사실 A가 있으니, A -> X 진행하고
   • X를 사실DB에 넣으라는 말
3. C 있으니, C -> L
4. L & M은 없으니 일단 건너뛰고
   • 다시 맨 위에서부터 시작
5. X & B & E 있으니, X & B & E -> Y 진행
   • L & M은 마찬가지로 없고
6. Y & D 있으니, Y & D -> Z 진행
   • 이를 통해 Z를 찾아내지

• 이렇게 진행하는 것이다
  • 단, 보다싶이 마구잡이로 사실을 막 생성하기에
  • 좀 비효율적 ㅎ

• 얘는 목표 지향
  • 쓸데없는 상태 만들지 않는다는 말
  • 왜냐고? 애초에 goal에서 시작하걸랑
  • 초기 상태는 동일

1. 목표 사실 Z부터 시작해 역으로 추론을 시작한다
2. Y & C -> Z니까, Y와 C를 찾아줌
   • 참고로 C는 이미 있으니, Y만 찾아주면 되겠지
3. X & A -> Y
   • A는 이미 있고, X만 찾아주면 된다
4. B -> X
   • 이를 통해 Z가 추론가능함을 알 수 있겠지
5. 그대로 추론진행

• AI의 핵심은 지식 인데, 이를 체계적으로 정제한 것

• 지식표현 종류

  • 논리
  • 규칙
  • 의미망
  • 프레임
  • OOR(Object-Oriented Representation)

• 규칙

  • 앞서 전문가시스템에서 봤지
  • (A, B) -> (C, D, E) 로도 표현이 가능하댄다

• 의미망

  • 카나리 is a 새
  • 새 has 날개
  • 배니 is a 카나리
  • 뭐 이런 관계를 명시한 것
  • 전문가 시스템과 함께 사용하곤 한다

• 프레임

  • 속성과 메서드가 합쳐저 있는, 마치 Class 비슷한 애
  • 전문가 시스템과 함께 사용하곤 한다

• 언어의 종류
  • 형식언어 => 프로그래밍 언어
  • 자연언어

• 매개변수 종류

  • 형식 매개변수: 파라미터
  • 실 매개변수: 인자

• 매개변수 전달 방법

  • 참조 호출: call by reference
  • 값 호출: call by value
  • 이름 호출: 파라미터 자체가 인자로 치환되는 것

• 다음을 각각 참조, 값, 이름 호출로 호출하면?

Begin Integer A, B:
  Procedure F(X, Y, Z); Integer X, Y, Z;
    Begin
      Y := Y + 2;
      Z := Z + X;
    End F;

  A := 3;
  B := 5;

  F(A + B, A, A);
  PRINT A         // <= 결과무엇?

END

• 참조

  • Y와 Z가 A를 가리킨다는 것만 잘 알고 있으면 된다
  • 따라서 PRINT A는 13을 출력

• 값

  • 이건 뭐... 당연히 3을 출력

• 이름

  • F(X, Y, Z)가 F((A + B), A, A)로 변하는 것
  • 따라서 다음과 같아진다
    • Y := Y + 2 => A := A + 2 => A := 5 + 2
    • Z := Z + X => A := A + (A + B) => A := 5 + (5 + 5)
  • 답은 15

• 어셈블러
  • 대부분 two-pass-assembler 로 구성된다
  • first pass: 어셈블리 코드로 기호표를 작성
  • second pass: 이를 bit로 표시

• 다음 순서로 진행되겠지

  1. 어휘분석: 토큰화
  2. 구문분석: 파스 트리
  3. 의미분석
  4. 중간코드 생성
  5. 최적화
  6. 목적코드 생성
  7. 목적 프로그램

• 구문분석에서 parse tree 만드는거 나온다고