최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기정보과학회논문지. Journal of KISS (a):computer systems and theory. A, v.25 no.4, 1998년, pp.362 - 368
이경미 , 이건명
순회 세일즈맨 문제(Traveling Salesman Problem, TSP)는 주어진 모든 도시를 한번씩만 경유하는 가장 짧은 경로를 찾는 문제로서 대표적인 NP-complete 문제의 하나이다. 본 논문에서는 우선 방문순서 제약이 있는 TSP라는 새로운 부류의 TSP에 대해서 소개한다. 방문순서 제약이 있는 TSP는 경로를 찾을 때 어떤 도시를 특정 도시보다 먼저 방문해야 한다는 방문순서에 대한 제약조건이 있는 TSP이다. 다음으로 이러한 TSP를 해결하기 위한 유전자 알고리즘을 제안한다. 제안된 유전자 알고리즘에서는, 부여된 모든 방문순서 제약을 만족하는 염색체만을 생성하는 선행관계유지 교차연산자와 선행관계유지 이동 연산자라는 새로운 두개의 유전 연산자가 도입되고, 부여된 방문순서 제약을 만족하는 염색체만으로 초기 모집단을 구성하는 방법이 사용된다. 실험을 통해서 제안된 방법이 방문순서 제약이 있는 TSP를 해결하기 위한 유용한 도구임을 보인다.
Traveling Salesman Problem (TSP) to find a tour which visits all the given cities just once with minimum traveling cost is a well-known NP-complete problem. We introduce a new class of TSP called TSP with precedence constraints. TSP with precedence constraints differs from conventional TSP. In this...
※ AI-Helper는 부적절한 답변을 할 수 있습니다.