Diversified Late Acceptance Search

dlas.hpp

#ifndef DLAS_HPP

#include "intdef.hpp"
#include <array>
#include <algorithm>
#include <functional>
#include <utility>

template<class T, class U>
T incMod(T x, U mod) {
	x += 1;
	return x == mod ? 0 : x;
}

template<class Domain, class CoDomain, size_t LEN = 5>
std::pair<Domain, CoDomain> dlas(
	std::function<CoDomain(Domain&)> f,
	std::function<void(Domain&)> mutate,
	Domain const& initial,
	u64 maxIdleIters = -1ULL
) {
	std::array<Domain, 3> S{initial, initial, initial};
	CoDomain curF = f(S[0]);
	size_t curPos = 0;
	size_t minPos = 0;

	std::array<CoDomain, LEN> fitness;
	std::fill(fitness.begin(), fitness.end(), curF);
	CoDomain minF = curF;
	size_t k = 0;

	for (u64 idleIters = 0; idleIters < maxIdleIters; idleIters += 1) {
		CoDomain prvF = curF;

		size_t newPos = incMod(curPos, 3);
		if (newPos == minPos) newPos = incMod(newPos, 3);

		Domain& curS = S[curPos];
		Domain& newS = S[newPos];

		newS = curS;
		mutate(newS);
		CoDomain newF = f(newS);
		if (newF < minF) {
			idleIters = 0;
			minPos = newPos;
			minF = newF;
		}
		if (newF == curF || newF < *std::max_element(fitness.begin(), fitness.end())) {
			curPos = newPos;
			curF = newF;
		}

		CoDomain& fit = fitness[k];
		if (curF > fit || curF < fit && curF < prvF) {
			fit = curF;
		}
		k = incMod(k, LEN);
	}
	return { S[minPos], minF };
}

#define DLAS_HPP
#endif

intdef.hpp

#ifndef INTDEF_HPP

#include <cstddef>
#include <cstdint>

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using usize = size_t;
using f32 = float;
using f64 = double;
using f80 = long double;

#define INTDEF_HPP
#endif

사용법: dlas<상태 타입, 점수 타입>(f, mutate, initial, maxIdleIters)

• f: 현재 상태를 받아서 해당 상태의 점수를 반환하는 함수
• mutate: 현재 상태를 받아서 임의의 수정을 가하는 함수 (반환값 없음)
• initial: 초기 상태
• maxIdleIters: 답이 안 바뀔 때(지역해에 갇혔을 때) 얼마나 오래 기다릴지

재시작

재시작은 적게는 16번, 많게는 256번 정도면 적절해 보인다. maxIdleIters는 제한시간 내에서 최대로. 아래와 같은 느낌

for(int i = 0; i < 16; i++) {
	auto[board, res] = dlas<Board, u32>(f, mutate, a, 1000);
	if(res < ans) {
		ans = res;
	}
}

아웃풋 온리

아웃풋온리면 maxIdleIters 안 넣고 그대로 쓰는 게 좋다. 위와 다르게 무한루프를 돌아서 재시작이 안 되는데, 터미널 여러 개 켜고 각각 굴리면 된다. (물론 직접 멀티스레딩을 하거나 OpenMP같은 걸 써도 무방하다.)

진행상황 보려면 f 끄트머리에다가 출력 로직을 짜야 한다. 다 출력하면 당연히 출력만 하다 죽으니까, 최소값 갱신 로직도 같이 넣고 갱신 시에만 출력하도록 해야 한다.