[BOJ / 휴리스틱(시뮬레이티드 어닐링)] 16992 3-SAT

https://www.acmicpc.net/problem/16992

16992번: 3-SAT

 

16992 3-SAT

알고리즘 : 휴리스틱(시뮬레이티드 어닐링)

시뮬레이티드 어닐링(담금질 기법)을 이용한 휴리스틱 풀이입니다. 휴리스틱이란 정해를 구하기엔 시간이 충분하지 않거나 정보의 부족으로 인하여 합리적인 해를 제시할 수 없을 때, 빠르게 사용할 수 있는 확률에 의지하는 방법 입니다. 

SCPC에 자주 나오는 유형이라 이번에 새로 공부하게 되었는데, 정해가 정해진 문제보단 정해에 가까운 답을 유추해내는 실전에서 유용할 듯 합니다.

풀이에 이용되는 방법으론 가지치기, 시뮬레이티드 어닐링, 유전 알고리즘 등이 있으며 후에 관련 글을 작성하도록 하겠습니다.

현재 세대의 x들의 true / false 정보를 저장하는 b의 랜덤 인덱스에 토글을 하는 식으로 진행하여 중간에 답을 찾을 경우 탈출하는 식으로 진행하면 됩니다. 제한 시간에 최대한 맞춰 반복 횟수를 지정하는 편이 답을 얻어내는데 유리하므로 조정을 잘 하여야 합니다.

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <random>
#include <vector>
#include <stdlib.h>
#include <ctime>
#include <cmath>

using namespace std;

int n,m;
int arr[3005];

int main() {
    random_device rd;
    mt19937 mt(rd());

    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    uniform_int_distribution<int> ran(1, n);

    for (int i = 0; i < m; i++) 
    {
        int start = i * 3;

        cin >> arr[start] >> arr[start+1] >> arr[start+2];
    }

    vector<bool> a(105, false), b(105, false); 
    int prv = 0; 
    double t = 1.0, k = 2.5; 

    for (int i = 0; i < 180001; i++) 
    { 
        b = a; 
        int rIdx = ran(mt);
        b[rIdx] = !b[rIdx];

        int now = 0; 

        for (int j = 0; j < m*3; j += 3) 
        {
            bool chk = false;

            chk |= ((arr[j] > 0) ? b[arr[j]] : !b[-arr[j]]);
            chk |= ((arr[j + 1] > 0) ? b[arr[j + 1]] : !b[-arr[j + 1]]);
            chk |= ((arr[j + 2] > 0) ? b[arr[j + 2]] : !b[-arr[j + 2]]);

            if(chk)
                now++;
        }
        double nowP = exp((double)(now - prv) / (k * t)); 

        double rP;
        
        if (n == 1)
            rP = 0;
        else
            rP = ((double)ran(mt) - 1) / (n - 1);

        if (nowP > rP)
        {
            a = b; 
            prv = now;
        }

        if (now == m)
        {
            cout << "1\n";

            for (int j = 1; j <= n; j++)
                cout << b[j] << ' ';
            cout << '\n';
            return 0;
        }

        t *= 0.9999; 
    }

    cout << "0\n";

    return 0;
}

시간 : 1740ms

 

태그 : #BOJ 3-SAT #백준 3-SAT #16992 3-SAT #3-SAT풀이 #시뮬레이티드어닐링 #담금질기법