위의 그림은 간단한 예제로써 1,2,3... 9 가 마을이고 그 사이의 간선들이 마을과 마을을 잇는 수송로이다.
여러분은 장군을 도와 모든 수송로를 파괴해 모든 마을이 서로 고립되게 하려고 한다.
이 장군은 좀 특이해서 한 마을을 지정해서 그 마을에 연결된 모든 수송로를 파괴한다고 한다.
(인도적인(?) 장군이라 선택한 마을자체는 파괴안한다고 하자)
이를테면 1번 2번 3번 4번 마을을 택한다면 총 4번의 파괴가 이루어지면 모든 마을은 단절된다.
하지만 2번,3번,4번 마을을 택한다면 아까보다 적은 총 3번의 파괴가 이루어지고 모든 마을은 단절된다.
임의의 그래프가 주어져있을떄 장군이 모든마을을 고립시키기 위한 최소한의 파괴횟수를 알아내시오...
님 TSP도 잘품?
몬품
일단 보자마자 직관적으로 떠오른 해법은 재귀 호출로 풀 수 있는 듯
http://en.wikipedia.org/wiki/A*_search_algorithm
이것은 코세가 잘푼다. 예전에 로또 5등 무조건 확보하는 갯수 조합 추출해달라고 했을때 풀었던 방법이 유전자 알고리즘에 path 검색, 인터리빙 조합해서 풀었으니깐.
A* 사용해서 TSP 풀자공?
TSP 노드 많아지면 유전자 알고리즘 필수라던데 나는 못품
A*는 그냥 특정방향 지향하는 길찾기
유전알고리즘같은거나 A* 사용하면 TSP 풀린다고 들었는데 안해봐서 모름 데헷
terminal 이 있다면 그 앞은 반드시 파괴되어야 하는거고
노드들을 연결된 간선 수로 정렬해서 제일 간선 연결이 많이 된 노드로부터 시작. 거기서 재귀 알고리즘(동적 프로그래밍)으로 이웃 노드 방문하면서 해결. 내 마을 없애기 + 이웃된 마을 재귀 호출 vs 내 마을 안 없애고 이웃된 마을을 모두 없애기 + 이웃된 마을의 이웃들 재귀 호출. 비교해서 적은 쪽으로 진행해 나가면 될 듯
에이스타랑은 전혀 상관 없는 문제
저거 효율적인 알고리즘 좀 시간 나면 고민해 봐야겠다. 내가 쓴 방법은 너무 노가다성인듯.
휴리스틱한 A* 랑 최적해는 좀 거리가 있지 : )
아 참 이게 선택한 마을은 파괴하는게 아닙니다. 선택한 마을에 연결된 수송로만 파괴해요
하긴 터미널을 파괴하는게 나을지 길목을 파괴하는게 나을지는 계산해봐야 알겠넹.
아 내가 표현을 잘못 했네.
뭐 그게 그 말이긴 하다.
네. 어떤 걸로 푸나 결과는 같을 듯
고립된 마을은 없는 셈 쳐도 되니까요
http://183.106.113.109/pool/koi_Ewire/koi_Ewire.php?pname=koi_Ewire
예전에 .. 이런문제 풀다가 이게 갑자기 생각났는데 둘이 비슷한거같음
이게 어디에 나오는 문제임? 온라인 저지일거 같은데
위에 올린 링크 문제 풀다가 내가 생각난 문제.. 어디있을지도? 생각나는 풀이가잇는데 맞는건지도 잘모름
코세 횽 방법이 제일 좋은 듯? Terminal 앞의 마을을 무조건 없애는 거. 이걸 더 이상 없을 때까지 반복하면 되는 거 아님?
문제는 루프가 있을 때인데 좀 고민해 봐야지.