지능 알고리즘 (1) - 아 날로 그 소 둔, 에 세이 화 된 욕심

머리말
욕심 은 좋 은 알고리즘 인 데 안 타 깝 게 도 적용 범위 가 넓 지 않다.에 세이 화 는 아주 좋 은 알고리즘 인 데, 아 쉽게 도 정확도 가 높 지 않다.
만약 이 두 알고리즘 을 결합 한다 면 우 리 는 적용 범위 가 넓 고 정확도 가 높 은 알고리즘 을 얻 을 수 있 습 니까?
답 은 긍정 적 이다.
아 날로 그 소 둔 (S i m u l a t e d A n e a l i n g Simulated Annealing Simulated Annealing, 약칭 S A SA SA) 은 에 세이 화 와 욕심 이 결 합 된 알고리즘 으로 많은 어 려 운 문 제 를 쉽게 해결 할 수 있 습 니 다 (전 제 는 RP 가 좋 거나 데이터 범위 가 작 다 는 것 입 니 다).
고전적 인 이야기
지구 상에 서 가장 높 은 산 을 찾기 위해 패기 있 는 토끼 들 이 방법 을 생각 하기 시작 했다.

토끼 는 지금 보다 높 은 곳 으로 뛰 어 갔다.그들 은 멀 지 않 은 곳 에서 가장 높 은 산 봉 우 리 를 찾 았 다.하지만 이 산 이 꼭 에 베 레 스 트 산 은 아니다.이것 이 바로 등산 알고리즘 이다. 국부 최 우수 치가 전역 최 우수 치 라 는 것 을 보장 할 수 없다.

토끼 가 술 에 취 했다.그 는 랜 덤 으로 오랫동안 뛰 었 다.그 사이 높 은 곳 으로 올 라 갈 수도 있 고 평지 로 발 을 들 여 놓 을 수도 있다.하지만 점점 깨 어 나 가장 높 은 방향 으로 뛰 어 내 렸 다.이것 이 바로 시 뮬 레이 션 퇴화 다.

토끼 들 은 토끼 의 힘 이 보잘것없다 는 것 을 안다.그들 은 어디 산 을 찾 았 는 지, 그리고 찾 았 던 모든 산 에 토끼 한 마 리 를 남 겨 표 시 를 했다 고 서로 전 했다.그들 은 다음 단계 에 어디로 가 야 할 지 전략 을 세 웠 다.이것 이 금기 수색 이다.

토끼 들 은 기억 상실 알약 을 먹고 우주 로 발사 되 어 무 작위 로 지구 상에 떨 어 졌 다.그들 은 자신의 사명 이 무엇 인지 모른다.하지만 몇 년 이 지나 면 해발 이 낮은 토끼 의 일 부 를 죽 이면 다산 토끼 들 은 스스로 에 베 레 스 트 봉 을 찾 을 수 있다.이것 이 바로 유전 알고리즘 이다.

그 중 두 번 째 부분 은 시 뮬 레이 션 퇴화 를 말한다.
의 원리
물리학 적 으로 금속 이 퇴화 하 는 과정 과 유사 하기 때문에 시 뮬 레이 션 퇴화 라 고 한다.
주요 사고 방향
우 리 는 함께 퇴화 를 모 의 하 는 주요 사고방식 을 귀납 할 수 있다.

우선, 우 리 는 먼저 최초의 온도 T T T (물리학 법칙 에 따라) 를 설정 해 야 한다. 이 초기 온도 가 무엇 을 선택 하 는 것 이 좋 은 지 나 도 잘 모르겠다. 일부 큰 남자 들 은 제목 에 따라 가장 좋 은 초기 온 도 를 내 놓 을 수 있다 고 한다.

초 온 을 확정 하면 우 리 는 조작 을 시작 할 수 있다.

현재 상태 에서 다음 상태 로 옮 길 수 있 는 모든 상태 에 대해 우 리 는 이 를 원래 의 답안 과 비교 할 수 있다.

r e s < n e w res < new res < newr e s res, 우 리 는 반드시 답 을 옮 길 것 이다.

그렇지 않 으 면 우 리 는 일정한 확률 로 답 을 옮 길 수 있다.

마지막 으로 한 번 의 답 이동 이 끝 난 후에 우 리 는 T T T 를 1, 1 에 가 깝 지만 1, 1 에 가 까 운 수 d e l t a delta delta 에 곱 하여 시간 이 답 에 미 치 는 영향 을 나타 내 는 것 을 기억 해 야 한다.

이 주요 사고 에 따라 우 리 는 소 둔 을 모 의 하 는 템 플 릿 을 쓸 수 있다.

int T=***;// T     （          ）
while(T>eps)//eps     0    ，   1e-15
{
	int nxt=Next(now),new_res=Calc(nxt);//nxt       ，new_res             
	if(res<new_res||exp((res-new_res)/T)*RAND_MAX>rand()) now=nxt,res=new_res;//            ，        ，      
	T*=delta;//     ，     ，                 
}

예제
마지막 으로 예 제 를 들 어 소 둔 을 모 의 하 는 신기 한 점 을 느껴 보 자. [낙 곡 1337] [JSOI 2004] 매달 기 XXX.
이 문제 의 정 해 는 나 도 무엇 인지 모르겠다.
제목 의 대 의 는 그림 의 넓 은 의미 의 페 이 마 를 구하 고 블 로 그 를 구체 적 으로 해석 하 라 는 것 이다.