Taessing

nadir (어떤 순간에서) 최악의 상황, 바닥
nadir point


1. Introduction  nadir objective vector를 계산하기 위해서 f1, f2 들이 개별적으로 최대화되었을때, 각자 A와 B라는 포인트가 나올 수 있다. 이들 두가지 point가 extreme point zw라는것을 만든다. (그림에서는 Worst objective vector라고 나와 있다.) 이것은 실제 nadir point가 아니다. nadir point라는것은 모든 Pareto-optimal solution들 사이에서 가장나쁜 objective value들을 이용해서 만들어지는것이지, 전체 search space상에서 가장 나쁜 objective value들로 만들어 지는것이 아니다. 그러므로 nadir point를 찾기 위해서는, nadir point를 찾기위한 solution들의 Pareto-optimality를 알 수 있어야 한다. 이것이 nadir point를 찾는것을 보다 어렵게 만든다.

3. Existing Methods
이런 어려움을 극복하기 위해서, 여러가지 method들이 제안되었다. Benayoun et al. [1]-Linear programming with multiple objective functions: Step method (STEM). Mathematical Programming, -은 처음으로 interactive multi-objective optimization method를 소개했다. (저자가 nadir 이라는 용어를 쓰지는 않았지만) 이것은 nadir point를 추정하기 위해서 payoff table이라는 method를 이용을 했다. 이 method에서는 어떤 table이 구성이 된다. 그 테이블은 i번째 objective가 최소인 point에서 다른 모든 objective function의 값이 계산된 값이 table의 i번째 행으로 구성이 된다. 그런 다음에 i번째 열의 최대값은 i번째 objective의 upper bound의 추정값으로 할 수 있고 이들 최대값들은 함께 nadir vector를 구성하는데에 이용이 된다. 이런 접근방식에서 주로 문제가 되는것은 어떤 objective의 minimum solution에 상응하는것이 다른 objective에 서로 다른 값에 따라 하나 이상은 존재하게 되는 것이다. 특히 문제가 2개이상의 objective를 가질때 이야기이다. Figure2에 있는 전형적인 3개의 objective에 대한 Pareto-optimal front를 한번 살펴보자.
첫번째 objective function의 minimum value는 f1 = 0 일 때이다.  그림에서 봐서 알 수 있듯이 f1=0일 떄 f2와 f3이 각각 서로 다른 값을가지게 되는 수많은 solution들이 존재를 한다. (선 BC라인에 있는 모든 솔루션들이 그러하다.) payoff table method에 의해서, 다음의 세가지 solution이 나타날 수 있다. f(1) = (0, 0, 1)T => point C, f(2) = (1, 0, 0)T => Point A, f(3) = (0, 1, 0)T(point B), 즉 nadir point, znad = (1, 1, 1)T로 나타낼 수 있다. 하지만 solutions이  f(1) = (0, 0.2, 0.8)T, f(2) = (0.5, 0, 0.5)T 그리고 f(3) = (0.7, 0.3. 0)T (이것은 그림에서 하얀 동그라미로 표시가 되어있다) 와 같이 f1, f2, f3가 각각 minimization 되는 해를 찾았다면 이것의 nadir point는 z' = (0.7, 0.3, 0.8)T로 나타낼 수 있을것이다. 이 그림에서 잘못된 nadir point는 오직 Pareto-optimal front의 부분에서만 나타난다는것을 보여주고 있다. 

후에 Iserman 과 Steuer [9] - Computational experience concerning payoff tables and minimum criterion values over the efficient set - 에서는 linear problem 조차도 nadir point를 찾는데 어려움이 있다는 것을 증명했고 payoff table 보다 더 나은 method를 이용해야 한다고 강조를 했다. Dessouky et al. [7] - Estimates of the minimum nondominated criterion values in multiple-criteria decision-making.- 에서는 3가지의 heuristic method를 제안했고 Korhene et al. [10] - A heuristic for estimating nadir criterion values in multiple objective linear programming.- 에서는 nadir point를 찾기 위해서 또다른 method를 제안했다. 중요한 것은 이들 method 모두가 모든 objective들과 constraint들이 linear function인 multi-objective linear problem들을 위해서 제안 되었다는 것이다.

Ehrgott 와 Tenfelde-Podehl [8] - Computation of ideal and nadir values and implications for their use in MCDM
methods. - 에서는 subproblem에 기반을 둔 알고리즘을 제안했다. 즉, M-objective problem에서 nadir point를 찾기 위해서더 낮은 dimensional problem의 Pareto-optimal solution들을 이용했다. 이런 요구사항이 알고리즘을 objective가 3개 이상일 때는  계산적으로 실현 불가능하게 할수 도 있다. 더욱이 저자는 nonlinear problem에 대해서 확장할 수 있는 알고리즘을제안하지않았다. 비록 nadir point를 찾는것이 Pareto-optimal solution들의 set에서 가장 나쁜  objective value를 찾는 것이고, 이것이 linear problem에 적용하는 것이라 할 지라도 이것은 반드시 다루어져야 하는 내용이다. 이것은 또 한 매우 어려운 task이다. 

4. Evolutionary Approach
nadir point를 결정하는 것은 Pareto-optimal solution들과 관련이 있다 그 때문에 Pareto-optimal set의 결정에 대한 힌트를 주는것은 nadir point를 추정하는 것을 가능하게 한다. 과거 십수년전에는 EMO 알고리즘은 그들의 multiple, wide spread 한 Pareto-optimal solution들을 한번의 simulation run동안에 동시에 찾을 수 있는 기능에 인기를 얻었다. 그들 알고리즘이 Pareto-optimal solution들의 set을 찾는것이기 때문에, EMO procedure는 nadir objective vector를 찾기 위한 이상적인 방법이라고 할 수 있다. 하지만 먼저 Pareto-optimal set을 찾고 다음에 set에서 nadir objective vector를 찾는  naive procedure는 딜레마를 야기시키는 듯 하다. 자 여기서 nadir objective vector의 목적에 대해서 상기시켜 보자. 그것은 objective들을 normalize해서 interactive multi-objective optimization algorithm을 이용해서 이상적인 Pareto-optimal solution을 찾는것이다. 하지만 EMO가 대표적인 Pareto-optimal set을 찾는데 사용이 된다면 nadir point를 찾을 이유가 더 이상 없다는 것이다. 상호적인 의미에서는 EMO procedure의 application은  Pareto-optimal set의 본질에 대한 idea를 제공해줄 수 있고 차후에 이상적인 Pareto-optimal 지역을 위한 EMO procedure가 nadir point 기반을 한 interactive method들과 같다고 정할 수 있을것이다. 

유저가 그룹단위일때 어떻게 할것인가?

설계문서

기존연구논문

중간 보고 내용

문제 분석 및 학습 결과 보고

- 컨테이너, 크레인 환경 분석

- 고려해야할 사항(크레인 간섭 확률, 크레인 작업용이성, 컨테이너 그룹, 높이)

- 등등...

