4개의 댓글이 있습니다.
-
-
A.I -
intersection 에 대한 thread도 올라와있네요.
http://forums.topcoder.com/?module=Thread&threadID=677737
13년 전 link
-
-
-
ILyoan -
기본적으론 SA이고 SA를 하기전에 전처리를 해서 점들의 초기 위치를 잡았습니다.
전처리:
처음에는 인접한 점들의 무게중심으로 점을 이동시키는 방법을 썼는데 이 방법을 쓰면 점들이 일렬로 배치되는 문제가 있어 나중에 sammon mapping으로 바꿨습니다.
SA:
우선 평면의 크기를 대폭 줄입니다. 원래는 700*700인데 정점과 에지수에 따라 10*10 ~ 20*20 정도로 줄여서 시작합니다.
정점을 임의의 순서로 정렬하여 하나씩 이웃한 위치로 옮겼을때 이득이 최대가 되는 점을 찾아 이동합니다.
일정시간이 되면 사이즈를 두배로 늘리고 반복합니다.
사이즈를 늘리는 것에 대해서
우선 초기에는 상대적으로 먼 지점으로 점들을 옮겼을 때의 이득을 구하고 후반에는 주변으로의 이동에 대한 이득을 취한다는 컨셉이었고 사이즈를 줄이면 서치공간이 줄어들기 때문에 시간에서 이득을 취할 수 있다고 생각했습니다.
지금 생각해 보니 사이즈를 두배로 늘리는것이 점들의 이동 반경을 줄이는 것과 거의 비슷군요
사이즈를 두배로 늘릴때 너무 급격하게 변화가 생기는거라 점진적으로 사이즈를 늘리는 방법이 없을까 고민을 했었는데 사이즈를 늘리지 말고 점의 이동 반경을 점진적으로 줄이면 되는 거였는데 미쳐 생각하지 못했네요 ㅠㅠ.
교점 처리는 CLRS에서 배꼈습니다.
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
일루
드디어 길고 긴 R1이 끝났습니다. 한국인 통과자 분들도 꽤 되시는듯...
방법을 토론해 봅시다 :)
저는 일단 http://forums.topcoder.com/?module=Thread&threadID=677731 여기 써놨습니다.
13년 전