Robot Tour Optimization 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]

==개요==
Robot Tour Optimization 문제란, 어떠한 공장에서 납땜 인두와 같은 도구가 장착된 로봇팔이 주어졌을 때, 회로 기판을 제조할 때는 모든 칩과 다른 부품들을 기판에 고정하기 위해서 취해야 하는 가장 효율적인 동선을 찾는 것이다. 더 구체적으로, 각 칩에는 보드에 납땜되어야 하는 접점들의 집합이 있다. 이 작업을 위해 로봇 팔을 프로그래밍하려면, 로봇이 첫 번째 접점을 방문(그리고 납땜)하고, 그다음 두 번째, 세 번째 접점을 방문하는 식으로 작업이 끝날 때까지 동선을 구성해야 하며, 또한 모든 작업을 마친 후에는 다음 보드를 준비하기 위해서 첫 번째 접점으로 되돌아가므로, 로봇팔의 동선은 닫힌 순회 동선이 된다. 이때 두 점 사이를 이동하는 시간은 그 거리와 비례한다. 따라서 요약하자면 아래와 같은 알고리즘 문제이다.
 입력: 평면 위의 n개 점으로 이루어진 집합 S.
 출력: 집합 S의 각 점을 방문하는 가장 짧은 닫힌 순회 동선은 무엇인가?

==알고리즘==


==각주==