Sắp xếp ma trận 2D nhị phân?

Question

Tôi đang tìm một số gợi ý ở đây vì tôi không biết bắt đầu nghiên cứu cái này ở đâu.

Tôi có một ma trận 2D với 0 hoặc 1 trong mỗi tế bào, chẳng hạn như:

1 2 3 4 
A 0 1 1 0 
B 1 1 1 0 
C 0 1 0 0 
D 1 1 0 0 

Và tôi muốn sắp xếp nó để nó là như "tam giác trên" càng tốt, như vậy:

4 3 1 2 
B 0 1 1 1 
A 0 1 0 1 
D 0 0 1 1 
C 0 0 0 1 

Hàng và cột phải giữ nguyên vẹn, tức là các phần tử không thể di chuyển riêng lẻ và chỉ có thể hoán đổi "toàn bộ".

Tôi hiểu rằng chắc chắn sẽ có những trường hợp bệnh lý mà một ma trận có nhiều khả năng kết quả sắp xếp (tức là cùng một hình dạng, nhưng khác nhau về danh tính của "bản gốc" hàng/cột.)

Vì vậy, có thể bất cứ ai đề nghị nơi tôi có thể tìm thấy một số điểm khởi đầu cho điều này? Một thư viện/thuật toán hiện có sẽ rất tuyệt, nhưng tôi sẽ giải quyết để biết tên của vấn đề mà tôi đang cố giải quyết!

Tôi nghi ngờ đó là vấn đề đại số tuyến tính như vậy và có thể có một số loại kỹ thuật xử lý hình ảnh có thể áp dụng.

Bất kỳ ý tưởng nào khác, dự đoán ban đầu của tôi là viết một loại chèn đơn giản trên các hàng, sau đó các cột và lặp lại cho đến khi nó ổn định (và hy vọng phát hiện các trường hợp bệnh lý không quá khó.)

Chi tiết khác: Một số thông tin khác về những gì tôi đang cố gắng làm có thể giúp làm rõ. Mỗi hàng đại diện cho một đối thủ cạnh tranh, mỗi cột đại diện cho một thách thức. Mỗi 1 hoặc 0 đại diện cho "thành công" cho đối thủ cạnh tranh về một thách thức cụ thể. Bằng cách phân loại ma trận sao cho tất cả 1 đều ở trên cùng bên phải, tôi hy vọng sẽ cung cấp xếp hạng về độ khó nội tại của mỗi thử thách và xếp hạng của đối thủ cạnh tranh (điều này sẽ tính đến độ khó của những thách thức mà họ gặp phải.). thành công, không chỉ là số lần thành công.)

Lưu ý về câu trả lời được chấp nhận: Tôi đã chấp nhận Mô phỏng ủ là "câu trả lời" với lời nhắc rằng câu hỏi này không có câu trả lời đúng. Nó có vẻ như là một cách tiếp cận tốt, mặc dù tôi đã không thực sự quản lý để đến với một chức năng chấm điểm mà làm việc cho vấn đề của tôi.

Answer 1

Thuật toán dựa trên simulated annealing có thể xử lý loại điều này mà không cần quá nhiều sự cố. Không tuyệt vời nếu bạn có ma trận nhỏ mà rất có thể hae một giải pháp cố định, nhưng tuyệt vời nếu ma trận của bạn có được lớn hơn và vấn đề trở nên khó khăn hơn.

(Tuy nhiên, nó cũng không mong muốn của bạn mà chèn có thể được thực hiện từng bước.)

Chuẩn

1. Vạch một hàm hiệu suất mà "điểm" một ma trận - ma trận được gần gũi hơn với tam giác của bạn sẽ có điểm số tốt hơn so với những điểm ít tam giác hơn.

2. Thiết lập một tập hợp các hoạt động được cho phép trên ma trận. Mô tả của bạn hơi mơ hồ, nhưng nếu bạn có thể trao đổi hàng thì một op sẽ là SwapRows(a, b). Số khác có thể là SwapCols(a, b).

Các deo vòng

