|
:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
18/07/06 01:55
1. 홀수점의 개수가 n 개라면 항상 (n/2)붓그리기가 가능한 걸로 기억합니다.
간단히 설명하면, 홀수점이 4개인 도형의 홀수점 하나에서 출발해서 다른 홀수점에서 끝내면 그 두 점은 짝수점으로 바뀝니다. 남은 도형은 홀수정 2개짜리 도형이 되니 한붓그리기가 가능하겠죠. 이렇게 반복하면 됩니다.
18/07/06 01:59
(수정됨) 2번은... 질문의 뜻을 잘 모르겠습니다. 모든 edge를 지나되 하나의 edge를 두 번 지나지 않는 게 한붓그리기의 규칙이니까, 규칙대로 그린다면 어떻게 그리든 이동거리는 똑같습니다. 모든 edge들의 길이의 합과 동일하죠.
18/07/06 02:03
이동하는 세일즈맨 문제가 TSP인가요? TSP라면 한붓그리기가 가능함을 전제로 했던 것 같은데.... 모든 노드가 최소 2개 이상 연결되어 있을 때, 모든 노드들을 방문하고 출발점으로 돌아오는 문제니까요. TSP의 global optima는 못 구하지만 local optima를 구하는 알고리즘들은 꽤 많이 나와 있습니다. TSP가 겉으로 보기에 쉬워 보이고, 실제로 노드의 개수가 적으면 손쉽게 global optima를 구할 수 있는 알고리즘이 있으니 (다익스트라) 뭔가 어떻게 하면 될 것도 같은데... 싶어서 이것저것 적용해 보면 재미있죠. 가장 심플한 건 그리디, SA, GA같은 고전(?) 알고리즘들이 있겠네요. 요샌 얼마나 또 신박한 것들이 나왔으려나.. 다만 물류회사라거나 구글맵 같은 곳에서 실제로 어떤 알고리즘을 쓰는지는 모르겠네요.
|
||||||||||