Lập trình Puzzle: Làm thế nào để vẽ một bảng?

Question

Có một bảng N x M chúng ta nên vẽ. Chúng tôi có thể vẽ toàn bộ hàng hoặc toàn bộ cột cùng một lúc. Với một ma trận N x M màu của tất cả các ô của bảng, hãy tìm số lượng hoạt động vẽ tối thiểu để vẽ bảng.

Ví dụ: chúng ta nên vẽ một bảng 3 x 3 như sau (R - đỏ, B - xanh, G - màu xanh lá cây):

B, B, B
B, R, R
B , G, G

số tối thiểu của các hoạt động vẽ tranh là 4:

• sơn hàng 0 với Blue
• sơn hàng 1 với Red
• sơn dòng 2 với Green
• Sơn cột 0 với Blue

Làm thế nào bạn sẽ giải quyết nó?

Answer 1

Để bắt đầu, bạn có thể thử một tìm kiếm đầy đủ thông tin thông báo đầy đủ.

Cho đồ thị trạng thái của bạn là: G=(V,E) trong đó V = {all possible boards} và E = {(u,v) | you can move from board u to v within a single operation}.

• Lưu ý rằng bạn không cần phải tạo ra các đồ thị trước - bạn có thể tạo ra nó một cách nhanh chóng, sử dụng một hàm successors(board), mà trả lại tất cả những người kế vị hội đồng quản trị nhất định.

Bạn cũng sẽ cần h:V->R - một admissible heuristic function rằng đánh giá ban .

Bây giờ, bạn có thể chạy A* hoặc bi-directional tìm kiếm BFS [hoặc kết hợp cả hai], nguồn của bạn sẽ là bảng trắng và mục tiêu của bạn là bảng được yêu cầu. Bởi vì chúng tôi sử dụng chức năng heuristic chấp nhận được - A * là cả hai complete (luôn luôn tìm thấy một giải pháp nếu có tồn tại) và optimal (tìm giải pháp ngắn nhất), nó sẽ tìm ra giải pháp tốt nhất. [cùng với BFS hai hướng].

nhược điểm:

• Mặc dù các thuật toán được thông báo, nó sẽ có hành vi mũ. Nhưng nếu nó là một câu hỏi phỏng vấn, tôi tin rằng một giải pháp không hiệu quả là tốt hơn thì không có giải pháp.
• Mặc dù hoàn thành và tối ưu - nếu không có giải pháp - thuật toán có thể bị kẹt trong vòng lặp vô hạn hoặc vòng lặp rất dài ít nhất cho đến khi nó nhận ra nó có exuahsted tất cả các khả năng.

(1) ví dụ cho heuristic, chấp nhận là h(board) = #(miscolored_squares)/max{m,n}

Answer 2

này trông giống như một vấn đề thú vị. Hãy để tôi chụp ảnh với một số mã giả.

Function MinPaints(Matrix) Returns Integer 
    If the matrix is empty return 0 
    Find all rows and columns which have a single color 
    If there are none, return infinity, since there is no solution 
    Set the current minimum to infinity 
    For each row or column with single color: 
     Remove the row/column from the matrix 
     Call MinPaints with the new matrix 
     If the result is less than the current minimum, set the current minimum to the result 
    End loop 
    Return the current minimum + 1 
End Function 

Tôi nghĩ rằng sẽ giải quyết được vấn đề của bạn, nhưng tôi đã không thử bất kỳ tối ưu hóa hay gì cả. Tuy nhiên, điều này có thể không đủ nhanh, tôi không biết. Tôi nghi ngờ vấn đề này có thể giải quyết được trong thời gian phụ theo cấp số nhân.

Sau đây là cách thuật toán này sẽ giải quyết ví dụ:

BBB 
BRR 
BGG 
| 
+---BRR 
| BGG 
| | 
| +---RR 
| | GG 
| | | 
| | +---GG 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | +---RR 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | Solvable in 2 
| | 
| Solvable in 3 
|      BB 
+---Another branch with RR ... 
|      GG 
Solvable in 4