나는 mysql에서 정규화 된 인접성 목록을 사용하여 가중 그래프를 설계했습니다. 이제 주어진 두 노드 사이의 최단 경로를 찾아야합니다.지도의 최단 경로
나는 Dijkstra를 PHP에서 사용하려고 시도했지만 구현하기가 어렵다 (나를 위해 너무 어렵다). 내가 느꼈던 또 다른 문제는 Dijkstra를 사용하면 모든 노드를 고려해야한다는 것입니다. 큰 그래프에서는 매우 비효율적 일 수 있습니다. 그럼 누구나 위의 문제와 관련된 코드를 가지고 있습니까? 최소한 누군가가이 문제를 해결할 수있는 방법을 보여 주면 좋을 것입니다. 나는 거의 일주일 동안 이곳에 갇혀있다. 도와주세요.
이것은 A * 알고리즘의 고전적인 사례처럼 들리 겠지만, 당신이 다 익스트라를 구현할 수없는 경우, 당신이 A *를 implenting 볼 수 없습니다.
편집 : 이것은 당신이 예상하는 좋은 방법이 있다고 가정합니다 (그러나 그것은 중요하다 당신이하지 과다 추정) 한 노드에서 목표에 점점의 비용.
edit2 : 인접 목록 표현에 문제가 있습니다. 지도에서 각 정점에 대한 객체를 만드는 경우 링크가있을 때 이러한 객체에 직접 연결할 수 있습니다. 따라서 근본적으로는 각 노드가 인접한 노드에 대한 포인터 목록 (또는있는 경우 참조)을 포함하는 개체의 목록입니다. 이제 새로운 노드의 경로에 액세스하려면 링크를 따라 가면됩니다. 무한 사이클을 피하기 위해 주어진 꼭지점을 따라 갔던 경로 목록을 유지해야합니다.
뭔가를 액세스해야 할 때마다 DB를 쿼리하는 한 어쨌든이 작업을 수행해야합니다. 가장 좋은 희망은 오직 DB를 쿼리하는 것입니다 ... 이것은 그래프의 특정 에지 또는 그래프의 한 vertext에 대한 모든 에지에 대한 정보를 얻고 자 할 때 쿼리하는 것입니다 (후자는 더 나은 경로가 될 수 있습니다.) 그래서 거대한 덩어리가 아닌 한 번에 느린 I/O를 한 번만 쳐보십시오.
이제 Ok that thats something ..하지만 그건 내 프로그램을 실행할 때마다 맵을 만드는 DB에서 모든 노드를 가져 오는 것을 의미할까요? – 5lackp1x3l0x17
사실, 질문을 다시 읽은 후에 뭔가를 이해했습니다. 목록은 이미 DB에 내장되어 있습니다. 이 경우 데이터베이스의 링크를 따르는 것 외에는 동일한 작업을 수행 할 수 있어야합니다. 테이블 구성 방법에 따라 간단하거나 매우 어렵습니다. 이상적으로, 정점에 대한 테이블 하나와 에지에 대한 테이블 하나가 있어야합니다. 이 경우 DB 구조만으로 위에서 언급 한 것과 똑같은 구조를가집니다. –
고맙습니다. .. 제 제안을 시도해 보겠습니다. – 5lackp1x3l0x17
다음은 Dijkstra 알고리즘을 Java로 작성한 것으로 PHP로 구현하는 방법을 이해하는 데 도움이 될 수 있습니다.
http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29
Dijkstra 알고리즘은 주어진 꼭지점에서 다른 꼭지점으로 최단 경로를 반환합니다.
의사 코드는 Wiki에 있습니다.
그러나 당신은 Floyd 알고리즘이 필요하다고 생각합니다. 이것은 직접 정점에서 모든 정점 사이의 최단 경로를 찾습니다.
두 가지 모두의 수학적 복잡성은 매우 비슷합니다.
나는 위키에서 PHP implementation을 찾을 수 있습니다.
OP가 소리 같은 거대한 데이터 세트에 대해 걱정한다면,이 알고리즘은 다항식 메모리 소비뿐만 아니라 명백한 런타임에 대한 트릭을 수행하지 않을 것입니다. 나는 이것을 줄이기 위해 집합의 클러스터링을 수행 할 몇 가지 구현을 보았고, 방문한 각 클러스터 내에서 다른 알고리즘을 실행했다.하지만 그렇게함으로써 가장 짧은 경로의 증거가 있다면 잊어 버린다. –
데이터베이스에서이 작업을 수행 하시겠습니까? 아니면 메모리에서 모두 수행 하시겠습니까? –
당신은 무엇을 제안합니까? 나는 둘 다 좋아하지만 기억이 더 좋다. – 5lackp1x3l0x17
정확히 무엇을 고집하고 있습니까? 또한 Dijkstra가 대용량 데이터 세트의 경우 속도가 느려지는 것이 맞습니다. –