나는 문제가 있지만 문제를 해결할 수있는 이름이나 알고리즘을 찾지 못했습니다.연결이 끊긴 선분을 통한 최단 경로
유클리드 2D 공간에서 선 세그먼트 집합을 감안할 때 모든 세그먼트를 통과하는 최단 경로를 찾는 것이 좋습니다.
이 문제는 예를 들어 펜을 사용하여 종이에 그려지는 그리기 기계에서 발생하며 그리기 작업간에 쓸모없는 이동 시간을 최소화해야합니다.
이 문제의 이름은 무엇입니까? 간단한 근사 솔루션이 있습니까?
플롯 펜의 비 도면 이동 거리를 최소화하는 문제는 라인 세그먼트 끝점을 정점으로 사용하고 선 그리기 선 세그먼트의 두 끝 사이에 0의 비용을 할당하여 traveling salesman problem에 매우 가깝습니다.
TSP과 달리, 문제로 인해 선 세그먼트 중간에서 선 그리기를 시작하고 중지 할 수 있습니다. power icon의 세로선은 한 번에 전체를 표시하는 것이 아니라 두 개의 세그먼트로 한 줄을 그리려는 시간의 한 예입니다. 그러나, 나는 그리기를 시작하는 장소가 그리기를 멈추는 장소와 다른 경우에만 이러한 종류의 사례가 발생한다고 생각합니다. 내 추측이 맞다면, 여행 판매원 문제를 해결함으로써 얻을 수있는 해답은 그래프의 너비까지만 최적 솔루션과 다를 것입니다.
이 경우 tsp 용 솔루션을 채택해야합니다.
유전자 알고리즘을 통해이를 수행 할 수 있습니다. 최상의 솔루션을 얻을 수 있다고 보장 할 수는 없지만 짧은 시간 내에 대개는 매우 가까워 질 수 있습니다.
기본적으로 임의의 솔루션 세트로 시작합니다. 그런 다음 각 솔루션에 대해 임의의 변경을 가하고 이동 거리를 측정합니다. 최단 거리를 유지하십시오. 새로운 세대가 최적화를 제공하지 못하게 될 때까지 또는 당신이 시간이 없어 질 때까지이 과정을 반복하십시오.
세그먼트가 비용 0 인 TSP에 대한 솔루션이 모든 세그먼트를 사용하기 위해 보증되어 있습니까? 나는 단지 몇몇 vertifications가 0- 비용 경로보다 더 민감한 2 개의 여행 경로를 통해 도달하는 것이 더 쌀 수 있다고 상상했다. – dronus
그러나 세그먼트 안에 다른 정점을 배치하면 쉽게 해결할 수 있습니다. – dronus