[인공지능] 문제 표현 요약

2023. 10. 25. 19:54·Study/인공지능
상태공간이란?

초기 상태와 목표상태를 포함하여 임의의 상태로부터 연산자를 통해 생성 가능한 모든 상태들의 집합

 

상태공간 구성요소
  • 상태 묘사 형태 : 연산자 적용이 용이한 상태 묘사방식을 선택
  • 초기상태와 목표상태에 대한 묘사
  • 연산자의 종류

 

상태 묘사란?

다양한 형태의 자료 구조를 사용하여 문제의 상태를 표현하는 것

 

목표 상태 : 탐색과정이 끝났는가 하는 결정

  • 새로 생성된 상태묘사들이 목표상태를 묘사하고 있는지 검토하는 정합과정
  • 최적화 문제의 경우 최적해를 탐색하는 과정까지 수행

상태 공간 표현(방향성 그래프)

  • 상태공간에서 목표를 탐색하는데 유용
  • 노드 (node): 상태 묘사를 나타낸다.
  • 아크 (arc): 연산자를 표현
  • C(Ni, Nj ): 두 노드 사이의 경로에 드는 비용

 

문장 분석

초기 상태: abaab

연산자는 생성 규칙으로 정의하자.

  1. ($1)ab($2)→($2)S($2) :부분 스트링 ab는 문장을 나타내는 S로 대치될 수 있다.
  2. ($1)aS($2)→($1)S($2)
  3. ($1)Sb($2)→($1)S($2)
  4. ($1)SS($2)→($1)S($2)

abaab (1번규칙) → Saab (1번규칙) → SaS (2번규칙) → SS (4번규칙) → S

 

스키마: 변수에 따라 달라지는 상태들의 집합 또는 연산자들의 집합

스키마 변수: 변화 가능한 상태를 표현

 

원숭이와 바나나문제

어떤 방에 원숭이, 상자, 바나나가 있다.

상태묘사 : 리스트로 표현

  • w =원숭이의 수평위치(2차원 벡터)
  • x =원숭이가 상자의 위에 있는지(0 or 1)
  • y =상자의 수평위치(2차원 벡터)
  • z =원숭이가 바나나를 가졌는지(0 or 1)

스키마 (schema)를 이용한 연산자: 원숭이의 네 가지 행동 표현

  • goto(u):원숭이는 수평위치 (변수)로 간다.
  • pushbox(u) :원숭이는 수평위치 (변수)로 상자를 밀고 간다.
  • climb box:원숭이는 상자 위로 올라간다.
  • grasp(u) :원숭이는 바나나를 잡는다.

(w, 0, y, z) goto(u) → (u, 0, y, z)

(w, 0, w, z) pushbox(v) → (v, 0, v, z)

(w, 0, w, z) climbbox → (w, 1, w, z)

(c, 1, c, 0) grasp → (c, 1, c, 1)

 

원숭이와 바나나 문제 풀이

저작자표시 비영리 변경금지 (새창열림)

'Study > 인공지능' 카테고리의 다른 글

[인공지능] Monte Carlo Tree Search 요약  (2) 2023.10.26
[인공지능] Min-Max Algorithm 요약  (1) 2023.10.25
[인공지능] 탐색(Search) 요약  (0) 2023.10.25
[인공지능] 에이전트 요약  (0) 2023.10.25
[인공지능] 인공지능의 개요 요약  (1) 2023.10.24
'Study/인공지능' 카테고리의 다른 글
  • [인공지능] Min-Max Algorithm 요약
  • [인공지능] 탐색(Search) 요약
  • [인공지능] 에이전트 요약
  • [인공지능] 인공지능의 개요 요약
퀵차분
퀵차분
Web Developer 🥐
  • 퀵차분
    QC's Devlog
    퀵차분
  • 전체
    오늘
    어제
    • 분류 전체보기 (168)
      • Frontend (28)
        • HTML, CSS (7)
        • Javascript (3)
        • React (11)
        • Typescript (2)
        • Next.js (4)
      • Node.js (3)
      • Fedify (3)
      • Study (40)
        • Modern JS Deep Dive (13)
        • SQL (1)
        • Network (1)
        • 프롬프트 엔지니어링 (4)
        • 인공지능 (9)
        • 시스템프로그래밍 (11)
        • 선형대수학 (1)
      • Intern (4)
      • KUIT (20)
      • Algorithm (48)
        • Baekjoon(C++) (26)
        • Programmers(JavaScript) (22)
      • 우아한테크코스(프리코스) (4)
      • Project (7)
        • PROlog (4)
        • Nomadcoder (2)
      • 생각 (4)
      • Event (7)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    타입스크립트
    백준
    프롬프트 엔지니어링
    프로그래머스
    자바스크립트
    알고리즘
    react
    음악추천
    프로그래머스 자바스크립트
    next.js
    인공지능
    HTML
    프론트엔드
    티스토리챌린지
    리액트
    KUIT
    typescript
    오블완
    javascript
    시스템프로그래밍
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
퀵차분
[인공지능] 문제 표현 요약

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.