선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 또 어떤 사이트는 여러 개의 경유지를 입력하는 것을 허락한 다음, 입력된 순서대로 경유지들을 방문하는 경로를 찾아준다. 본 논문에서 설계하고 구현하는 웹 시스템은 입력된 경유지들의 방문 순서를 방문에 드는 비용이 최소가 되도록 결정한다는 점에서 기존의 시스템과 다른 새로운 최적 경로 제공 웹 시스템을 구현하고자 한다. 또한, 본 웹 시스템은 출발지와 목적지가 동일하여도 되고 서로 달라도 된다는 점에서 기존의 외판원 문제와는 차별화된다.
- 그리고 제안하는 알고리즘을 Java 애플릿으로 구현하였다. 본 논문에서는 여행하는 국도의 거리리는 관점에서 최적의 경로를 찾는 웹 시스템을 구축하였으며, 본 논문이 제안한 방문지 경유 최단 경로 찾기 알고리즘은 비용이 거리이든, 시간이든, 이니면 여비이든 어떤 조건에서도 무관하게 적용이 가능하다’ 추후에는, 여러가지 관점에서 비용을 최소화하는 최적의 경로를 찾아주도록 본 시스템을 개선하고자 하며, 나아가서 지리정보 기술을 적용하여 더욱 실용적인 시스템으로 개선하는 연구를 계속하고자 한다.
- 군 간의 거리를 측정한다는 것은 너무 시간과 노력이 많이 드는 작업이다. 본 논문에서는 이 문제를 해결하기 위하여, 지도에 나타나는 각 시 . 군에 대해 바로 이웃한 도시간의 국도의 거리만 측정하였고, 이 데이터로부터 Dijkstra 알고리즘〔9〕을 사용하여 모든 쌍의 도시간의 최단거리를 구하였다.
- 세 개뿐이다. 첫 번 방문지로 B가 선정되었을 경우를 고려해보자. 노드 1에 나타난 도시 A와 B간의 거리는 0이다.
- 또한, 본 웹 시스템은 출발지와 목적지가 동일하여도 되고 서로 달라도 된다는 점에서 기존의 외판원 문제와는 차별화된다. 출발지와 목적지가 동일한 경우에는 기존의 외판원 문제를 푸는 A* 알고리즘을 그대로 적용하여 해를 찾지만, 서로 다른 경우의 문제에 대한 접근방법은 본 논문에서 새롭게 제시하고자 한다.
가설 설정
- 따라서 여행에 드는 비용은 거리 행렬의 각행의 최소값과 각 열의 최소값의 총합 보다는 작지 않다〔13〕. 외판원 문제는 기본적으로 출발 도시와 종착 도시가 같다고 가정한다. 그러나 실생활에서는 출발지와 종착지가 다른 경우가 발생할 수 있다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.