Android 용 대중 교통 가이드를 구현하고 싶습니다. 입력은 시작 지점과 대상 지점입니다. 출력은 버스, 지하철을 사용하여 어떻게 목적지로 갈 수 있는지 알려주는 지시문이 될 것입니다 ... e.c 이것은 대도시에서는 쉽지 않으며 신속한 답변을 위해서는 잘 설계된 데이터베이스가 있어야합니다. Tranport 알고리즘은 passanger에 최적의 라인을 제공해야합니다. 데이터베이스 및 알고리즘 설계에 대한 귀중한 아이디어를보고 싶습니다. 답변 해 주셔서 감사합니다.대중 교통을위한 데이터베이스 설계 및 알고리즘?
아마도 가장 짧은 경로를 계산하려면 graph이 필요합니다.
그래프는 G=(V,E)이고 V = {all possible stations} 및 E = {(u,v) | there is a transport connecting station u to station v}입니다.
그래프가 [대도시의 경우 일 수있는] 메모리에 맞지 않으면 successors(u) = { v | (u,v) in E } 함수를 만들어서 즉시 그래프를 계산할 수 있습니다.
this older question에는 설명하는 것과 비슷한 동적 환경에서 두 꼭지점 간의 경로를 효율적으로 찾는 방법에 대한 몇 가지 토론이 있습니다.
거리가 없거나 시간, 경로 만 (예 : 32-51-12-65-45, 숫자는 스테이션 ID 임). 우리는 여전히 그래프를 사용해야합니까? – fiasco
@ user1193197 : 시간이 없어도 그래프를 사용하면 많은 정보를 얻을 수 있습니다. 최소한의 스위치가있는 경로를 찾으려면 간단한 [BFS] (http://en.wikipedia.org/wiki/Breadth-first_search)를 실행할 수 있습니다 (예 :). 그렇습니다. 그렇습니다. 이런 종류의 문제 때문에, 그래프가 좋은 선택이라고 말하고 싶습니다. – amit
@amit으로 그래프를 사용해야하고 거리/시간이 없으므로이 값에 '0'을 사용할 수 있다고 제안했습니다. 내가 '0'을 사용하려고하는 이유는 미래에 다음 버전을위한 새로운 구현을 많이 절약 할 수 있다는 것입니다. –
우리는 문제를 푸는 데 귀중한 시도를보고 싶습니다. – dasblinkenlight
먼저 그래프 이론에 대해 배우고, 두 번째로 np-full "세일즈맨 작업"을 풀려고합니다. 8-) –