들어오는 patrol의 수와 나가는 patrol의 수가 같다 -> 모든 경로는 어떤 cycle의 일부여야 한다.
음... 대회 당시에는 얼핏 이런 정도의 아이디어로만 생각하고 말았기 때문에 자세한 증명을 적기는 좀 어렵다.
무조건 연결해야 하는 edge들이 있는데, 아무렇게나 이런 edge들을 포함하는 cycle들을 찾은 다음에 해를 개선하는 방법으로 접근해보기로 했다.
<ul><li>※ : 어떤 해를 표현하는 방법은 patrol이 다니는 edge들의 집합으로 정의하겠다. 예) S={1,2,5} : 1,2,5번 edge에 patrol이 지나고, 나머지 edge는 감시카메라를 놓는 해.
</li><li>임의의 해 S를 개선하기 위해서는 S에 새로운 cycle을 추가하거나, 기존의 cycle을 변형해서 새로운 cycle을 만들 수 있으면 되는데, 기존의 cycle을 변형하는 방법은...
<ul><li> network flow의 idea를 응용하면 된다. 어떤 edge E가 사용중이라면 E의 끝점에서 E의 시작점으로 이동하는 가상의 edge가 있다고 가정할 수 있는 것이다.
<ul><li>다만 이 방법을 사용할 때, 무조건 연결해야 하는 edge들을 연결해제하면 안되니 특수처리해주는 센스가 필요함.
</li></ul>
그러므로 해를 개선하는(=negative 가중치의) cycle을 찾으면 되니 bellman-ford 알고리즘을 사용해서 계속해서 해를 개선하면 된다.
<ul><li>다만... 계속해서 해를 개선하는 local search 방식이기 때문에 local minimum인 경우가 존재한다면 조금 문제가 된다. 증명해야 하는데 대회 당시에는 그런거 안함 ㅋ
</li></ul>
이런 식으로 최적해를 찾았는데, 최적해에 patrol이 하나도 없으면 문제 조건 때문에 안되므로, 가장 작은 가중치의 cycle을 하나 찾아서 집어넣는다.
Neon
원문은 역시나 제 springnote에 있습니다.
개요
풀이
<ul><li>※ : 어떤 해를 표현하는 방법은 patrol이 다니는 edge들의 집합으로 정의하겠다. 예) S={1,2,5} : 1,2,5번 edge에 patrol이 지나고, 나머지 edge는 감시카메라를 놓는 해.
</li><li>임의의 해 S를 개선하기 위해서는 S에 새로운 cycle을 추가하거나, 기존의 cycle을 변형해서 새로운 cycle을 만들 수 있으면 되는데, 기존의 cycle을 변형하는 방법은...
<ul><li> network flow의 idea를 응용하면 된다. 어떤 edge E가 사용중이라면 E의 끝점에서 E의 시작점으로 이동하는 가상의 edge가 있다고 가정할 수 있는 것이다.
<ul><li>다만 이 방법을 사용할 때, 무조건 연결해야 하는 edge들을 연결해제하면 안되니 특수처리해주는 센스가 필요함.
</li></ul>
<ul><li>다만... 계속해서 해를 개선하는 local search 방식이기 때문에 local minimum인 경우가 존재한다면 조금 문제가 된다. 증명해야 하는데 대회 당시에는 그런거 안함 ㅋ
</li></ul>
참고자료
14년 전