전공 공부/인공지능(Artificial Intelligence)

[인공지능] CSPs -2

7_JUN_7 2023. 10. 15. 03:25

Constraint Graphs

제약 그래프는 Constraint Satisfaction Problem (CSP)의 구조와 관계를 시각적으로 표현하는 데 사용되며, 이를 통해 문제의 복잡성과 구조를 더 잘 이해하고 해결할 수 있다.

  • Binary CSP
    • 각 제약 조건은 최대(at most) 두 변수와 관련된다. 이는 제약 조건이 두 변수 사이의 관계만을 정의한다는 것을 의미한다.
  • Binary Constraint Graph
    • 노드(node)는 변수(variable)를 나타내며, 호(arc)는 제약 조건을 나타낸다. 이 그래프는 변수 간의 제약 조건을 시각적으로 표현하는 도구로 사용됩니다.
  • General-Purpose CSP Algorithms
    • 일반 목적의 CSP 알고리즘은 그래프 구조(Graph structure)를 사용하여 검색을 가속화한다.
    • 예시) 타즈마니아(Tasmania =T)는 독립적인 부분 문제로 간주될 수 있다. 이는 타즈마니아와 관련된 변수와 제약 조건이 다른 지역과 독립적으로 해결될 수 있음을 의미한다.

Example: Sudoku

 Sudoku는 전형적인 Constraint Satisfaction Problem (CSP)의 예시로, 주어진 제약 조건을 만족하면서 게임판을 완성하는 것이 목표이다.

  • Variables
    • 각 (빈) 칸 ((open) square)을 나타냅니다. Sudoku 게임판은 9x9의 격자로 구성되어 있다.
  • Domains:
    • 각 칸에 들어갈 수 있는 숫자의 집합이다. , 각 칸에는 1부터 9까지의 숫자 중 하나가 들어간다. 즉,Sudoku에서는 {1,2,...,9}의 숫자 집합을 사용한다.
    • D={1,2,...,9}
  • Constraints
    • 9-way alldiff for each row: 각 행에는 1부터 9까지의 숫자가 중복 없이 한 번씩만 나타나야 한다.
    • 9-way alldiff for each column: 각 열에도 1부터 9까지의 숫자가 중복 없이 한 번씩만 나타나야 한다.
    • 9-way alldiff for each region: Sudoku 게임판은 3x3 크기의 9개의 작은 격자로 나뉘어져 있다. 각 작은 격자 내에서도 1부터 9까지의 숫자가 중복 없이 한 번씩만 나타나야 한다.
    • (or can have a bunch of pairwise inequality constraints): 이는 각 칸의 숫자가 서로 다르게 설정되어야 함을 나타내는 다른 방식의 제약 조건을 의미한다

Varieties of CSPs and Constraints

Varieties of CSPs 

  • Discrete Variables(이산 변수)
    • Finite Domains(유한 영역)
      • 크기(size) d는 O(d^n)의 완전한 할당을 의미한다. 여기서 d는 도메인의 크기이며, n은 변수의 수를 나타낸다.
      • 예: Boolean satisfiability (NP-complete)를 포함한 Boolean CSPs
    • Infinite Domains (무한 영역 : 정수, 문자열 등)
      • 예: job 스케줄링 - 변수는 각 직업(kob)의 시작/종료 시간이다.
      • 선형(linear) 제약 조건은 해결 가능(solvable)하며, 비선형(non-linear) 제약 조건은 결정 불가능(undeciable)하다.
  • Continuous Variables(연속 변수)
    • 예: 허블 망원경 관측의 시작/종료 시간과 같은 문제들
    • 선형(linear) 제약 조건은 LP 방법(LP Method)에 의해 다항 시간(polynomial time) 내에 해결 가능(solvable)하다.