stacking strategy를 선택하고 학습한 내용과 의문점을 발표.

회피 방지의 모듈 제공 여부 확인,

가정
(
크레인이 선석까지 움직이는 거리와 시간은 일정하다고 가정한다.

블록 정보 : 6단 9열 41베이

컨테이너의 정보 : 무게, 목적지, 컨테이너의 높이, 적하 시간, 출하 시간

크레인(2대) 정보 : 현재 작업중인 컨테이너, 앞으로의 작업 일정, 현재 위치정보, 생산성(box/hour)
opt)속도, 가속도
)

설계 내용 보고

GUI, 시뮬레이션 엔진, 실험 데이터 , 장치위치 결정전략, 크레인간섭회피(불확실)

각각의 모듈에 어떤 요소가 있을지 분석을 한다.(알고리즘, 어떤데이터가 들어갈 것인가)

GUI의경우 프로토 타입 제작.

 

hared memory와 semapore를 사용하여 데이터를 공동관리 하는 두개이상의 프로세스로 구성된 프로그램을 작성하시오
(예 : 계산담당 프로세스와 디스플레이 담당 프로세스)


이과제를 해결하기 위해서 shared memory와 semapore에 대해서 확실히 알고 넘어가야한다.

먼제 세마포어(semapores)에 대해서 알고 넘어가도록 하자.


Semaphores
세마포어
A counter used to provide access to a shared data object for multiple process.
세마포어란 여러 프로세스가 공유된 데이터를 Access 할 수 있게 하는 Counter이다.

To obtain a shared resource a process
프로세스가 공유된 자원을 얻기 위해서는
1.Test the semaphore that controls the resource
세마포어를 테스트 해봐야하는데 그것은 리소스를 컨트롤 한다.
2. If the value of the semaphore is positive, the process can use the resource
세마포어의 값이 양수(positive)이면 프로세스는 자원을 이용할 수 있다.
-The process decrement the semaphore value by 1, indicating that it has used one unit of the resource.
프로세스는 세마포어의 값을 1을 감소시킨다, 그것은 리소스의 하나의 unit을 이용했다는것을 나타낸다.
3.If the value of the semaphore is 0, the process goes to sleep until the semaphore value is greater than 0
만약 세마포어 값이 0이라면 프로세스는 세마포어의 값이 0보다 커질때까지 슬립을 한다.
-When the process wakes up, it returns to sleep
프로세스가 깨어나면 그것은 슬립을 리턴시킨다.

To implement semaphores correctly,
세마포어를 올바르게 구현하려면
The test of a semaphore’s value and the decrementing of this value must be an atomic operation.
세마포어의 값의 테스트와 이값의 감소가 atomic operation이어야 한다.
For this reason, semaphores are normally implemented inside the kernel.
이런 연유로 세마포어는 커널 안에서 일반적으로 구현이 된다.


이론적 형태의 세마포어

-네덜란드의 이론가 E.W.Dijkstra가 프로세스의 동기화 해결책으로 제안
-세마포어 (sem)은 다음과 같이 연산이 허용되는 정수형 변수

p(sem) or wait(sem)
if (sem != 0)
    decrement sem by one
else
    wait until sem becomes non-zero

v(sem) or signal(sem)
if (queue of waiting processes not empty)
restart first process in wait queue
else
increment sem by one

