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

* 상태, 연산자, 그리고 상태 트리를 이용해 답을 찾아나가는 것
  * 물론 이를 직접 프로그래밍 하지는 않으며, _DFS/BFS_ 를 사용해 풀어나감

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

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

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

![https://i.imgur.com/ZdLDAi4.png](https://i.imgur.com/ZdLDAi4.png)

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

### DFS
* Stack을 이용
  * 알고리즘 보면 알겠지만, FIFO

```js
// 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에 넣어주고

### BFS
* Queue 이용하는 것
  * LIFO

```js
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 이슈가 발생될 수 있고

* 알고리즘은 다음과 같음

```js
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같은 문제가 발생하게 된다

### A* 알고리즘
* 너무 깊이는 들어가지 않도록 하는 것
  * 평가함수 `f(n) = g(n) + h(n)`
  * `h(n)`: 현재 노드에서 목표까지의 거리
  * `g(n)`: 초기 상태에서 현재까지의 비용(깊이)

* 알고리즘은 비슷한

```js
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'
    }
  }
}
```

#### 탐색의 방향
* 지금까지 한 탐색은 '전향추론'
  * 전향추론: _초기상태 => 목표상태_ 탐색
  * 후향추론: _목표상태 => 초기상태_ 탐색

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

### Mini-Max 알고리즘
![https://t1.daumcdn.net/cfile/tistory/25579C38596D93C127](https://t1.daumcdn.net/cfile/tistory/25579C38596D93C127)

* 두 명 이상의 상대가 서로 겨룰 때 사용할 수 있는 알고리즘
  * depth를 진행할 때 마다 서로 번갈아가며
  * _자신에게 최적인(자신이 원하는)_ 결과를 취하도록 한다
  * 위의 그림에서는 짝수는 Max, 홀수는 min 값을 취하도록 함

* 마지막 node에 도착해야만이 중간 node의 값을 알 수 있음
  * 아래부터 올라오는 구조이기 때문
  * 따라서 _비효율적_
  * 또한, 너무 깊이 들어갈 수가 있기에 max-depth를 잡곤 함

####  alpha-beta 가지치기
* `a`, `b`를 이용해 가지쳐서 Mini-Max 알고리즘을 좀 더 빠르게 진행할 수 있도록 하는 방법
  * `a`는 Max (init: `a := -inf`)
  * `b`는 min 을 가리킴 (init: `b := inf`)

* 진행하며 가지치는 것
  * 방법은 [유튜브](https://youtu.be/_i-lZcbWkps) 참고

# 전문가 시스템
* 생성규칙: `IF-THEN` 으로 표현한 문장
  * `IF`: 조건
  * `THEN`: 결과

* 전문가 시스템은 info와 생성 규칙을 이용하는 것
  * 정보(info): 의미가 있게 체계화된 것
  * 데이터: 의미가 없는 그냥 사실
  * 지식(knowledge): 더욱 일반화되고 모호해진, 정제된 정보

* 이런 전문가 시스템은 사실로 새로운 사실을 만들어 내는 것이기에
  * 결과에 대한 이유를 설명할 수 있다

![https://i.imgur.com/3Fv0X9I.png](https://i.imgur.com/3Fv0X9I.png)

* 전문가 시스템의 세 파트
  * 지식 베이스
  * 추론엔진
  * 인터페이스

* 다음과 같이 동작하는 것

![https://i.imgur.com/5GPgtGC.png](https://i.imgur.com/5GPgtGC.png)

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

## 순방향 연결 추론
![https://i.imgur.com/jjlYNe8.png](https://i.imgur.com/jjlYNe8.png)

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

![https://i.imgur.com/oU6xguP.png](https://i.imgur.com/oU6xguP.png)

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`를 찾아내지

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

