현재 대형, 희소 그래프에서 k- 중심 문제를 해결할 방법을 찾고 있습니다. 이 데이터는 openstreetmap에서 가져온 것이므로 지점에있는 그래프의 노드까지의 거리가 최소화되도록 도시에 k 피자 배달 지점을 배치하고 싶습니다.큰 그래프 (도로망)의 k- 센터
예 : 나는 도시 최선을 충당하기 위해 3 피자 배달 지점을 배치해야합니까?
문제점 : 그래프는 약 50,000 내지 250,000 노드 (OpenStreetMap의 데이터)을 포함한다.
단순화 : 해결책은 완벽 할 필요는 없습니다. 근사치이면 충분합니다. k은 20보다 작습니다. 몇 시간의 런타임도 괜찮습니다.
큰 실세계 그래프 (도로 네트워크)에서 문제를 해결하는 방법에 대해 아이디어를 듣고 기다릴 수 없습니다.
다음 greedy 알고리즘은 각 도로의 이동 시간이 양방향에서 동일한 경우에 대한 2 근사입니다. 단방향 거리를 무시하면 여행 시간이 너무 많이 왜곡되어서는 안됩니다.
첫 번째 중심을 임의로 선택하십시오. 이후의 각 중심에 대해 기존 중심에서 가장 멀리 떨어진 정점을 선택합니다. Dijkstra 알고리즘의 다중 소스 확장 (우선 순위 큐를 초기화하여 거리가 0 인 기존 센터를 모두 포함)을 사용하면 매개 변수가 n = 250,000이고 k = 20 인 최신 하드웨어에서 실행되는 좋은 구현은 최대 초를 취해야합니다 또는 두.
나는 그것을 시도 할 것입니다. 그러나 고속도로는 매우 빠르고 일방 통행의 길이어서 여행 시간을 많이 왜곡 할 것이므로 일방 통행의 거리에 대한 무언가에 대해 우려하고 있습니다. – user2033412
@ user2033412 일방 통행 거리를 처리하는 최악의 알고리즘이 없습니다. 실제 도로 네트워크는 당연히 그다지 적대적이지 않으며, 일방 통행 도로가 이론상의 문제를 해결하기위한 가장 단순한 ** 이론적 ** 가정은 아니라고 가정합니다. 일방 통행을 무시하고 구현할 필요는 없습니다. –
그래서 나는 일방 통행 거리를 알고 그것을 어떻게 수행하는지 살펴 보도록 구현할 것이다. 직감적으로 20에 가까운 _k_에 대한 결과는 좋지만 1에 가까운 _k_에 대한 결과는 더 나빠질 것이라고 생각합니다. – user2033412
k는 얼마나 큽니까? –
_k_은 20보다 작습니다. – user2033412