Varieties of Constraints

  • Varieties of Constraints
    • Unary Constraints(단항 제약)
      • 단일 변수와 관련된 제약 조건입니다. 이는 도메인을 축소하는 것(reducing domain)과 동일(equivalent)하다.
      • 예시) SA != green
    • Binary Constraints(바이너리 제약)
      • 두 변수 간의 제약 조건이다.
      • 예시) SA != WA
    • Higher-Order Constraints
      • 3개 이상의 변수와 관련된 제약 조건이다.
      • 예시) cryptarithmetic 문제에서의 열(column) 제약 조건
  • Preferences (Soft Constraints) : 선호도 또는 부드러운 제약 조건
    • 예시) red is better than green : 'red' 색상이 'green' 색상보다 더 좋다는 것을 나타낸다.
    • 각 변수 할당에 대한 비용으로 종종(Often) 표현될 수 있다.
    • 이러한 제약 조건은 제약 최적화 문제(constrained optimization problem)를 생성한다.
    • (우리는 Bayes' nets에 대해 다룰 때까지 이러한 제약 조건은 일단 무시할 것이다.)

Real-World CSPs

실제 세계에서의 CSPs는 다양한 분야에서 발생하는 복잡한 문제들을 포함하며, 이러한 문제들은 특정 제약 조건 하에서 최적의 해결책을 찾는 것을 목표로 한다.

  • Scheduling Problems
    • 예: when can we all meet? ( 우리가 모두 만날 수 있는 시간은 언제일까? )
    • 여러 사람의 일정을 조정하여 모두가 만날 수 있는 시간을 찾는 문제이다.
  • Timetabling Problems
    • 예: which class is offered when and where? (어떤 수업이 언제 어디서 열리는가?)
    • 대학이나 학교에서 각 수업의 시간표를 설정하는 것과 관련된 문제이다.
  • Assignment Problems
    • 예: who teaches what class (누가 어떤 수업을 가르치는가?)
    • 교사와 수업 간의 매칭 문제를 포함합니다.
  • Hardware Configuration
    • 하드웨어 구성 요소를 최적화하거나 특정 목표를 달성하기 위해 설정하는 문제이다.
  • Transportation Scheduling
    • 교통 수단의 운행 일정을 최적화하는 문제이다.
  • Factory Scheduling
    • 공장의 생산 일정을 최적화하는 문제이다.
  • Circuit Layout
    • 전자 회로의 물리적 배치를 최적화하는 문제이다.
  • Fault Diagnosis
    • 시스템에서의 결함이나 오류를 진단하는 문제이다.
  • ...and lots more!
  • 많은 실세계 문제들은 실제 값을 가진 변수(real-valued varialbes)를 포함한다.
    • 이는 변수가 연속적인 값을 가질 수 있음을 의미한다.

Solving CSPs

Standard Search Formulation

  • Standard Search Formulation of CSPs
    • CSPs (Constraint Satisfaction Problems)의 표준 검색 형식화에 대해서 다룬다. 표준 검색 형식화는 CSPs를 해결하기 위한 기본적인 방법을 제공하며, 이를 통해 문제의 상태와 전환, 그리고 목표를 정의하고 이해할 수 있다.
  • States Defined by the Values Assigned So Far (Partial Assignments)
    • 현재까지 할당된 값에 의해 정의된 상태에 대해서 다룬다. 부분적으로 할당되었다고도 말한다.
    • Initial State: 빈(empty) 할당, {}으로 표현한다. 이는 아무런 변수에도 값이 할당되지 않은 초기 상태를 나타낸다.
    • Successor Function(후속 함수): 할당되지 않은 변수(unassigned variable)에 값을 할당한다.
    • Goal Test: 현재 할당(current assignment)이 모든 제약 조건을 만족하며(satisfied) 완전한(complete) 경우이다.
  • 우리는 우선 직접적(starightforward)이고 순진한(naiive) 접근 방식으로 시작하고, 이후에 그것을 개선해 볼 것이다.

Search Methods

  • BFS (Breadth-First Search)
    • BFS는 너비 우선 탐색 방식으로, 시작 노드에서 시작하여 가장 가까운 노드부터 탐색한다. 모든 인접한 노드를 방문한 후에는 그 다음 레벨의 노드를 방문한다.
    • BFS 방식으로는 이 그래프를 어떻게 탐색하는가?
  • DFS (Depth-First Search)
    • DFS는 깊이 우선 탐색 방식으로, 시작 노드에서 시작하여 먼저 가능한 깊게 노드를 탐색한다.
    • DFS 방식으로는 이 그래프를 어떻게 탐색하는가?
  • Naïve Search의 문제점
    • What problems does naïve search have? : naive한 탐색 방식은 어떤 문제점을 가지는가?
       
    • naive 검색 방식은 문제의 모든 가능한 해를 탐색하려고 시도한다. 이로 인해 탐색 공간이 매우 크거나 무한할 경우 비효율적이며, 많은 시간이 소요될 수 있다. 또한, naive 검색은 중복된 경로나 불필요한 경로를 탐색할 수 있어, 불필요한 계산을 수행할 가능성이 있다