운송 회사 정보 시스템을 모델링하는 간단한 웹 앱이 있습니다. 주어진 순서에 대한 최단 경로의 자동 계산 기능을 구현하고 싶습니다.가장 짧은 운송 순서 경로를 찾는 그래프 알고리즘
주문이화물의 집합으로 표현된다, 그들 각각 출발/도착 지점이 있습니다. 나는 각 쌍의 도시와 거리를 데이터베이스에 저장한다. 문제는 이러한 모든화물을 수송 할 수있는 최단 경로를 찾는 것입니다. 출발 도시와 도착 도시는 중요하지 않으며 유일한 흥미로운 점은 모든 운송의 하역을 포함하는 최단 경로입니다.
이러한 문제를 해결하는 데 적합한 그래프 알고리즘이 있습니까?
항목 수가 비교적 적은 경우 (사용자 의견에 나와있는 것처럼) Traveling Salesman Problem으로 줄일 수 있습니다.
먼저 각 도시 쌍 사이의 최단 거리가없는 경우 Floyd-Warshall algorithm을 사용하여 찾을 수 있습니다. 각 도시 쌍 사이에 이미 거리가 있다면이 단계를 건너 뛸 수 있습니다.
이제는 무차별 대도를 사용하는 도시 수가 적거나 복잡한 동적 프로그래밍 솔루션으로 쉽게 해결할 수있는 TSP 문제가 발생했습니다.
저는 여러분입니다. 순진한 해결책부터 시작하고 충분하지 않은 경우 - 더 복잡한 것을 구현하십시오.
이후에 도시 수가 많아지면 더 복잡한 TSP 알고리즘이 필요하며 문제의 특성으로 인해 최적이 아닌 솔루션을 찾아야 할 수도 있습니다. 즉, 당신이 소수의 도시에만있는 동안 - 기존 솔루션은 그 트릭을 수행해야합니다.
답장을 보내 주셔서 감사합니다. 문제의 정확한 정의를 찾았습니다. 픽업 및 배송과 관련된 차량 라우팅 문제 (https://en.wikipedia.org/wiki/Vehicle_routing_problem)입니다. 이 기능은 내 앱에 중요하지 않지만 구현을 시도하는 것이 흥미 롭습니다.이 작업을 수행 할 수있는 Java 라이브러리가 있기를 바랍니다. –
정확하게 이해하면 모든 경로를 제공하는 하나의 경로가 필요합니다. 이것은 [여행 세일즈맨 문제] (https://en.wikipedia.org/wiki/Travelling_salesman_problem)의 변형으로, NP-Hard입니다 (효율적인 최적의 솔루션은 알려져 있지 않습니다). 문제의 규모는 무엇입니까? 얼마나 많은 아이템을 기대합니까? – amit
[Dijkstra의 알고리즘] (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) 및 [A * 검색 알고리즘] (https://en.wikipedia.org/wiki/A*_search_algorithm)이 유용 할 수 있습니다 . – Bim
@amit 예, 단일 운송 중에 모든 품목을 인도하고 싶습니다. 훈련 프로젝트이므로 항목 수는 3-4 개가 될 것입니다. 그래서, 수동 경로 작성을 더 잘 구현하는 것처럼 보입니까?) –