19개의 댓글이 있습니다.
-
-
JongMan -
아.. 좀 시간을 들여서 열심히 해봤어야 하는데 너무 안타깝네요. 여엉 시간을 별로 못썼습니다. ㅜㅜ
초반에 그냥 한번 로컬서치나 하고 짜볼까 하고 대충 코딩했다가 얼떨결에 거기에 매달려서 삽질한게 제일 아쉽네요. 저는 처음에 5초씩 쪼개서, 랜덤한 두개를 스와핑해가며 로컬서치 했습니다. 이거 섭밋이 35점 정도 나왔는데, 그 후로 며칠간 쭉 바빠서.. 마지막 네시간 동안 이거를 최적화하는 걸 택했는데요. Simulated Annealing 도 적용해보고 초기해를 그리디로도 만들어보고, 해 조작하는 방법도 바꿔보고 단순 dp로도 만들어보고 패러미터 튜닝도 해보고 별의 별 삽질을 다했는데, 36점 조금 넘긴 점수로 마감하게 되었네요. ^^;
확실히 시간을 좀 더 들이고 문제와 어프로치에 대한 직관을 얻어야 잘 할 수 있겠다는 생각이 듭니다.
그 외에는, SA나 로컬서치같은 메타휴리스틱을 쓸 때는 해 조작함수를 가능한한 atomic 하게 했어야 하는데 그걸 간과했다는 생각도 들구요. 많은 접근 방법들이 있는데, 어떻게 시작하느냐에 따라서 점수의 상한선 같은 것이 정해진다는 느낌을 받았습니다. 초반에 가능한한 많은 방법을 생각해 보고, 기계에서 이들을 경쟁시켜서 답을 선택하고 패러미터 튜닝을 하는 게 중요한 것 같구요. 상위 랭커들 소스를 보니 많이 돌려보고 많이 테스트하고 많이 고민한 흔적이 느껴지더군요.
일단 CPU 빠른 컴퓨터를 한대 사야할 것 같습니다. -__-;
16년 전 link
-
-
-
JongMan -
아 그리고.. 로컬 서치는 이와 같이 시간이 오래 걸리는 문제를 해결하기 위한 근사 알고리즘 (메타휴리스틱) 입니다. 해를 랜덤하게 바꿔보고, 더 좋으면 그걸 택하고, 아니면 버리는 방법이지요. 예를 들면 다음과 같겠습니다.
solution = (1,2,..,n)
while(시간이 다 될 때까지)
a = rand(); b = rand()
if(만약 a 와 b 를 바꿀 때 답이 더 좋아지면)
swap(solution[a], solution[b])
물론 답을 어떻게 수정하느냐에 따라서도 달라지고.. 최적화할 거리가 많은 알고리즘이지요.
http://en.wikipedia.org/wiki/Local_search_(optimization)http://en.wikipedia.org/wiki/Local_search_(optimization) 를 참조하세요.
16년 전 link
-
-
-
lewha0 -
이미 irc에서 한바탕(?) 토의가 끝난 뒤라서 게시판은 아직 한산한 건가요, 아니면 단지 아직 아침이라? ㅎㅎ
저는 기본적으로 그리디+로컬서치를 사용했습니다. 최대한 다양한 그리디 알고리즘을 돌려본 뒤, 그 해를 가지고 로컬서치를 적용하는 방식 이었습니다. 그리디는 기본적으로 weight[ i ] = sum( a[ i ][ j ] ) 가 최대한 것부터 앞에 놓는 방식이었습니다. 나머지는 이를 변형한 것이었는데, sum( a[ j ][ i ] ) 가 최대인 것부터 뒤에 놓는 방식, 혹은 이미 놓은 것들과의 weight 를 계산해서 더하는 방식 이었습니다. 로컬 서치는 연속되어 있는 7 이하의 영역을 잡아서 백트래킹으로 순서를 조절하는 방식이었습니다.
위의 그리디와 비슷한 기준으로 divide and conquer 방식도 돌려 보았습니다. 그리디와 비슷한 기준으로 절반을 추려낸 뒤, 그 부분에 대해서만 weight 를 다시 계산하는 식이었습니다. 또, 최종적으로 시도한 방법은 백트래킹이었는데, 7개씩 묶어서 백트래킹으로 순서를 정하고, 그 7개씩 묶은 것들을 다시 7개씩 묶어서 백트래킹으로 순서를 정하고, 이런 식으로 묶음이 한 개 이하로 남을 때까지 반복하는 식이었습니다. 결과는 참담하더라고요 -_-;
제가 사용한 방법은 '어떤 수들을 뭉쳐 놓으면 좋을 것인가'에 초점을 맞춘 방법들이었던 것 같은데, 이 문제는 이러한 질문에 답하기 꽤 어려운 문제였던 것 같습니다. 그나마 쉽게 답할 수 있는 질문은 '두 수만 놓고 봤을 때, 이 둘을 어떤 순서로 놓으면 좋을 것인가' 정도인 것 같고요. 다른 분들 중에 순열을 shift 해 보는 식으로 접근하신 분들도 있는 것 같던데, 이 경우에는 두 원소간의 순서가 거의 유지되기 때문에 제법 잘 먹혔던 것 같습니다.
흥미로운 건 제 백트래킹 부분인데요, 백트래킹에서 최적해를 구한 다음에 갱신을 하지 않았습니다 -_-; 따라서 로컬 서치는 '아주 작은 부분에 대해서 최적해를 구해서 해를 변형한다' 가 아니라, '아주 작은 부분에 대해서 개선이 가능하다면 가능한 방법 중 하나를 택하여 해를 변형한다'가 되었는데.. 오히려 이 편이 해가 더 좋았습니다 -0- 로컬 옵티마에 빠지는 걸 스스로 경계하는 알고리즘이 아니었나 생각되네요. 허허허허.. 그 외에도 버그가 조금 더 있었는데, 이상하게 버그를 고치면 해가 더 나빠지더라고요 -_-; 최종 제출본 역시 버그가 담겨 있습니다.
16년 전 link
-
-
-
최치선 -
큐가 작다는 이유로 c#을 선택한 치선입니다 orz. 덕분에 뻘짓도 좀 하고. 그랬네요.
다들 그랬듯이 n <= 15보다 작을땐 next permutation으로 다돌려서 계산. (문제 안읽었음 ㅈㅅㅈㅅ)
처음 적용한 소트는 생략하고 (효율이 떨어지고 말도 안되는거라) 느리지만 나름 나오는 그리디를 설명하자면
Sum[i, j] = (sum x=0~i-1, w[p[x],p[j]]) + (sum x=j+1~n-1, w[p[i], p[x])라고 정의 했을 때
Swap(p[i], p[j])을 했을때 score변화량은 d는
d = (Sum[i, j] - w[p[i], p[i]]) + (Sum[j, i] - w[p[j], p[j]]) + w[p[j], p[i]] - (Sum[i, i] + Sum[j, j] - w[p[i],p[j]])
로 계산됩니다 (복잡하군요 orz)
i = 0~n-1, j = i+1~n 으로 돌리면서 d값이 최대가 되는 두 점을 찾아서 바꾸고 Sum을 갱신하면서 반복했습니다.
n^2만에 한번의 swap밖에 일어나지 않는 점과 매번 Sum을 갱신(n^2)해줘야한다는 점이 부담스러운 방법입니다.
저 방법으로 더이상 갱신이 일어나지 않을 때까지 돌린 뒤 로컬서치를 했습니다. (SA를 적용해봤으나 더 구려졌음)
로컬서치는 초기 반복회수 l = 100이고 바꿀 element의 개수 swapCount = 2로 시작합니다.
l만큼 반복할 동안 갱신이 일어나지 않으면 swapCount를 1증가 시키고
swapCount가 swapMax에 도달하면 l 값을 2배로 하여 반복합니다.
여기서 제가 실수한게 swap 할 element를 랜덤하게 뽑는데 중복되는 랜덤이 선택되었을 경우
무시하고 다음으로 넘어가야하는데 그 부분을 처리하지 않아 시간이 많이 소모되었던게 아쉽네요
(그걸 적용했더니 +2정도의 향상이 orz)
처음 그리디에서 계산부분의 시간 복잡도를 낮추지 못한것이 좀 많이 아쉬웠고
로컬서치에서 세세한 부분에 최적화를 하지 못했던게 좀 걸리네요.
그리고 c#이 리눅에서 무지 느리게 돌아가는 바람에 테스트에 조금 안습이었던 점도 있었습니다 ㅠㅠ
(집컴으로 돌리니 더 잘나오던데 ㅠㅠ)
JM의 '일단 CPU 빠른 컴퓨터를 한대 사야할 것 같습니다. -__-;' 완전 공감.
아무튼 다들 수고하셨어요 :)
16년 전 link
-
-
-
JongMan -
흠.. 얘기를 하다 보니 어떤 perturbation 방법이 SA 와 로컬서치에 각각 더 적합한지에 대해서 다들 다른 경험을 가지고 있군요.
대개 사용한 해 변경 방법은:
1. insertion: pick random a and b. b 위치에 있는 애를 a 앞으로 옮긴다.
2. swap: pick random a and b. a 위치와 b 위치에 있는 애를 스왑한다.
스탱이나 저는 1번이 SA 에 더 적합한 것 같다고 생각하는데,
그러나 20위 하신 일루옹은 SA 를 스왑으로 하셨다능...
<일루^wake> 스왑이 perturb 효과가 와방인듯
<일루^wake> 밀어넣는거는 너무 스스로 만족함
16년 전 link
-
-
-
Taeyoon_Lee -
저는 altertain입니다.
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
lewha0
여러분의 접근 방법을 리플로 토의하는 글입니다 :)
본의 아니게 풀이를 보게 되시는 걸 막기 위해서, 아래의 짤방을 하나 첨부합니다.
정말 토의하러 오신 분들만 아래로 스크롤 해 주세요 ㅎㅎ
지금은 소녀시대!
앞으로도 소녀시대!
영원히 소녀시대!!
16년 전