항공편 일정 알고리즘

Question

모든 직항 항공편 목록이 있습니다. 이걸로 나는 A와 B가 연결되는 항공편을 얻고 싶습니다. 이 문제에 적합한 알고리즘 또는 데이터 구조는 무엇입니까? 감사.

Answer 1

기본적으로 이것은 각 출발 또는 도착이 노드가되고 각 비행이 가장자리 인 그래프를 통과하는 문제입니다. 일반적으로 가장자리에 비용을 적용합니다 - 사용자의 선호도에 따라 "비용"은 티켓 가격 (최저가를 얻는 데 드는 비용) 또는 비행 시간 (최단 비행 시간을 얻기위한 비용) 일 수 있습니다. 같은 공항에서의 도착과 출발은 비용이 도중 체류 시간 인 가장자리로 연결됩니다. (가격 관점에서는 일반적으로 비용이 0이됩니다).

Answer 2

직항 노선은 그래프를 생성합니다. 노드는 공항입니다. 가장자리는 직행 비행기가있는 공항 사이이며, 각 가장자리에는 무게가 있다고합니다. A와 B 사이의 모든 단순 경로를 찾으려하고 아마도 경로 모음으로 끝내기를 원할 것입니다. 그래프의 깊이 우선 검색을 할 수 있습니다.

그래프를 인코딩하는 일반적인 두 가지 방법은 인접 목록 (즉, 각 노드에 대해 가장자리가있는 노드 목록)입니다. 또는 NxN 행렬 (N 노드의 경우) 위치 (i, j)의 값은 노드 i와 노드 j 사이의 가장자리 비용을 알려줍니다.

주어진 데이터 구조. 노드 A에서 시작하여 노드 B에서 끝나는 깊이 우선 탐색을 사용할 수 있습니다. 순환을 방지하기 위해 알고리즘이 현재 경로에있는 노드를 다시 방문하는 것을 방지해야합니다.

Answer 3

기존 문제 Shortest path problem. 알고리즘을보고있는 경우 위키 백과 페이지에 몇 가지 옵션이 표시되거나 ACO과 같은 알고리즘이 있지만 옵션은 있지만 유스 케이스 및 솔루션 제공 방법에 따라 다릅니다. .

이 내용은 traveling salesman problem의 변형이며 결과는 NP-complete입니다.