대략적인 경로 솔루션을 설계하는 방법은 무엇입니까?

Question

노드가 연결될 것이라는 보장이 없다는 것을 고려하여 대상 노드에 가장 가까운 경로를 찾을 수 있도록 그래프 검색 알고리즘을 작성하려고합니다 (또는 기존의 경우 확장).

온타리오 주 Brampton에서 온타리오 해밀턴으로 가야한다고 가정 해 봅시다. 출발점에서 가능한 옵션은 지역 대중 교통, 버스 또는 도보입니다. 나는 걷는 것이 나의 목적지에 도착하는 가장 적은 길인 것을 안다. 그래서 나는 첫번째로 버스에 간다. 나는 내가 해밀턴에 가까운 지점으로 갈 수 있다는 것을 알고 있지만, 그 시점에서 GO 버스가 돌아 서서 그 가장 가까운 지점에서 또 다른 방향은 내가 걷는 것 외에 다른 선택 사항이없는 곳에서 진행된다. 그러나 알고리즘은 걷는 것을 고려할 뿐이다. 짧은 거리의 경우 그렇지 않다면 실행 불가능한 경로를 고려할 것입니다.)

알고리즘을 사용하면 더 길지만 도착 노드에 가까워 지거나 목적지 노드)가 더 높은 가중 경로가 될 수 있습니다 (가중치는 검색하는 동안 그다지 중요하지 않습니다. 결과가 전달 될 때만 오름차순으로 대상에 가장 가까운 경로로 나열됩니다). 유사한 내가 그 시작해야 어떤 알고리즘 1) 뭔가 : 3 개 대중 교통 버스가 떨어져 나에게

을 500m를 얻을 것입니다 예를 들어, 하나 개의 GO 버스 그래서 제 질문은 두 배입니다, 목적지 노드에서 나에게 3km를받을 수 있습니다 I : 2) 어떻게 programmaticly 노드가 그래서 그냥 끝에서 시작하여이

편집을 수행 역순 R.겠습니까을 노드에서 노드 A에서 이동하지 않는 것을 연결되지 않는 경우가 괜찮 것을 설명 할 것 가장 큰 근사해를 목표로하는 방법을 묻는 것을 잊었습니다. 특히 큰 그래프를 사용하면이 문제에 대한 수백만 개의 솔루션이있을 수 있기 때문입니다.

감사합니다, 마이클

Answer 1

왜 모든 노드가 연결되어 있다고 가정 할 수 없습니까? 현실 세계에서는 보통 택시 등을 걸거나 걸을 수 있습니다.

이 경우 모델을 다음과 같이 간단히 변경할 수 있습니다. 각 운송 수단에 대해 하나의 그래프가 있습니다. 같은 위치에있는 노드는 가중치 0의 가장자리로 연결됩니다 (예 : 공항이나 기차역에서 자동차로 내린 경우).

그런 다음 각 정점과 가장자리에 교통 유형을 표시하고 기존 라우팅 알고리즘을 사용할 수 있습니다. 오, 그건 그렇고, A *는 정말 큰 네트워크에 맞게 확장되지 않을 것입니다. Yahoo/Google/Microsoft Maps와 같은 소프트웨어가 실제로 사용할만한 것을 얻으려면 here을보십시오. 이 연구 그룹의 연구에는 DIMACS shortest path challenge의 우승자가 포함됩니다.

Answer 2

는 A* algorithm 읽기 최대. Dijkstra의 최단 경로 알고리즘을 일반화 한 것으로, 두 개의 꼭지점 사이의 거리에 대한 하한선을 제공하는 경험적 방법을 지정할 수 있습니다. 귀하의 경우, 경험적 함수는 단순히 유클리드 거리를 반환합니다.

알고리즘을 실행하고 최상의 특성 값을 갖는 버텍스를 추적하십시오. 소스와 유클리드 거리에서 그래프까지의 거리에서 어떻게 든 계산됩니다. 유일한 까다로운 부분은 종료 할시기를 결정하는 것입니다 (전체 그래프를 트래버스하지 않는 한).

Answer 3

추가 노드 특성과 관련된 문제가 발생했습니다. travelling salesman과 매우 유사합니다. 이런 유형의 문제가 NP Complete이고 조심성있는 알고리즘 일종의 최선의 방법이 될 것입니다.