## 역방향 연결 추론
![https://i.imgur.com/jjlYNe8.png](https://i.imgur.com/jjlYNe8.png)

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

![https://i.imgur.com/4dDlxMD.png](https://i.imgur.com/4dDlxMD.png)

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 비슷한 애
  * 전문가 시스템과 함께 사용하곤 한다

## 몀제논리의 추론
* 인공지능에서의 논리
  * 명제논리: `P`, `R` 이런걸로 추상화하는거
  * 술어논리: 전체 문장을 주어/목적어 이렇게 분리하는 것

* 이 중, 명제논리를 구현해보면 다음과 같음

C|D|­|C -> D
-|-|-|-
T|T|­|T
_T_|_F_|­|_F_
F|T|­|T
F|F|­|T

* 이게 뭘 의미하느냐?
  * 조건 `C`가 참이면, 결과 `D`도 참
  * 물론, `C`가 참이 아니어도, 결과 `D`는 참이 될 수 있음
  * __그러나, `C`가 참이나 결과 `D`가 거짓일 수는 없음__

* 기억해야하는 규칙들 (위의 구현과 함께 보면 좋겠지)
  * Modus Tollens(부정식)
    * `A -> B`일 때, `~B` 면 `~A`
    * 결과가 false면, 가정도 false
    * `(A -> B) and ~B => ~A`
  * Modus Ponens
    * `A -> B`일 때, `A`면 `B`
    * 가정이 true면, 결과도 true
    * `(A -> B) and A => B`
  * Chain Rule (삼단논법): `A -> B, B -> C`일 때, `A -> C`
    * `A -> B and B -> C => A -> C`

## 술어논리의 추론
* 명제논리를 술어논리로 변환

`p`|`q`|­|`~p`|­|`~p v q`|­|`p -> q`
-|-|-|-|-|-|-|-
`T`|`T`|­|`F`|­|`T`|­|`T`
`T`|`F`|­|`F`|­|`F`|­|`F`
`F`|`T`|­|`T`|­|`T`|­|`T`
`F`|`F`|­|`T`|­|`T`|­|`T`

* 그냥 뭐 그대로 대치되는 것
  * 즉, _`~p v q <=> p -> q`_

* 예시
  * `forall(x): DOG(x) -> MAMML(x)`
  * `~DOG(x) v MAMML(x)`

# Fuzzy
![https://i.imgur.com/B6nyKLQ.png](https://i.imgur.com/B6nyKLQ.png)

* fuzzy: 확실하지 않은... 확률의 세계 (`0.0 ~ 1.0`)
  * fuzzy logic: 명확히 정의할 수 없는 지식을 표현하는 방법
  * fuzzy set: 이런 애매모호한 값들의 집합을 나타내기 위한 방법

* 일반 집합
  * `A = { x | x > 6 }`

* 퍼지 집합
  * `A = { x, u A(x) | x in A }`
    * `u`는 비율
  * `A = { u A (x_i) / x_i | x in A }` (참고로 `/`는 나누는 게 아니라, 그냥 구분기호임)
    * `A = {u_A (x_1) / x_1}, {u_A (x_2) / x_2}, ...`
    * 이렇게 비율별로 나타내는 것

## 연산
* 설정한 Fuzzy set에 대해, 이를 좀 더 집중화 할 수가 있다
  * 이를 _헤지_ 라고 하며, 좀 더 모호한?표현을 할 수 있도록 함

* 일반적인 퍼지 집합

![https://i.imgur.com/va9mCt2.png](https://i.imgur.com/va9mCt2.png)

* 헤지를 적용한 퍼지 집합(초록색)

![https://i.imgur.com/yrO9oU4.png](https://i.imgur.com/yrO9oU4.png)

* 이러한 헤지는 기존의 퍼지 집합에 대해 다음과 같은 연산을 통해 가능하겠지
  * `[u_A (x)]^{n}`
  * `n < 1`: 볼록해짐
  * `n > 1`: 오목해짐 (위 그림과 같음)

## 퍼지추론
* 규칙에 대해
  * OR: `max`
  * AND: `min`
  * NOT: `1 - value` (여집합)

* 전건: `IF`
* 후건: `THEN`

* 소속 함수: `u_A (x)`

### 1\. 뭐암튼 이렇게 해서 퍼지 값을 구하고 (퍼지화)
![https://i.imgur.com/BfsCq5C.png](https://i.imgur.com/BfsCq5C.png)

* _어떠한 일을 진행하는데 있어 정의된 평가 기준에 따라 퍼지값을 구한다_

* A
  * `u(x = A2) = 0.2`
  * `u(x = A3) = 0.2`

* B
  * `u(y = B1) = 0.1`
  * `u(y = B2) = 0.8`

### 2\. 이를 규칙에 따라 값을 구한다 (규칙 평가)
![https://i.imgur.com/zBAH91f.png](https://i.imgur.com/zBAH91f.png)

* 위와 같은 규칙 집합 및 아래와 같은 규칙들이 있다고 한다
  * 이 역시 미리 정의된 규칙이겠지

* 규칙1 (`C1`): _`x`가 `A2` __OR__ `y`가 `B1`_
  * `max(u(x = A2), u(y = B1)) = max(0.2, 0.1) = 0.2`
  * 즉, 규칙 `C1 = 0.2`

* 규칙2 (`C2`): _`x`가 `A2` __AND__ `y`가 `B2`_
  * `min(u(x = A2), u(y = B2)) = min(0.2, 0.8) = 0.2`
  * 즉, 규칙 `C2 = 0.2`

* 규칙3 (`C3`): _`x`가 `A1`_
  * `C3 = u(x = A1) = 0`

![https://i.imgur.com/latKqBZ.png](https://i.imgur.com/latKqBZ.png)

* 이를 통해 위와 같이 구해지겠다

### 3\. 통합 (규칙 후건의 통합)
![https://i.imgur.com/QQnmG1M.png](https://i.imgur.com/QQnmG1M.png)

* 이렇게 통합되고

### 4\. 역퍼지화
* 다음 수식을 통해 무게중심을 구한다
  * 무게중심의 값은 `u_A (x)` 안에 있다

![https://i.imgur.com/KQzqV32.png](https://i.imgur.com/KQzqV32.png)

* 해 보면 다음과 같음

![https://i.imgur.com/SZJia1T.png](https://i.imgur.com/SZJia1T.png)

* 즉, `35%`의 확률로 어떠한 일이 발생된다는 것을 암시한다는 말

# 베이즈 추론
* 다음을 기반으로 한다

![https://i.imgur.com/QoYBB0O.png](https://i.imgur.com/QoYBB0O.png)

* 위를 통해 다음을 이끌어낼 수 있다
  * `A`와 `B`가 함께 일어날 확률은
  * `B`가 일어난 상태에서 `A`가 일어날 확률

![https://i.imgur.com/vzYYw6D.png](https://i.imgur.com/vzYYw6D.png)

* 여기서, 교집합의 교환법칙으로 인해 다음과 같음을 알 수 있다

![https://i.imgur.com/SiOyPKQ.png](https://i.imgur.com/SiOyPKQ.png)

* 따라서, 다음과 같다고 할 수 있다

![https://i.imgur.com/xIvk51W.png](https://i.imgur.com/xIvk51W.png)

## 응용
* `A`가 일어날 확률을 다음과 같이도 표현할 수 있을 것이다
  * `B`가 일어난 상태에서 `A`가 일어날 확률 +
  * `B`가 일어나지 않은 상태에서 `A`가 일어날 확률
  * 이를 수식으로 표현하면 다음과 같다

![https://i.imgur.com/3xbCGOK.png](https://i.imgur.com/3xbCGOK.png)

* 이를 통해 위의 식을 다음과 같이 표현할 수 있음

![https://i.imgur.com/3HW0Taf.png](https://i.imgur.com/3HW0Taf.png)

## 문제풀이

# 진화 알고리즘
* 인코딩 과정
  * 평가
  * 선택
  * 교차
  * 변이 (_이후 다시 평가 반복_)

---

# 참고
### `n`-queen 경우의 수
![https://i.imgur.com/TGaUngX.png](https://i.imgur.com/TGaUngX.png)