직교 좌표를 배열하기위한 알고리즘

Question

다음과 같은 형태의 직교 좌표 점이 있습니다. (x, y)
여기서 x와 y는 모두 음수가 아닌 정수입니다.

예 :
(0,0), (1,1), (0,1)

제가
다른 변경 X 어느 한 지점에서가 이러한 방식으로 상기 지점
를 배열하는 알고리즘이 필요 또는 y를 1로 변경하십시오.

즉, 나는 피하고 싶습니다.
대각선 방향 이동.

따라서 위에서 언급 한 점은
(0,0), (0,1), (1,1)과 같이 정렬됩니다.

마찬가지로 (0,0), (1,1), (0,2)
과 같은 배열은 없습니다.

나는
전화를하지만 난 그것을 맨하탄 주문라고 부르는 확실하지 않다.

아무도 도와 줄 수 있습니까?

Answer 1

당신은 정점을 반복하지 않는 배열을 찾고 있습니다.

일반 격자 그래프의 경우 NP 완료로 알려져 있습니다 (Hamilton Paths in Grid Graphs 참조).

아마도 해밀턴 경로/유클리드 여행 세일즈맨 문제로 알려진 대략적인/경험적/등 알고리즘을 사용하여 행운을 시험해 볼 수 있습니다.

---

하면 반복 할 수있는 배열을 찾고 있지만 배열 포인트의 가능한 최소 수를하려는 경우 :

이 다시 NP 완성입니다. 위의 문제는 그것으로 줄일 수 있습니다. 이것은 그래프에 해밀턴 경로가있는 경우에만 n 개의 꼭지점을 가질 수 있기 때문입니다.

---

방금 ​​포인트의 일부 배열을 찾고 있다면,

그런 다음 그래프가 연결되어 있는지 확인하기 만하면됩니다. 연결되어 있지 않으면 그러한 배치가 될 수 없습니다.

깊이 우선 검색을 통해 확인할 수 있습니다. 깊이 우선 검색은 그래프가 연결되어있는 경우에도 그러한 배열을 제공합니다.

만약 당신이 뭔가를 최적에 가깝게 (그러나 합리적으로 빠른 시간에) 원한다면 Euclidean Traveling Salesman 문제에 근사 알고리즘을 사용할 수 있습니다.

Answer 2

이것은 각 연속 점 사이의 거리를 최소화하면서 단순화 될 수 있습니다. (0,0)에서 (0,1)로가는 것은 단순히 1 단위이지만, (0,0)에서 (1,1)로가는 것은 실제로 sqrt (2)입니다. 따라서 점을 그래프로 배열 한 다음 간단한 최소 총 거리 탐색 (세일즈맨 출장)을 수행하면 올바르게 정렬해야합니다.

편집 : 1보다 큰 단계를 원하지 않으면 1보다 큰 가장자리를 추가하지 마십시오. 탐색은 여전히 ​​올바르게 작동하고 이동이 필요한 경로는 무시하십시오> 1

편집 2 : 더 명확히하기 위해 원하는 모든 가장자리 선택 알고리즘을 사용할 수 있습니다. 만약 당신이 2 칸을 움직이는 것이 좋다면, 그 칸이 대각선이 아닌 한, (0,2)와 (0,4) 사이에 모서리를 놓을 수도 있습니다. 최소 거리 알고리즘은 여전히 ​​작동합니다. 단순히 가장자리를 현명한 방법으로 배치하고 결과를 결정하기 위해 원하는 수의 선택 기준을 사용할 수 있습니다.

Answer 3

이 작업을 수행하는 한 가지 방법은 정렬 된 두 개의 좌표 목록을 만드는 것입니다. 하나는 x로 정렬되고 하나는 y로 정렬됩니다. 그런 다음 재귀 적으로 솔루션을 찾습니다.

코드가 올 것입니다 (아직 어떤 언어인지, 아마도 의사 코드일까요?) ... 편집 - 내 대답이 다른 사람들처럼 어둡기 때문에 좋지 않습니다.

Answer 4

꼭지점을 점으로하고 가장자리를 유효한 단계로 구성하여 그래프를 만들 수 있습니다.

당신이 찾고있는 것은 Hamiltonian path입니다. 이것은 일반적인 형태로 NP 완전 문제입니다. 이는 알려진 효율적인 솔루션이 없음을 의미합니다 (즉, 포인트의 수와 잘 맞습니다). 임의의 정점에서

시작을하지 방문한 이웃이있는 경우 계속 : 위키 백과는 "대부분의 그래프에 빠르게"이고 사용이 될 수있는 randomized algorithm에 대해 설명합니다.방문하지 않은 이웃이 더 이상없고, 형성된 경로가 해밀턴이 아닌 경우, 무작위로 이웃을 일정하게 선택하고 그 이웃을 피벗으로 사용하여 회전합니다. (즉, 해당 이웃에 가장자리를 추가하고 루프를 형성하지 않도록 해당 이웃에서 기존 가장자리 중 하나를 제거하십시오.) 그런 다음 경로의 새 끝에서 알고리즘을 계속 진행하십시오.

이 특정 상황에 대해보다 효율적인 해결책이있을 수 있습니다.

Answer 5

각 노드가 최대 네 개의 가장자리 인 그래프로 생각하십시오. 그런 다음 깊이/너비 우선 검색을 수행하십시오.

뭘 찾는 것 같다 것은 그리드 그래프에서 해밀턴 경로 :

Answer 6

브 루트 포스 재귀 REXX 루틴은 어떻게 될까요? 가능한 모든 경로를 시도해보고 올바르게 인쇄하십시오.

/* rexx */ 
point. = 0 /* Boolean for each existing point */ 
say 'Enter origin x and y coordinate:' 
pull xo yo 
point.xo.yo = 1 /* Point exists... */ 
say 'Enter destination x and y coordinate:' 
pull xd yd 
point.xd.yd = 1 /* Point exists... */ 
say 'Enter remaining x and y coordinates, one pair per line:' 
do forever 
    pull x y 
    if x = '' then leave 
    point.x.y = 1 
end 

path = '' 
call findpath xo yo path 
say 'All possible paths have been displayed' 
return 

findpath: procedure expose point. xd yd 
arg x y path 
if \point.x.y then return    /* no such point */ 
newpoint = '(' || x y || ')' 
if pos(newpoint, path) > 0 then return /* abandon on cycle */ 
if x = xd & y = yd then     /* found a path */ 
    say path newpoint 
else do         /* keep searching */ 
    call findpath x+1 y path newpoint 
    call findpath x-1 y path newpoint 
    call findpath x y+1 path newpoint 
    call findpath x y-1 path newpoint 
    end 
return 

예 세션 :

Path.rex 
Enter origin x and y coordinate: 
0 0 
Enter destination x and y coordinate: 
2 2 
Enter remaining x and y coordinates, one pair per line: 
0 1 
1 1 
2 1 
1 2 

(0 0) (0 1) (1 1) (2 1) (2 2) 
(0 0) (0 1) (1 1) (1 2) (2 2) 
All possible paths have been displayed 

그래도 큰 아무것도 시도하지 마십시오 - 시간이 오래 걸릴 수 있습니다! 그러나 그때 질문은 결코 최적의 해결책이되는 것에 대해서는 언급하지 않았습니다.