그래프에서 가장 가까운 점에서 시작점까지의 점

Question

이 문제를 오랫동안 파악하지 못했습니다. 우리가 항상 (0,0)의 원점에있는 미리 정의 된 루트를 가진 2D 평면을 가지고 있다고 가정 해 봅시다. 이 2D 평면에는 얼마나 큰지에 대한 제한이 없습니다.

사용자가이 그래프에서 유한 한 수의 점을 입력 할 수 있다고 가정 해 봅시다 (각 점은이 평면에있을 수 있습니다). 이 점은 S0, S1, ... Sn으로 정의되며 사용자는이 점의 각각의 X, Y 좌표 위치를 제공합니다.

루트 지점에서 그래프의 모든 지점까지 최단 경로 길이를 찾고 싶습니다.

무엇을 의미합니까? : 최단 경로가 6으로 결정했다고 가정 해 봅시다. 이는 루트 지점에서 지점 S0까지의 경로 길이가 6이고 경로 길이가

이

내 그림 참조 : 부인을 내 다이어그램의 목적이다 S1 루트가 6 인, 주석 루트에서 경로 길이 내가이 문제를 해결하려고 한 일을 6

입니다 내 생각의 과정을 보여줘. 이 문제에 어떻게 접근하고 싶은지를 나타내는 것이 아닙니다.

이 예제에서는 모든 점이 균등하게 이격되어 있다고 가정합니다. 내가하려고 한 것은 포인트 사이의 중간 점을 찾는 것입니다. 예를 들어, S0와 S1 사이의 중간 점은 A입니다. S2와 S3 사이의 중간 점은 B입니다. A와 B 사이의 중간 점은 C입니다. 루트 점은 C까지 이어지며 그래프의 모든 점과 동일한 거리를 이동할 수 있습니다. 그래프에서 루트에서 ANY 지점까지의 최단 경로 길이는이 예제에서 4입니다. 즉, 루트에서 S0로가는 가장 짧은 방법은 루트에서 S1까지 얻을 수있는 가장 짧은 방법과 같습니다. 루트에서 S1까지 얻을 수있는 가장 짧은 방법은 해당하는 가장 짧은 방법과 같습니다. 루트에서 S3까지

문제는이 방법이 항상 작동하지 않는다는 것입니다. 특히 비행기를 가로 질러 무작위로 흩어져있는 비 루트 지점이 홀수 일 때 더욱 그렇습니다. 알고리즘을 찾을 수 없습니다. 누구든지 나를위한 포인터/팁이 있습니까?

Answer 1

Here is the formula 두 지점 사이의 거리를 결정합니다. 모든 사용자 지정 점 (s0, s1 ... sN)에 대한 루트에서 거리를 계산하고 결과 집합에서 최소값을 얻으십시오.

Answer 2

그래프에서 루트에서 ANY 지점까지의 최단 경로 길이는이 예제에서 4입니다. 즉, 루트에서 S0로가는 가장 짧은 방법은 루트에서 S1까지 얻을 수있는 가장 짧은 방법과 같습니다. 루트에서 S1까지 얻을 수있는 가장 짧은 방법은 해당하는 가장 짧은 방법과 같습니다. 루트에서 S3으로.

및

그들은 90 개도 할 필요가 없습니다.

은 그래서 당신이 정말로 말하고있는 것은 :

나는 모든 등거리 루트에있는 각 사용자 입력 지점과 끝에서 시작 라인을 만들

.

루트에서 가장 먼 지점을 찾아 거리 (X)를 계산하십시오. X와 같은 루트와 같은 거리에있는 모든 점에 선은 직선입니다. 다른 모든 점에는 거리가 X 인 임의의 곡선 선을 만듭니다.

예 (선은 거리에 비례하지 않습니다.

Answer 3

나는 가장 먼 지점으로 원점에서 연결이 직선해야한다는 에릭 필립스에 동의하는 경향이있다. 여러 포인트가 가장 큰 명예를 공유하면 모두 직선을 ​​얻습니다. 나머지 점에 대해서는 기존 직선에 연결하는 것이 중요합니다.

하는 샘플 문제에이 기술 및 각 지점에 원점에서의 거리를 적용하는 것은 ≈ 3.16