-두 연산은 모두 atomic operations
`sem을 변경할 수 있는 프로세스는 한 순간에 오직 하나뿐이다.

세마포어의 좋은점: 세마포어의 불변특성 (unvariant)
-(semaphore’s initial value + number of v operations – number of completed p operations) >= 0
세마포어는 다방면으로 사용될 수 있다.
-가장 단순한 경우는 프로그램의 특정한 부분을 수행하는 프로세스가 한 순간에 오직 하나만 존재하도록 하는 mutual exclusion (상호배제)를 보장.

-예제:
(number of completed p operations – number of v operations) <= initial value of semaphore sem의 초기값이 1이면
(number of completed p operations – number of v operations) <= 1
즉 P와 V사이에 있는 문장들은 한 순간에 오직 하나의 프로세스에 의해서만 수행된다.

이런 이론으로 Unix에는 세마포어가 구현이 되어 있다. 유닉스에 세마포어 시스템 호출은 어떻게 이루어지는지 한번 살표보도록 하자. 커널에서는 세마포어를 위한 스트럭처를 이용하여 세마포어를 관리하게 된다. 이때 사용하는 스트럭처가 다음의 smid_ds이다.

struct semid_ds{
  struct ipc_perm sem_perm; //세마포어에 대한 접근권한
  struct sem *sem_base; /* ptr to first semaphore */
  ushort sem_nsems;     /* # of semaphores in set */
  time_t sem_otime;     /* last-semop() time *///마지막으로 세마포어와 관련된 작업을 수행하는 시간
  time_t sem_ctime;     /* last-change time *///마지막으로 스트럭처의 데이터들이 업데이트 된 시간
};

(1) 주어진 파일을 Copy 하는 프로그램을 작성하되, copy 중 SIGINT 와 SIGQUIT을 받아도 죽지않고 COPY를 모두 마치닣후 종료하는 프로그램을 작성하라.

주어진 파일을 카피하는 과정이야 어떤 파일명을 받아서 그파일을 바이너리로 읽어 그대로 다른 파일명으로 써주면 된다. 쉽게 할 수 있는 과정인데 이꽈제는 SIGINT 와 SIGQUIT의 기능을 먼저 이해를 해야 한다.

유닉스에서는 signal.h 헤더파일에 정의된 시그널 이름들이 있는데 그중에 SIGINT, SIGQUIT이 있다

#define SIGINT : 인터럽트를 위한 시그널로 유저가 인터럽트를 발생시키는 키를 입력했을 때 그와연결된 프로세스에세 커널이 보내는 시그널이다. 이 시그널은 프로세스를 종요할 때 많이 사용되는 시그널이다.이것은 터미널에서 ctrl+c와 같은 역활을 한다.

#define SIGQUIT : Quit를 위한 시그널로 유저가 터미널에서 Quit키를 치면 커널이 프로세스에게 SIGQUIT 시그널을 보낸다. 

그러면 C언어상에서 이들 시그널을 어떻게 이용을하는가 하는것에 대한 궁금증이 생길텐데 한번 예제코드를 이용해서 살펴보도록하자.

signal()이라는 함수가 있는데 이 함수는 이름그대로 시그널을 처리하는 함수 이다. signal 함수는 다음과 같이 나타낼 수 있다.

int sigkind; int function(); signal(sigKind, function);

여기서 sigKind에 바로 SIGINT, SIGQUIT같은 것이 들어가는것이다.
그리고 function은 sigKind의 함수가 호출 되었을때 실행되는 함수 이다.

이제 이 signal함수를 이용해서 간단한 코드를 작성해 보자

 

#include<stdio.h> #include<signal.h> int handler() { //필요한 작업을 처리한후에 프로그램을 종요한다. printf("\n\nSIGINT 핸들러 호출\n"); printf("\n<<작업 종료 시작>>>\n"); sleep(1); printf("\n\n실행되는 모든 프로세스 종료\n\n"); printf("All open file closed\n\n\n"); exit(1); } int main() { int result, step =0; //signal 함수를 사용하여 SIGINT 핸들러와 SIGQUIT핸들러를 등록한다. printf("signal 함수를 사용하여 SIGINT 핸들러를 SIGQUIT핸들러를 등록한다.\n\n"); result = signal(SIGINT, handler); result = signal(SIGQUIT, handler); //무한루프 프로그램을 돌린다. printf("메인 프로세스 실행.\n"); while(1) { step++; printf("%d 번째 작업 수행\n", step); sleep(1); } return 1; }

위의 코드를 실행하면 무한 루프대로 작업수행 메시지가 뜰것이고 시그널이 들어오면 핸들러 함수가 동작 하고 프로그램이 종료가 될 것이다. 실행을 시켜보자. 프로그램 실행도중 ctrl + c 또는 ctrl + \ 키를 눌러보자.

ktss1023@ktss1023-desktop:~/바탕화면$ ./a.out signal 함수를 사용하여 SIGINT 핸들러를 SIGQUIT핸들러를 등록한다.   메인 프로세스 실행. 1 번째 작업 수행 2 번째 작업 수행 3 번째 작업 수행 SIGINT 핸들러 호출 <<작업 종료 시작>>> 실행되는 모든 프로세스 종료 All open file closed

다음과 같이 잘 실행이 될 것이다.

그런데 이것으로는 과제의 내용에 합당하는 문제를 풀수가 없다. 그러면 어떤 시그널이 들어올때 그시그널을 미리 block을 시킬수 있는 함수가 있다면 좋을 것이다. 바로 그것이 문제를 해결 하기위한 함수이다. 어떤함수가 있는지 한번 살펴 보자.

int sigemptyset(sigset_t * set)

set 이 가리키고 있는 시그널 집합을 초기화 한다.

성공시에 0을 return 하고, 실패시에 -1을 return 한다.

int sigaddset(sigset_t * set, int signum)

set 이 가리키고 있는 시그널 집합에 signum을 추가한다.

성공시에 0을 return 하고, 실패시에 -1을 return 한다.

int sigdelset(sigset_t * set, int signum)

set 이 가리키고 있는 시그널 집합에 signum을 삭제한다.

성공시에 0을 return 하고, 실패시에 -1을 return 한다.

int sigprocmask(int how, const sigset_t * set, sigset_t * oldset)

시그널 마스크를 검사하고 변경하기 위해서 사용된다. 간단히 말해서 해당 시그널에 대해서

BLOCK, UNBLOCK 를 하기 위해서 사용한다.

 

how option

SIG_BLOCK

새로운 시그널 마스크는 현재의 시그널 마스크와 set에 의해 지정된 시그널 마스크의 합집합이다.

즉, set는 블록 시키고자 하는 추가적인 시그널들을 포함한다.

SIG_UNBLOCK

새로운 시그널 마스크는 현재의 시그널 마스크와 set로 지정된 시그널 마스크의 보수의 교집합이다.

즉, set는 블럭에서 해제시킬 시그널들을 포함한다.

SIG_SETMASK

새로운 시그널 마스크는 set로 지정된 시그널 마스크이다.

시그널 마스크를 변경하였다가 이전 시그널 마스크로 복귀시키고자 할 때, 원래의 시그널 마스크를

저장하였다가 SIG_SETMASK 옵션을 사용해야 한다. 

sigprocmask 는 성공시에 0을 return 하고, 실패시에 -1을 return 한다.

바로 이런 함수이다. sigset_t * set 집합을 하나 선언하고 집합에 SIGINT, SIGQUIT을 추가 한뒤int sigprocmask(int how, const sigset_t * set, sigset_t * oldset) 함수를 이용해서 SIG_BLOCK을 해주면 된다.

문제를 풀기 전에 이 함수를 이용해서 아까의 프로그램을 약간 변형하는 형태의 프로그램을 작성해보자.

 

#include<stdio.h> #include<signal.h> int main(void) { int result, step =0; sigset_t* set, oldset, pendset;//BLOCK할 signal set의 변수를 선언, //셋을 초기화 시킨다. if(sigemptyset(&set)<0) { printf("sigemptyset error\n"); exit(1); } //블록할 시그널 등록 if(sigaddset(&set, SIGINT)<0) { printf("sigaddset error\n"); exit(1); } //블록할 시그널 등록 if(sigaddset(&set, SIGQUIT)<0) { printf("sigaddset error\n"); exit(1); } //시그널 블록을 해준다. printf("시그널 블록 시작\n\n"); printf("5초만기다려봐\n"); if(sigprocmask(SIG_BLOCK, &set, &oldset)<0) { printf("블록 에러"); exit(1); } sleep(5); if(sigpending(&pendset)<0) { printf("sigpending error"); exit(1); } if(sigismember(&pendset, SIGINT)||sigismember(&pendset, SIGQUIT)) { printf("작업이 진행중이다.\n"); } //무한루프 프로그램을 돌린다. printf("메인 프로세스 실행.\n"); while(1) { step++; printf("%d 번째 작업 수행\n", step); sleep(1); if(step==20)break; } if(sigprocmask(SIG_SETMASK, &oldset, NULL) <0) { printf("unblock error"); exit(1); } printf("SIGQUIT,SIGINT가 언블록되었다\n\n"); return; }

위의 프로그램은 처음 5초간 기다리면서 신호를 받아 그신호가 SIGINT, SIGQUIT이면 메시지를 출력할려고 그랬는데 이걸지속적으로 할려면 타이머나 스레드를 돌려서 해야 될 듯 하다. 그리고 sigprocmask 함수를 이용해서 SIGINT,SIGQUIT의 신호를 막았다. 그러므로 실행하면 작업이 끝나기전에는 신호가 블록이 되어 동작하지 않는다.
자 그렇다면 이제 위를 토대로 문제를 해결하면 된다. 작업에 파일을 복사하는 작업을 하면 되는것이다. 처음에 폴더내에있는 파일명들을 출력해주고 파일명을 입력 받고 복사해주면 되는 형식으로 작성을 해보자.

#include<stdio.h> #include<signal.h> #include<fcntl.h> #define LENGTH 256 static void sig_int(int); int main() { char filename[LENGTH];//파일이름은 100자를 초과할 수 없다. char c_filename[LENGTH];//복사할 파일 이름 char buf[LENGTH];//버퍼 int result= 0; int readCnt, writeCnt, orgFile, newFile; sigset_t* set,oldset;//BLOCK할 signal set의 변수를 선언,     //복사할 파일 오픈 printf("복사할 파일 이름을 입력하시오 : "); scanf("%s",filename); orgFile = open(filename, O_RDONLY); if(orgFile<0) {     printf("없는 파일입니다.\n");     return -1; } //복사 당할 파일 생성 printf("생성할 파일 이름을 입력하시오 : "); scanf("%s",c_filename); newFile = open(c_filename, O_WRONLY|O_CREAT|O_APPEND); if (signal(SIGINT, sig_int) == SIG_ERR) { printf("signal error\n"); return -1; } if (signal(SIGQUIT, sig_int) == SIG_ERR) { printf("signal error\n"); return -1; } //셋을 초기화 시킨다. if(sigemptyset(&set)<0) { printf("sigemptyset error\n"); return -1; } //블록할 시그널 등록 if(sigaddset(&set, SIGINT)<0) { printf("sigaddset error\n"); return -1; } //블록할 시그널 등록 if(sigaddset(&set, SIGQUIT)<0) { printf("sigaddset error\n"); return -1; } //시그널 블록을 해준다. /* sleep(5); if(sigpending(&pendset)<0) { printf("sigpending error"); exit(1); } if(sigismember(&pendset, SIGINT)||sigismember(&pendset, SIGQUIT)) { printf("작업이 진행중이다.\n"); } */ printf("시그널 블록 시작\n\n"); if(sigprocmask(SIG_BLOCK, &set, &oldset)<0) { printf("블록 에러"); return -1; } //프로그램을 돌린다. printf("복사 시작!\n"); for(readCnt=1;readCnt>0;) {     readCnt = read(orgFile, buf, LENGTH);     writeCnt = write(newFile, buf, LENGTH);          /*     step++;     if(step%2==0)     {         printf("1초만쉬어요.\n");         sleep(1);     } */     printf("%d, %d\n", readCnt, writeCnt); } printf("SIGQUIT,SIGINT가 언블록되었다\n\n"); } printf("복사끝\n"); close(orgFile); close(newFile); if(sigprocmask(SIG_SETMASK, &oldset, NULL) <0) { printf("unblock error"); return -1; } static void sig_int(int signo) {     printf("신호확인\n");     return; }

하지만 이코드로는 왠일인지 파일 복사가 진행이 되지 않는다. 대체 무슨 연유일까? 이것만으로는 해결하기가 어렵다는 결론으로 sigaction이라는 함수를 찾아 보았다.

sigaction()

sigaction은 시그널을 취급할 방법을 선택 할 수 있다.

헤더파일

#include <signal.h>

원형

int sigaction(int signo, const struct sigaction *act, struct sigaction *oact);

인자

첫번째 : 행동을 지정할 개개의 시그널

두번째 : 지정하고 싶은 행동

세번째 : 나중에 복구를 위해 현재 값을 저장한다.

다음과 같이 시그널의을 취급하는 방법을 선택하는 함수이라고 하는데.
일단, sigaction 구조체에 대해서도 알아봐야 할 것이다.

struct sigaction {
    void (*sa_handler)(int);
    void (*sa_sigaction)(int, siginfo_t *, void *);
    sigset_t sa_mask;
    int sa_flags;
    void (*sa_restorer)(void);
}
sa_handler

signum번호를 가지는 시그널이 발생했을 때 실행된 함수를 설치한다. 함수외에도 SIG_DFL과 SIG_IGN을 지정할 수 있다. 전자는 시그널에 대한 기본행동을 후자는 시그널을 무시하기 위해서 사용한다.

sa_mask 

sa_handler에 등록된 시그널 핸들러 함수가 실행되는 동안 블럭되어야 하는 시그널의 마스크를 제공한다. SA_NOMASK가 적용되어 있지 않다면

sa_flags 

시그널 처리 프로세스의 행위를 수정하는 일련의 플래그들을 명시한다. 다음중 하나 이상의 것들에 의해서 만들어 진다.

SA_NOCLDSTOP 

만약 signum이 SIGCHLD라면, 자식 프로세스가 SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU등을 받아서 중단되었을 때 이를 통지 받을 수 없게 된다.

SA_ONESHOT, SA_RESETHAND

일단 시그널 처리기가 호출되면, 기본 상태에 대한 시그널 액션을 재 저장한다. 이는 signal(2)호출에 대한 기본 행위이다.

SA_RESTART 

일부 시스템 호출들이 시그널을 통해 재시작할 수 있도록 함으로서 BSD 시그널과 호환되도록 한다.

SA_NOMASK, SA_NODEFER

시그널이 자체 시그널 처리기로부터 수신 받지 않도록 한다.

SA_SIGINFO 

시그널 처리기가 하나가 아닌 3개의 인자를 취할경우 sa_handler대신 sigaction의 siginfo_t를 이용할 수 있다. siginto_t는 다음과 같이 정의된 구조체이다.

[

 

다음과 같은 구조체를 지니는데 각구조체의 역확은 예제 코드에서 알아보자.

------------------------------------------------------- ---------------------test.c---------------------------- ------------------------------------------------------- //sigaction() 사용하기 //시그널을 취급할 방법을 선택할 수 있다. #include <stdio.h> #include <signal.h> //sigaction() int main(void) {  static struct sigaction act; //행동을 지정할 구조체  void catchint(int); //행동할 함수(함수를 바꿈으로 인터럽트시 행동을 조절 할 수 있다.)  act.sa_handler = catchint; //구조체 변수에 취해질 행동을 지정한다.    sigfillset(&(act.sa_mask)); //시그널을 포함하도록 집합을 완전 채운다.(?)    //SIGINT : 인터럽트를 프로세스에게 보낸다.  //&act 지정된 행동  //현재값은 0으로(나중에 복구하기 위해 지정할 수 있다.)  sigaction(SIGINT, &act, NULL);    //프로세스 실행  printf("sleep call #1\n"); sleep(5);  printf("sleep call #2\n"); sleep(5);  printf("sleep call #3\n"); sleep(5);  printf("sleep call #4\n"); sleep(5);  printf("Exlting\n");  exit(0); } //실행 함수 //인터럽트를 칠때 커널에 의해 프로세스에게 보내진다. void catchint(int signo) {  printf("\nCATCHINT : signo = %d\n", signo);  printf("CATCHINT : returning\n\n"); } ==================================================================

다른 블로그의 글을 퍼온 코드인데 이해 하기가 쉬울것이다. 그러니까 sigaction은 signal 함수를 좀더 발전? 시킨것이다. 이를 토대로 코드를 한번 작성해보자.

#include<stdio.h> #include<signal.h> #include<fcntl.h> #include<stdlib.h> #define LENGTH 256 void sigcatch(int); //행동할 함수(함수를 바꿈으로 인터럽트시 행동을 조절 할 수 있다.) int main(void) {     char filename[LENGTH];//파일이름은 100자를 초과할 수 없다.     char c_filename[LENGTH];//복사할 파일 이름     char buf[LENGTH];//버퍼     int result= 0;     int readCnt, writeCnt, orgFile, newFile;     static struct sigaction act; //행동을 지정할 구조체          act.sa_handler = sigcatch; //구조체 변수에 취해질 해동을 지정한다.       sigfillset(&(act.sa_mask)); //sigaction 구조체의 sigset을 모든 신호를 다 채운다.     //이는 sigaddset함수를 이용해 SIGINT 와 SIGQUIT만 선택해도 된다.     act.sa_flags = 0;         //SIGINT : 인터럽트를 프로세스에게 보낸다.     //&act 지정된 행동     //현재값은 0으로(나중에 복구하기 위해 지정할 수 있다.)     if(sigaction(SIGINT, &act, NULL)==-1)     {         perror("sigaction error\n");     }     if(sigaction(SIGQUIT, &act, NULL)==-1)     {         perror("sigaction error\n");     }     //위     //복사할 파일 오픈     printf("복사할 파일 이름을 입력하시오 : ");     scanf("%s",filename);     orgFile = open(filename, O_RDONLY);          if(orgFile<0)     {         printf("없는 파일입니다.\n");         return -1;     }          //복사 당할 파일 생성     printf("생성할 파일 이름을 입력하시오 : ");     scanf("%s",c_filename);     newFile = open(c_filename, O_WRONLY|O_CREAT|O_APPEND);     //프로그램을 돌린다.     printf("복사 시작!\n");     for(readCnt=1;readCnt>0;)     {         readCnt = read(orgFile, buf, LENGTH);         writeCnt = write(newFile, buf, LENGTH);                 /*              step++;             if(step%2==0)             {                 printf("1초만쉬어요.\n");                 sleep(1);             }         */         printf("%d, %d\n", readCnt, writeCnt);          }     printf("복사끝\n");     close(orgFile);     close(newFile); } //실행 함수 //인터럽트를 칠때 커널에 의해 프로세스에게 보내진다. void sigcatch(int signo) {  printf("\nsigno = %d 신호가 들어왔습니다.\n", signo);  printf("파일 복사가 진행중입니다.\n\n"); }

단순히 텍스트 파일 복사를 시험하였고 복사가 빨리 진행되므로 255바이트 마다 1초간 sleep함수를 실행했다.
결과는

(2) alram()과 SIGALRAM을 사용하여 timeout을 가지고 file을 read하는 함수를 작성하시오.

일단 alarm()과 SIGALRM에 대해서 알아 보아야 할것이다. 우선 alarm함수는 시그널을 전달하기 위해서 사용하는 함수로 전달되는 시그널이 SIGALRM이다.

alarm 은 seconds 초 후에 프로세스에 SIGALRM 을 전달한다. 만약 seconds 가 0이라면 결코SIGALRM 이 전달되지 않을것이다. 만약 alarm 이 여러개 쓰인다면 기존에 설정되었던 alarm 설정값은 취소되고가정최근의 alarm 설정값으로 지정된다.

그러므로 alarm 을 사용할때는 alarm 이 겹치지 않도록 주의해야 한다.

SIGALRM 의 기본 행동은 프로세스 종료이다.

이렇게 나와 있는 예제프로그램을 한번 보자.

#include <unistd.h> #include <signal.h> void myalarm() {     printf("ding dong dang\n"); } int main() {     printf("alarm setting\n");     // SIGALRM 이 발생하면 myalarm() 함수를 실행한다.     signal(SIGALRM, myalarm);     // 알람을 1초로 설정한다.     alarm(1);     while(1)     {         printf("ok\n");         // 신호를 기다린다.         pause();         // alarm 을 2초로 설정한다.         alarm(2);     } }

다음과 같이 signal 함수를 이용해서 SIGALRM이 발생할 경우 myalarm함수가 발생하도록 했다.
위코드를 토대로 타임아웃을 주는 파일을 리드하는 프로그램을 작성하자. 읽은 파일은 화면에 출력하는것으로 한다.

#include <unistd.h> #include <signal.h> #include <stdlib.h> #include <stdio.h> void myalarm() {     printf("\n파일리드를 종료합니다.\n");     exit(0); } int main() {     FILE *fp;//리드할 파일포인터     char f_name[200];//파일이름     char buf;//1바이트짜리 버퍼     int limit;//alarm의 수를 결정     printf("읽을 파일이름을 입력하세요 : ");     scanf("%s",f_name);          if(!(fp = fopen(f_name,"r")))     {         printf("파일이 잘못되었습니다.\n");     return -1;     }         printf("몇초후 타임아웃하실건가요 : ");     scanf("%d",&limit);     signal(SIGALRM, myalarm);          alarm(limit);     printf("alarm setting\n");     // SIGALRM 이 발생하면 myalarm() 함수를 실행한다.         while(!feof(fp))//파일은 1바이트씩 읽고 출력한다.     {         printf("%c",fgetc(fp));         sleep(1);     }     return 0;     }

위 프로그램은 미리 alram을 설정하고 그동안 1바이트씩을 읽고 출력한뒤 sleep(1)을해주는 프로그램으로 20초동안만 파일을읽고 출력이 된다.

 

 

 

줄여서 약자 CSP 이야 이번장 부터는 문제를 이용해서 이론을 도출하는 식으로 한번 공부를 해볼려고 한다.

먼저 기본적인 개념을 잡고 가자
우선 Constraint satisfaction problems(CSP) 문제를 푸는데 있어서 어떤 제약을 만족해야 되는 그런 문제를 말한다.

state는 Variable Xi 로 나타내고, domain Di 에서 오는 value 값을 지닌다.
goal테스트를 만족하기 위해서 set of constarint를 만족 하여야 한다.

이것을 간단히 Map-coloring 예제로 나타내면 다음 그리과 같다.

다음과 같이 Varialble은 지도의 지역들 지역들이 가지는 색깔값들은 domain Di에서 오게 되고 Constraint는 위와 adjacent 하는 지역은 다른 컬러를 지녀야 한다는 것이다.


1. 강의록 12 ~ 13 페이지에 소개된 backtracking search를 이용하여 4-queens problem을 풀면 어떻게 될지 강의록 17 페이지에 보인 것과 같은 형태로 그려보라.

먼저 backtracking search가 어떻게 돌아가는건지 한번 알아보도록 하자.

다음과 같이 Varialble은 지도의 지역들 지역들이 가지는 색깔값들은 domain Di에서 오게 되고 Constraint는 위와 adjacent 하는 지역은 다른 컬러를 지녀야 한다는 것이다. 이것을 토대로 이제 문제도 한번 풀어보자.

이런식으로 문제를 쉽게 풀 수 있다.

2. Backtracking search를 이용하여 graph coloring problem을 풀기 위해 most constrained variable과 most constraining variable 및 least constraining value heuristic을 모두 사용하면서 forward checking까지 적용하고자 핚다. 아래 graph의 node들에 {Blue, Green, Red}를 칠핛 경우 생성되는 search tree를 그려보라. 단, variable이나 value의 우선 순위가 같을 경우에는 그 이름의 alphabet 순을 따라 선택핚다.
이문제를 풀기위해서 백트래킹도 알아야 하겠지만 most contrained variable 과 most contraining variable, least constraining value heuristic, forward cheking 까지 알아야 한다.

most constrained variable
fewest legal value를 선택을 한다.

most constraining variable
영향을 제일 많이 주는 variable 부터 선택을 한다.

least constraning value
영향을 가장 적게 주는 value 부터 선택한다.
-> 남아 있는 variable중 fewest value 선택

forward cheking
어떤 variable 이든 더이상 legal value가 존재 하지 않으면 종료를 하는것이다. variable에 value를 assign 하면서 다른 남은 variable들에게 어떤 value가 assign될 수 있는지 항상 체크 하는것이다.


요렇게 푸는 것이다.

3. 위 2번 graph의 B에는 Red 그리고 F 에는 Green이 지정되어 있는 상태에서 forward checking과 arc consistency algorithm을 적용하고자 핚다. 교과서 Figure 5.7의 AC3 algorithm을 이용핛 경우 종료 시까지 총 몇 개의 arc가 처리되고 몇 개의 arc가 다시 queue로 insert되며 또핚 최종 결과는 어떻게 되는가? 단, queue에는 arc들이 다음과 같은 순서로 들어 있다고 가정핚다: AB, BA, AD, DA, AE, EA, BC, CB, BE, EB, CE, EC, CF, FC, DE, ED, EF, FE.

Arc consistency 가 뭔지를 알아야 한다.

본 포스팅은 부산대학교 정보컴퓨터 공학부 4학년 학생이 인공지능 수업을 들은 내용을 토대로 작성한 것입니다. 본 포스팅의 내용의 신빙성을 책임지지는 않습니다.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------
Informed Search Strategies

우리는 이전 내용에서 Searching에 의해서 문제를 해결하는 쉽게 이야기 해서 어떤 문제의 해답을 서치하는 몇가지 방법들을 살펴 보았다. 간단히 Review를 해본다면

먼저 중요한 용어 Fringe라는 용어가 있었다. Fringe는 Expand하기를 원하는Node들의 집합이다. 일반적으로 구현이 될때 queue로 구현이 된다. 그리고 Depth는 solution을 찾기위해 search를 할 때 만들어지는 Searching tree의 깊이, path cost는 한node에서 다른 node로 가는 비용이라 할 수 있다.

Breadth-first Search : 이건 같은 Depth의 fringe상에 있는 node들을 차례대로 expand 한다. Breadth가 먼저 즉 fringe들을 다 expand 하고 다음 Depth로 넘어간다.
Uniform Cost Search : depth의 수치보다 코스트의 수치로 프린지에 있는 노드를 선택해 expand한다.
Depth-first Search : 이건 Depth first, 즉 한쪽의 모든 Depth를 search 한다. 그다음 옆으로 이동한다.
Depth-limited Search : Depth-first에 limit를 준다.
Iterative Deeping Search : Depth-limited의 limit를 증가 시킨다.
Bidirectional Search : Start(initial) 과 Goal에서 동시에 뻐어 나온다. 그래서 제일 먼저 만나는것을 솔루션으로 한다.
이런것들을 알아 보았다. 위의 Searching 방법들의 성능을 비교한 것은 다음과 같다.

위의 전술들은 모두, Time과 space가 어떤 변수에 대해 exponential 하다. 이문제를 해결 하기 위해 이제 부터 우리는 Informed Search를 한번 배워 보자. 인공지능적인 요소는 여기서 부터 나오는 것이다.

먼저 이 Informed search strategies에는
Apply evaluation function to determine the order of the nodes in the queue.
평가 함수가 존재한다. 이평가함수는 큐속에 있는 노드들의 순위를 결정한다.
Evaluation function f(n):
바로 평가 함수 f(n) 파라미터는 어떤 한 노드 n 이다.
f(n) =distance through node n to the goal
노드 n부터 goal 까지의 distance, 즉 거리이지만 평가 값이라고 할 것이다.
Comes from problem-specific knowledge
problem-specific knowledge에서 이값을 도출할 수 있다.
Priority queue maintains the order of the fringe nodes.
프린지노드의 순서를 우선순위 큐로 결정할 수 있다.

Components of evaluation function:
그리고 평가함수의 구성요소를 살펴보자.
h(n):heuristic function
휴리스특 펑션 h(n)이 있다.
h(n) =estimated cost of the cheapest path from node n to the goal
이 h(n)은 노드 n에서 goal 까지 가장 짧은거리를 추측해보는건데 우리가 주로 보는 내용이 길찾기 이런게 많기 떄문에 f(n)은 노드 n에서 골까지의 직선거리로 추측하기도 하고 그런것이다.
g(n):path cost from the start node to n
이건 우리가 앞에서도 봤었던 시작 노드부터 노드 n 까지의 path cost이다.

만약 여기서 f(n) = h(n) 이라면 이건 단지 평가를 휴리스틱 함수로만 한것이다. 그리고 f(n) = g(n) 이라면 이것은 uniform cost search 이다 평가 기준이 path cost 이기 떄문이다.

이제 이 f(n)을 이용한 search 방법들에 대해서 알아보도록 하자.

Greedy best-fit search
일단 먼저 위의 그림은 루마니아의 지도인데. 오른쪽의 직선거리가 각 노드에서 Bucharest까지의 직선거리가 있다. 우리는 이것을 h(n), 휴리스틱 펑션값으로 이용을 할 것이다. Greedy best-fit search란 f(n)을 바로 휴리스틱 펑션만으로 판단하는 것이다.
즉 f(n) = h(n) 이렇게 되는 것이다. 이것을 바탕으로 Arad에서 Bucharest까지의 최단거리를 가지는 Path를 찾아 보자. 상당히 간단하다.

노드를 expansion하는 기준이 h가 가장 작은 노드이다. 즉 h값이 가장 작은 순서대로 queue에 들어 가있다고 생각하면 된다.
depth와 breadth에 전혀 관계가 없다.

Take the biggest bite possible the name “greedy search”
Greedy best-fit search는 가장 가능성이 큰것을 취한다. 이름이 그리디 서치이다.

Evaluation:
Neither optimal nor complete(cf: depth-first search)
이것은 옵티말 하지도 컴플리트하지도 않다.
Time and space complexity
Retains all nodes in memory
메모리안에 모든노드가 있다.
O(b^m), m:maximum depth of the search space
b의m승 오더가 적용이 되는데 m은 가장 깊은 depth 즉, 서치한트리에서 가장 깊은 depth값이다.
Good heuristic function can reduce the space and time complexity.
좋은 휴리스틱 펑션이 space와 time complexity를 줄일 수 있다.

이제 이것보다 약간 발전된 형태인 A* Search에 대해 알아보자.

A*Search
Minimizes the total estimated solution cost
추측된 총 솔루션 코스트를 최소화 시킨다.
Combination of greedy best-first search and uniform-cost search
A* 서치는 쉽게 이야기 해서 greedy best-fit 서치와 uniform-cost 서치의 콤비네이션 즉 합친거다
f(n) = g(n) + h(n)
그래서 평가함수 f(n)은 g(n)과 h(n)을 더한 결과가 된다.
g(n):path cost from the start node to n
h(n):estimated cost of the cheapest path from nto the goal
f(n):estimated cost of the cheapest solution through n
위의 설명은 저 위에서 수차례했으니 패스 바로 위의 지도에서 solution을 찾는 서치트리를 만들어보면

역시 위의 방법은 비슷하나 평가 함수에 g(n)이 들어오게 딘다.

Theorem:
이것에 Theorem에 대해서 보자.
A*using Tree-Search is optimal if h(n)never overestimates the cost to reach the goal. (Such an h(n)is called an admissible heuristic.)
A* 서치는 한가지 조건만 충족이 된다면 옵티말 하다. 바로 h(n)을 측정할때 h(n)이 실제보다 큰값으로만 측정 되지 않으면 된다.(이런 h(n)이 admissible heuristic이다.)

Proof :
Let C*be the cost of the optimal solution.
C*를 옵티말 솔루션의 코스트라고 하자
Suppose a suboptimal goal node G2 appears on the fringe. Then,
서브옵티말(옵티말하지는 않는다는것이다.) 골노드 G2가 프린지 상에 나타나게 된고 가정하자. 그러면
f(G2) = g(G2) + h(G2) = g(G2) > C*
G2에서 골까지 가는 평가 함수값 = 시작노드에서 G2까지의 path cost + G2에서 골까지의 h값  = g(G2) > C*
But, for a fringe node n that is on an optimal solution path
하지만 프린지 노드 n은 옵티말 솔루션 패스이므로
f(n) = g(n) + h(n) <= C*
이렇게 되고
Since f(n) <g(G2), G2 will not be expanded.
결구 f(n)< g(G2) 가 되고 G2가 expand가 되지 않는다. 역시 증명의 길은 어렵다는것을 꺠닫게 되는구나.

A*is optimal and complete.
A*는 옵티말 하고 컴플리트 하다. 단 h가 overestimate 하지않는다면 말이다.

Time and memory complexity:
Exponential time complexity
역시 exponential time complexity를 지니게 된다.
Perfect h->no search (practically impossible)
퍼펙트한 h -> 서치가 없게 되지 이건 불가능하다.
Exponential memory complexity
exponential한 메모리 complexity를 지니게 된다.

A*is optimally efficient for any given heuristics.
A*는 어떤 주어진 휴리스틱에도 옵티말하게 효율적이다.
Search is done efficiently by pruning the subtrees below the nodes with f(n) > C*.
서치는 서브트리를 가지치기 하면서 완료가 되는데 어떤서브티리이냐 하면 f(n) > C*것의 node 밑의 서브트리를 가지치기 한다.
No other optimal algorithm is guaranteed to expand fewer nodes than A*.
A*다 더적게 노드를 expand하는 옵티말 알고리즘은 없다.(이것이 중요하다.) 하지만 아직은 시간과 공간의 complexity가 부담이 된다. 좋은 휴리스틱 펑션을 찾는것이 필요하다. 그것은 유니폼 코스트 서치를 사용하는것보다 훨씬 더 좋게 된다는 말이 된다.
 
당연한 법칙 3가지를 소개 하면
Recall that f(n) = g(n) + h(n)
h= 0, uniform cost search g(n) -> path cost만을 이용해서 판단
g = 1, h= 0 breadth-first search -> 이것은 모든 노드를 차례대로 expand 해야한다. 판단기준이 모두 같기 때문에
g= 0 greedy best-first search -> 이것은 h(n)으로만 판단 하는 greedy best-fit 알고리즘과 같다.

이제 본격적으로 heuristic function에 대해서 알아보도록 하자.
8-puzzle problem을 예를 들어서 알아 보자.


h1= the number of tiles that are in the wrong position
h1 첫번쨰 휴리스틱은 잘못된 위치에 있는 타일의 개수이다.
h2= the sum of the distances of the tiles from their goal positions (Manhattan distance)
두번째 휴리스틱은 그들의 골포지션으로 부터 타일들의 거리의 총합이다. (맨하탄 디스턴스라고 한다.)
* Both are admissible: never overestimates
둘다 절대 overestimate 되지 않았다. h1같은 경우는 그러려니 싶지만 h2는 왜그런지 약간 헷갈릴 수도 있다. 이것은 타일들이 그위치에서 바로된 위치에서 거리보다도 그곳으로 실제로 가기위해서는 다른타일도 움직여야 하는 비용까지 더해지기 때문이다.

The total number of nodes expanded:
expand되는 노드의 총 개수는?
A*with effective branching factor b*(Figure 4.8)
브랜칭 팩터 b*r가 있다.
N= 1 + b* + (b*)^2+ (b*)^3+ … + (b*)^d, d :depth
요런식으로 expand 되는 노딍 총수를 구할수있다.

Dominating heuristic:
We say that h2 dominates h1 if for any node n,
h2가 h1을 어떤 노드 n에서든 dominate한다고 할 수 있는데
h2(n) >=  h1(n).
h2(n) >= h1(n)이기 떄문이 다.
It is always better to use a heuristic function with higher values, as long as it does not overestimates.
그러니까 정리를 하면 h값은 overestimate 되지않는 선에서 높은 값을 선택하는 것이 좋다.
그림에서 보게 되어도 h2가 depth가 커질수록 effective branching factor값이 더 많이 작아진다는 것을 알 수 있다.
그러므로 1 + b* + (b*)^2 + ..... + (b*)^d 인 expanded 노드의 총수 역시 작아진다는것을 알 수가 있다.

이제 좀더 확장된 주제로 넘어자 보자.
Inventing Admissible Heuristic Functions

Consider a relaxed problem:
relaxed problem에 대해서 생각해보자.
A relaxed problem is a problem with fewer restrictions on the action.
relaxed problem은 action에 있어서 제약이 더 없는 문제를 뜻한다.
The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.
relaxed problem에 대한 옵티말 솔루션의 코스트는 오리지널 문제에 대한 admissible 휴리스틱이다.
The optimal solution in the original problem is at least as expensive as the optimal solution in the relaxed problem. 
original problem에 있는 옵티말 솔루션은 적어도 relaxed problem에 있는 옵티말 솔루션과 비슷하게 expensive 할것이다.


8-puzzle의 예를 한번들어보자.
A tile can move from square Ato B if Ais horizontally or vertically adjacent to B and B is blank.
타일은 B가 비어있고 A와 수직또는 수평으로 근접할때 A에서 B로 이동이 가능하다.
 
Relaxed problems:
relaxed problem으로 생각하면
(a)A tile can move from square A to B if A is adjacent to B(h2)
A에 있는 타일은 A가 B에 adjacent할때 A에서 B로 이동이 가능하다 (h2)
(b)A tile can move from square A to B if B is blank.
A에 있는 타일은 B가 blank일떄 A에서 B로 이동이 가능하다.
(c)A tile can move from square A to B. (h1)
A에 있는 타일은 A에서 B로 이동이 가능하다. (h1)

Construction of a relaxed problem:
relaxed problem을 구축해보자.
Can be done automatically if a problem definition is written in a formal language
문제의 정의가 일반적인 언어로 쓸수 있다면 자동적으로 완료가 된다.

Trade off between accuracy and computation time:
정확도와 computation time을 trade off 한다.
It takes more time to derive more accurate heuristic.
좀더 정확한 휴리스틱은 더많은 시간을 소요할 것이다.

Using multiple admissible heuristics:
여러개의 admissible heuristic을 이용해보자
If a set of admissible heuristics h1,…, hm is available, and none of them dominates any of the others, we can use the
admissible 휴리스틱 h1,....의 집합이 있고 hm은 이용가능하며 그들중에 어떤것도 다른것을 dominate 하지 않는다. 
heuristic most accurate on the node in question:
휴리스틱은 어떤 노드에서 가장 정확한 휴리스틱을 선택하면 된다.
h(n) = max{h1(n),…, hm(n)}
그러므로 h(n)은 h1(n),......,hm(n)에서 가장 큰값을 선택하는것이다. 어짜피 집합은 admissible 한 휴리스틱이기 떄문에.

Consider a subproblem:
subproblem에 대해서 생각해보자.
Admissible heuristics can also be derived from the solution cost of a subproblem.
Admissible 휴리스틱들은 또한 subproblem의 솔루션 코스트로 부터 이끌어 낼 수 도 있다.
Can be substantially more accurate than Manhattan distance in some cases
어떤경우에는 맨하탄 디스턴스 모다 훨씬 정확할 수도 있다.


Pattern databases:
패턴 데이터베이스
Store exact solution costs for every possible subproblem instance (every possible configuration of four tiles and
모든 가능한 subproblem instance(4개의 타일과 blank의 모든 가능한 설정)에 대한 모든 가능석에 대한 정확한 소루션 코스트들을 저장한다.
blanks).
The database is constructed by searching backwards from the goal state and recording the cost of each new pattern
데이터베이스는 골스테이트로 부터의 searching backwards와 각각 새로운 pattern encountered의 코스트의 레코딩에의해 구축이 된다.
encountered.
We could construct databases for 5-6-7-8, 2-4-6-8, and so on.
우리는 5-6-7-8, 2-4-6-8 등등으로 데이터 베이스를 만들수가 있다.
These heuristics can be combined by taking the maximum value.
이들 휴리스틱은 최대의 값을 combine 할 수 있다.
The number of nodes generated can be reduced by a factor of 1,000 when solving random 15-puzzles compared with
노드의 갯수는  15-puzzle 문제에서는 1000개의 팩터정도를 제거 할 수 있다. 이것은 맨하탄 디스턴스를 쓸때 비해서 이다. 패턴 데이터 베이스를 쓸때이다.
using Manhattan distance.


Disjoint pattern databases:
패턴 데이터 베이스 분리

Example:
예를 들어서
Construct 1-2-3-4 database and the 5-6-7-8 database.
1-2-3-4 데이터 베이스와 5-6-7-8 데이터베이스를 구축한다.
Record not the total cost of solving the subproblem 1-2-3-4 (5-6-7-8) but just the number of moves involving 1-2-3-4
(5-6-7-8).
subproblem을 solving한 코스트의 총합을 기록하는것이 아니지만 subproblem의 move의 수를 기록한다.
Use the sum of the two costs → still admissible
두개의 코스트의 합을 더해도 아직 admissible 하다.
The number of nodes generated can be reduced by a factor of 10,000when solving random 15-puzzles.
15-puzzle에서 10000개 팩터를 제거, 등 스피드 업이 있다.
A speedup of 1,000,000for 24-puzzles.
==========================================================================================================================
Learning Heuristics from Experience
경험에서 오는 러닝 휴리스틱
Optimal solutions to an 8-puzzle provide examples from which h(n)can be learned.
8-puzzle에 옵티말 솔루션은 h(n)이 배울수 있는데서 오는 예제를 제공한다.

State is described by a set of features
state는 튿징들에 의해서 설명될 수 있는데.
x1(n): # of misplaced tiles
x1(n)은 잘못배치된 타일들이다
x2(n): # of pairs of adjacent tiles also adjacent in the goal state
x2는 adjacent된 타일쌍들의 갯수이고 또한 골스테이트에 근접한것도 된다.
Then, derive a linear combination (find best fitting ci’s)
그러면 선형 조합에서
h(n) = c1x1(n) + c2x2(n)
위와 같은 식을 얻게 되는것이다.
------------------------------------------------------------------------------------------------정말애매하군.

Local search algorithm

In many problems, the path to the goal is irrelevant.
많은 문제들에서 골까지의 path는 irrelevant 하다.
Example: 8-queens problem
예를들어 8-queens problem이 있다.
Order of adding queens is irrelevant
queen을 추가하는 순서는 관계가 없다.

Neighborhood search:
이웃 서치
Local search algorithms operate using a single current state and move only to its neighbors.
local search 알고리은 single current state을 사용하고 오직 자신의 이웃에 이동할 때만 동작하게 되된다.
여기서 state란 바로 어떤 문제를 해결하기 위해서 진행이 될때 그상태 어떻게 진행 되었는지 상태 뭐이런것들이다.
Start with a complete configuration and make modifications to improve its quality
완벽한 설정과함께 시작하고 퀄러티를 향상시키기 위해서 변경을 한다.

Useful for solving optimization problems:
Find the best state according to the objective function.
목표하는 함수를 위한 가장 좋은 state를 찾는다.


Local search algorithm의 예를 보자 이것의 neighborhood configuration의 후보자들을 보면 서로 인접해있는 것들끼리 바꾸는것을 알수있다. 한번에 하나씩! 이제 이런느낌의 알고리즘을 보게 될것이다 그것이 바로 Hill-climbing search이다.

State space landscape
Location: state
기로 : 스테이트 스페이스
Elevation: heuristic cost function or objective function
세로 : 휴리스틱 혹은 오브젝티브 펑션,
어떤 스테이트에서의 휴리스틱펑션값이나 오브젝티브 펑션값이 높으면 높을 수록 좋다.



이런게 노올 수가 있다. 어떤 스테트에서 가장 높은 값을가지는 objective function값을 가지는것을 찾는 것이 궁국적인 목표이다. 하지만 그것은 힘들고 local maximum이라도 잘찾으면 나름 성공적인 서치가 될 것이다.

Hill-climbing Search
Also called as greedy local search:
그리디 로컬 서치라고도 불리는데 그러는걸 보면 로컬 서치 알고리즘이기는 한가 보다.
Continually moves in the direction of increasing value
계속적으로 값이 오르는쪽으로 이동을 하게 된다. 그래서 언덕을 오르는 서치라는 이름이 붙은것이다. 수도코드를 보면

function Hill-Climbing(problem) returnsa state that is a local maximum //로컬 맥시멈인 스테이트를 리턴하게 된다.
inputs: problem, a problem//인풋으로는 문제가 들어가고
local variables: current, a node//local variable로서 현재노드와