Tôi sẽ không đưa ra một giải trình đầy đủ ở đây, nhưng ý tưởng rất đơn giản. Bạn thực hiện các phép biến đổi ngẫu nhiên trên ma trận bằng cách sử dụng các phép toán của bạn. Bạn đo lượng ma trận "tốt hơn" sau khi hoạt động (sử dụng hàm hiệu suất trước và sau khi hoạt động). Sau đó, bạn quyết định có nên cam kết chuyển đổi đó hay không. Bạn lặp lại quá trình này rất nhiều.

Quyết định có cam kết biến đổi hay không là phần thú vị: bạn cần phải quyết định có thực hiện thao tác đó hay không. Đến cuối quá trình ủ, bạn chỉ chấp nhận các phép biến đổi để cải thiện điểm số của ma trận. Nhưng trước đó, trong một thời gian hỗn loạn hơn, bạn cho phép biến đổi không cải thiện điểm số. Ban đầu, thuật toán là "nóng" và mọi thứ diễn ra. Cuối cùng, thuật toán nguội đi và chỉ cho phép biến đổi tốt. Nếu bạn tuyến tính mát thuật toán, sau đó lựa chọn xem có nên chấp nhận một sự chuyển đổi là:

public bool ShouldAccept(double cost, double temperature, Random random) { 
    return Math.Exp(-cost/temperature) > random.NextDouble(); 
} 

Bạn nên đọc kỹ thông tin tuyệt vời chứa trong Numerical Recipes để biết thêm thông tin về thuật toán này.

Câu chuyện dài ngắn, bạn nên tìm hiểu một số thuật toán mục đích chung này. Làm như vậy sẽ cho phép bạn giải quyết các lớp lớn các vấn đề khó giải quyết một cách phân tích.

thuật toán Chấm điểm

Đây có lẽ là phần khó khăn nhất. Bạn sẽ muốn đưa ra một cầu thủ ghi bàn hướng dẫn quá trình ủ để hướng tới mục tiêu của bạn. Người ghi bàn nên là một chức năng liên tục dẫn đến số lượng lớn hơn khi ma trận tiếp cận giải pháp lý tưởng.

Làm cách nào để đo lường "giải pháp lý tưởng" - hình tam giác? Đây là một cầu thủ ghi bàn ngây thơ và dễ dàng: Đối với mọi điểm, bạn biết liệu nó có nên là 1 hoặc 0.Thêm +1 vào điểm nếu ma trận là đúng, -1 nếu nó sai. Dưới đây là một số mã để tôi có thể được rõ ràng (không kiểm tra! Xin vui lòng xem!)

int Score(Matrix m) { 
    var score = 0; 
    for (var r = 0; r < m.NumRows; r++) { 
     for (var c = 0; c < m.NumCols; c++) { 
      var val = m.At(r, c); 
      var shouldBe = (c >= r) ? 1 : 0; 
      if (val == shouldBe) { 
       score++; 
      } 
      else { 
       score--; 
      } 
     } 
    } 
    return score; 
} 

Với thuật toán điểm này, trường ngẫu nhiên của 1s và 0s sẽ đưa ra một số điểm là 0. Một "đối diện" tam giác sẽ cung cấp cho các điểm số âm nhất, và giải pháp chính xác sẽ cho điểm tích cực nhất. Khác biệt hai điểm sẽ cho bạn chi phí.

Nếu trình ghi điểm này không hoạt động cho bạn, thì bạn sẽ cần phải "điều chỉnh" nó cho đến khi nó tạo ra ma trận bạn muốn.

Thuật toán này dựa trên tiền đề điều chỉnh trình ghi điểm này đơn giản hơn nhiều so với việc thiết lập thuật toán tối ưu để sắp xếp ma trận.

Answer 2

Dưới đây là một điểm khởi đầu:

Chuyển đổi mỗi hàng từ bit nhị phân thành một số

Sắp xếp các số theo thứ tự giảm dần.

Sau đó chuyển đổi mỗi hàng trở lại thành nhị phân.

Answer 3

thuật toán cơ bản:

1. Xác định số tiền hàng và lưu trữ giá trị. Xác định tổng cột và lưu trữ các giá trị.
2. Sắp xếp tổng số hàng theo thứ tự tăng dần. Sắp xếp cột khoản tiền theo thứ tự tăng dần.

