TIL - 2021.09.13

Wanna be __·2021년 9월 15일
0

TIL

목록 보기
32/45
post-thumbnail

Today, I Learned

1. CE2

  • Presentation day - 9/27

2. DB

  • Keys

    • SuperKey
      - 하나 이상의 attributes로, tuple을 unique하게 만드는 key 조합(혹은 1개)
      (id) -> superkey
      (id, name) -> superkey
      (name) -> NOT superkey
    • Candidate Keys
      - minimal superkeys!
      (id) -> candidate key
    • Primary Key
      - same as candidate key.
      동일한 key를 가질 수 없기 때문에 primary key constraints 이라고도 불림.
  • Schema Diagrams

    • Domain knowledge
      ex) 대학의 구성원은 학생, 직원, 강사이다
      와 같은 db를 구성하기 위하여 알고 있어야 하는 정보들.
    • Diagram에서 ForeignKey를 참조하는 쪽에서, 가리키는 방향으로 화살표 가짐.
  • Relational Query Languages

    • Relational Algebra
      6 Types: select(σ), project(Π), union(∪), set difference(−), cartesian product(×), rename(ρ)
    • Cautions
    1. For union and set difference, r,s must have the same arity.
    2. For union and set difference, the attribute domains must be compatible.

    Basic operator인 6개를 바탕으로 Additional Operations로 확장을 하게 됨.

3. AI

  • 지난 Search (DFS, BFS, UCS)의 최종 결론은, UCS가 좋긴 한데(Complete, Optimal) 방향성이 없기 때문에 필요 이상의 Fringe 숫자가 늘어나는 단점이 있다는 점이었음.
    그러한 Search를 blind search의 한계라고 할 때, 어느정도 판단할 수 있는 기준을 가지고 search를 하는 informed search(=herustic search)에 대하여 알아봄.

  • heuristic

    • A fuction that estimates how close a state is to a goal
      ex) Manhattan dist, Euclidean dist.
      즉, 각 state가 goal까지 얼만큼 떨어져 있는지에 대한 적절한 "추측"을 바탕으로 방향성을 가진 탐색을 할 수 있는 것.
  • Greedy

    • Expand the node that seems closest to the goal.
      Dijkstra에서도 알 수 있듯, Greedy는 Complete하지도, Optimal 하지도 않음!
      그럼에도 Greedy를 설명한 이유는? Greedy의 장점은 속도에 있음.
      Whether or not this strategy could lead to complete or optimal option, still we can take advantage from the algorithm.
  • A* algorithm
    !!!

    UCS: Orders by path cost, or backward cost g(n).

    • 지금까지의 누적합을 최소화하는 선택.

    Greedy: Orders by goal proximity, or forward cost h(n).

    • 앞으로의 경로가 최소화 될 것 같은 선택.

    A* Algorithm : Orders by the sum! g(n) + h(n)

    • 두 가지의 장점을 합침.

    A*는 언제 끝나야 하나?
    단순히 Goal State가 Queue에 enqueue 되었다고 해서, 그 경로가 최단 경로는 아님.
    Goal State가 dequeue 될 때가 최단경로임!

    A*는 Optimal한가?
    Yes. with some condition -> future estimation is optimistic.
    만약, 어떤 future에 대한 cost를 너무 높게 측정한다면, 실제로 optimal했을 경로를 선택하지 못하는 문제가 발생할 수 있음.

    그럼 마냥 optimistic(=admissible)한 heuristic이면 어떤가?
    Still Optimal함. 다만 과하게 optimistic한 heuristic은 fringe의 수를 늘리면서 결과적으로 방향성 없는 UCS와 다를 바 없는 Search일 수 도 있음.

    0 <= h(n) - Heuristic function <= h*(n) - Actual Cost.

profile
성장하는 개발자

0개의 댓글