State Space (상태 공간)
- What is a state space?
A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behaviour of a given system and is widely used in the fields of AI and game theory.
Example: 15 Puzzle
| 7 | 5 | 6 | 15 |
|---|---|---|---|
| 9 | 2 | 3 | |
| 8 | 1 | 11 | 4 |
| 10 | 14 | 13 | 12 |
위 퍼즐을 움직여서 아래의 퍼즐의 상태로 만들어보자.
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 |
위와 같은 경우는 오랜 시간이 걸릴 수 있겠지만 맞출 수는 있다. 그러나 만약 퍼즐을 뜯어서 새로운 위치에 넣었다면 아무리 오랜 시간이 걸려도 문제를 풀 수 없다. 상태공간이 변형되었기 때문이다.
- Set of all possible configurations
- Link between states changeable in one move
Properties of 15 puzzle state space
- Size: 16! nodes
- 2 connected components
- If you change 2 pieces, you go to the other component
Why?
- Invariant
- Let the empty spot be 16
- Parity of permutation plus parity of distance of 16 from corner
- The above parity is preserved
Search Trees and Cutoff
- State space graph is usually too big
- For 15 puzzle, 16! is almost
2*(10^13) - Most likely you make only some of the nodes
- and traverse the graph as if it is a tree
- So it looks like the tree is growing
- You cut off a branch if there is no solution in that direction
Subset Sum Problem
- Problem Definition
- Input: Set of positive integers A={a1, a2, …, an} and target S
- Problem is NP-Complete
- Pseudopolynomial algorithm exists
- Can we do exhaustive search with cutoff?
Exhaustive Search for Subset Sum
그래프를 어느쪽으로 만들어 갈것인가를 생각해 작전을 잘 짜야 한다.
How will you cut off?
- In other words, how can you be sure that there is no solution?
- Cut off at level i if
C + sigma(n, j=i+1) ai<S or C>S)
Traveling Salesman Problem
- Problem Definition
- Input: Weighted graph G, initial node s
- Goal: Find a path starting at s, ending at s, that visits each node exactly once, and of minimum sum of edge weights
노드가 n개면 전체 방법의 개수는 (n-1)!가지이다.
State Tree
각 단계마다 지금까지 본 가장 좋은 값인 current best cost를 구할 수 있다. 이 값을 가지고 cutoff를 할 수 있다.
How do you cut off?
- Simple: Cut off if current cost(of node) is larger than the best seen so far
- A bit better: Cut off if
current cost + # of remaining edgesis larger than the best seen so far - Still better: Cut off if
current cost + (# of remaining edges) * (smallest edge weight)is larger than the best seen so far