Hy vọng rằng, bạn nên có ma trận gần với vùng tam giác trên bên phải càng tốt.

Answer 4

Tôi đã đưa ra thuật toán dưới đây và có vẻ như hoạt động chính xác.

Giai đoạn 1: di chuyển các hàng có nhiều nhất 1 s lên và cột nhiều nhất 1 s.

1. Đầu tiên các hàng. Sắp xếp các hàng bằng cách đếm 1 s của chúng. Chúng tôi không quan tâm nếu 2 hàng có cùng số lượng 1 s.
2. Bây giờ, các cột. Sắp xếp các cols bằng cách đếm số 1 s của chúng. Chúng tôi không quan tâm nếu 2 cols có cùng số lượng 1 s.

Giai đoạn 2: lặp lại giai đoạn 1 nhưng với tiêu chí thêm, để chúng ta đáp ứng các ma trận morph hình tam giác.
Tiêu chí cho hàng: nếu 2 hàng có cùng số lượng 1 s, chúng tôi di chuyển lên hàng bắt đầu với ít hơn 0 s.

Tiêu chí cho cols: nếu 2 cols có cùng số 1 s, chúng tôi di chuyển đúng các col rằng có ít 0 s ở phía dưới.

---

Ví dụ:

Giai đoạn 1

1 2 3 4      1 2 3 4     4 1 3 2 
A 0 1 1 0     B 1 1 1 0     B 0 1 1 1 
B 1 1 1 0 - sort rows-> A 0 1 1 0 - sort cols-> A 0 0 1 1 
C 0 1 0 0     D 1 1 0 0     D 0 1 0 1 
D 1 1 0 0     C 0 1 0 0     C 0 0 0 1 

Giai đoạn 2

4 1 3 2      4 1 3 2 
B 0 1 1 1     B 0 1 1 1 
A 0 0 1 1 - sort rows-> D 0 1 0 1 - sort cols-> "completed" 
D 0 1 0 1     A 0 0 1 1 
C 0 0 0 1     C 0 0 0 1 

Edit: nó chỉ ra rằng thuật toán của tôi không cho ma trận tam giác đúng luôn.
Ví dụ:

Giai đoạn 1

1 2 3 4     1 2 3 4     
A 1 0 0 0     B 0 1 1 1     
B 0 1 1 1 - sort rows-> C 0 0 1 1 - sort cols-> "completed" 
C 0 0 1 1     A 1 0 0 0     
D 0 0 0 1     D 0 0 0 1     

Giai đoạn 2

1 2 3 4     1 2 3 4     2 1 3 4 
B 0 1 1 1     B 0 1 1 1     B 1 0 1 1 
C 0 0 1 1 - sort rows-> C 0 0 1 1 - sort cols-> C 0 0 1 1 
A 1 0 0 0     A 1 0 0 0     A 0 1 0 0 
D 0 0 0 1     D 0 0 0 1     D 0 0 0 1 
          (no change) 

(*) Có lẽ một giai đoạn 3 sẽ làm tăng tốt kết quả. Trong giai đoạn đó, chúng tôi đặt các hàng bắt đầu với ít hơn 0 s ở trên cùng.

Answer 5

Treat hàng như số nhị phân, với cột tận cùng bên trái là bit quan trọng nhất, và sắp xếp chúng theo thứ tự giảm dần, trên xuống dưới

Hãy đối xử với các cột như số nhị phân với dòng dưới cùng là bit quan trọng nhất và sắp xếp chúng theo thứ tự tăng dần, từ trái sang phải.

Lặp lại cho đến khi bạn đạt đến điểm cố định. Chứng minh rằng thuật toán chấm dứt trái như là một bài tập cho người đọc.

Answer 6

Tìm một bài báo năm 1987 của Anna Lubiw về "Thứ tự gấp đôi ma trận của ma trận".

Có một trích dẫn bên dưới. Việc đặt hàng không giống với những gì bạn đang tìm kiếm, nhưng là khá gần. Nếu không có gì khác, bạn sẽ có thể có được một ý tưởng khá tốt từ đó.

http://dl.acm.org/citation.cfm?id=33385