Thuật toán để sắp xếp các điểm Descartes

Question

Tôi có vài điểm Descartes dạng: (x, y)
trong đó x và y đều là số nguyên không âm.

Ví dụ:
(0,0), (1,1), (0,1)

Tôi cần một thuật toán để sắp xếp các điểm nêu trên
theo cách như vậy mà đi từ một điểm đến
thay đổi khác hoặc x hoặc y bằng 1.

Nói cách khác, tôi muốn tránh
chuyển động chéo.

Vì vậy, các điểm nêu trên sẽ được sắp xếp như sau:
(0,0), (0,1), (1,1).

Tương tự cho (0,0), (1,1), (0,2)
không có sự sắp xếp như vậy.

Tôi không chắc chắn về những gì gọi nó là
nhưng tôi sẽ gọi nó là Đặt hàng Manhattan.

Có ai giúp được không?

Answer 1

Nếu bạn đang tìm kiếm một sự sắp xếp mà không lặp lại đỉnh:

gì bạn dường như muốn tìm một con đường Hamilton trong một Graph Grid.

Điều này được biết là NP-Hoàn chỉnh cho đồ thị lưới chung, xem Hamilton Paths in Grid Graphs.

Vì vậy, bạn có thể thử vận ​​may của mình bằng bất kỳ thuật toán gần đúng/heuristic/etc nào được biết đến cho Hamiltonian Path/Euclidean Traveling Salesman Problem.

---

Nếu bạn đang tìm kiếm một sự sắp xếp có thể lặp lại, nhưng muốn số có thể tối thiểu của điểm trong sự sắp xếp:

Đây lại là NP-đầy đủ. Vấn đề trên có thể được giảm xuống. Điều này là do đi bộ tối thiểu có thể có n đỉnh nếu và chỉ khi đồ thị có một con đường hamiltonian.

---

Nếu bạn chỉ là tìm kiếm một số bố trí điểm,

Sau đó, tất cả các bạn cần làm là kiểm tra xem đồ thị được kết nối. Nếu nó không được kết nối, có thể không có sự sắp xếp như vậy.

Bạn có thể thực hiện tìm kiếm độ sâu đầu tiên để tìm ra điều đó. Độ sâu tìm kiếm đầu tiên cũng sẽ cung cấp cho bạn một sự sắp xếp như vậy trong trường hợp đồ thị được kết nối.

Nếu bạn muốn một cái gì đó gần gũi hơn với tối ưu (nhưng trong thời gian hợp lý nhanh), bạn có thể sử dụng các thuật toán xấp xỉ cho vấn đề Euclidean Traveling Salesman.

Answer 2

Điều này có thể được đơn giản hóa như giảm thiểu khoảng cách giữa mỗi điểm liên tiếp. Đi từ (0,0) đến (0,1) đơn giản là 1 đơn vị, nhưng đi từ (0,0) đến (1,1) thực ra là sqrt (2). Vì vậy, nếu bạn sắp xếp các điểm vào một đồ thị, và sau đó thực hiện một traversal tối thiểu tổng số khoảng cách đơn giản (đi du lịch nhân viên bán hàng), nó nên sắp xếp chúng một cách chính xác.

Chỉnh sửa: Nếu bạn không bao giờ muốn một bước lớn hơn 1, chỉ cần không thêm bất kỳ cạnh nào lớn hơn 1. Traversal sẽ vẫn hoạt động chính xác và bỏ qua bất kỳ đường dẫn nào cần chuyển động> 1.

Chỉnh sửa 2: Để làm rõ hơn, bạn có thể sử dụng bất kỳ thuật toán chọn cạnh nào bạn muốn. Nếu bạn ổn với nó di chuyển 2 không gian, miễn là không gian không phải là đường chéo, sau đó bạn có thể chọn để đặt một cạnh giữa (0,2) và (0,4). Thuật toán khoảng cách tối thiểu sẽ vẫn hoạt động. Đơn giản chỉ cần đặt các cạnh một cách thông minh và bạn có thể sử dụng bất kỳ số lượng tiêu chí lựa chọn nào để xác định kết quả.

Answer 3

Một cách để thực hiện việc này là tạo hai danh sách sắp xếp tọa độ. Một được sắp xếp theo x và một được sắp xếp theo y. Sau đó, đệ quy tìm một giải pháp.

Mã sắp tới (không biết ngôn ngữ nào; có thể giả mã?) ... Chỉnh sửa - không bao giờ, vì câu trả lời của tôi không tốt bằng một số ngôn ngữ khác.

Answer 4

Bạn có thể tạo biểu đồ có các đỉnh là điểm của bạn và các cạnh là các bước hợp lệ.

Những gì bạn đang tìm kiếm là Hamiltonian path cho biểu đồ này. Điều này, trong hình thức chung của nó, là một vấn đề NP-hoàn thành, có nghĩa là không có giải pháp hiệu quả được biết đến (tức là một giải pháp có quy mô tốt với số điểm). Wikipedia mô tả một số randomized algorithm là "nhanh trên hầu hết các đồ thị" và có thể được sử dụng:

Bắt đầu từ một đỉnh ngẫu nhiên và tiếp tục nếu không có hàng xóm.Nếu không có thêm hàng xóm chưa được thăm dò nào và đường dẫn được tạo thành không phải là Hamilton, hãy chọn ngẫu nhiên một người hàng xóm và xoay vòng bằng cách sử dụng hàng xóm đó làm trục xoay. (Tức là, thêm một cạnh cho hàng xóm đó, và loại bỏ một trong các cạnh hiện có từ hàng xóm đó để không tạo thành một vòng lặp.) Sau đó, tiếp tục thuật toán ở đầu mới của đường dẫn.

Một giải pháp hiệu quả hơn có thể tồn tại cho trường hợp cụ thể này.

Answer 5

Hãy coi đó là biểu đồ trong đó mỗi nút có tối đa bốn cạnh. Sau đó thực hiện tìm kiếm chiều sâu/chiều rộng.

Answer 6

Làm thế nào về một thói quen REXX đệ qui bạo lực ... Hãy thử tất cả các đường dẫn có thể và in những thứ đó hoạt động. phiên

/* 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 

Ví dụ:

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 

Đừng cố gắng này trên bất cứ điều gì lớn mặc dù - có thể mất một thời gian rất dài! Nhưng sau đó câu hỏi không bao giờ đề cập đến bất cứ điều gì về việc là một giải pháp tối ưu.