일단 문제 자체는 NP-hard 문제임. 정확히 말해서 set cover 문제. 물론 n = 45로 고정되어 있어서 엄밀히 말하자면 상수 시간안에 돌긴 하겠지만, 이건 제쳐두고.


그러므로 당연히 공식/다항시간안에 최적의 답을 내놓는 알고리즘은 P = NP가 아닌 이상 존재하지 않음. 


그럼 결국 남은건 휴리스틱을 이용해서 탐색 공간을 줄이거나 하는 방법 밖에 없음. 코세님은 이걸 위해 GA를 쓰신것 같고. 사실 set cover 문제 휴리스틱 알고리즘은 많이 연구되어왔던 분야임.


neural net을 사용하는 방법도 있고, simulated annealing을 사용하는 방법도 있고, 등등 방법은 많음. LP + rounding을 이용한 f-approximation 알고리즘 (로또 문제에서 f는 6 C 3 = 20)도 있고 (f가 이론적으로 20이긴 하지만, 실제 활용면에서는 더 나은 답을 낼수도 있음), 그리디 휴리스틱도 있고.


뭐 그냥 그렇다고