Tìm số tối thiểu cục bộ trong ma trận n x n trong thời gian O (n)

Question

Vì vậy, đây không phải là câu hỏi về nhà của tôi, nhưng nó được lấy từ một bài tập về nhà không được phân loại của khóa học coursera về thuật toán và cấu trúc dữ liệu (hiện đã hoàn thành).

Bạn được cung cấp một mạng lưới n bằng n số riêng biệt. Một số là số tối thiểu địa phương nếu nó nhỏ hơn tất cả các nước láng giềng của nó. (Một người hàng xóm của một số là ngay lập tức ở trên, bên dưới, bên trái, hoặc bên phải. Hầu hết các số có bốn hàng xóm; số ở bên có ba; bốn góc có hai.) Sử dụng thiết kế thuật toán phân chia và đánh dấu mô hình để tính toán mức tối thiểu của địa phương chỉ bằng O (n) so sánh giữa các cặp số. (Lưu ý: vì có n con số trong đầu vào, bạn không thể đủ khả năng để xem xét tất cả trong số họ Gợi ý:. Hãy suy nghĩ về những gì loại tái phát sẽ cung cấp cho bạn những mong muốn trên ràng buộc.)

Kể từ khi các con số không theo thứ tự nào, tôi không thấy cách chúng ta có thể lấy đi bất kỳ thứ gì nhưng O (n) so sánh.

Answer 1

Chúng tôi có thể điều chỉnh câu trả lời của Từ Giống như câu trả lời của Jared, bằng cách xem nó có thể sai như thế nào.

Ý tưởng trong câu trả lời đó - một câu trả lời hay - là "cuộn xuống dốc". Điều này chỉ có nghĩa là, nếu bạn đang ở trên một yếu tố, kiểm tra xem nó là một tối thiểu địa phương. Nếu vậy, bạn đã hoàn thành; nếu không, hãy bước đến hàng xóm nhỏ nhất gần nhất. Cuối cùng điều này phải chấm dứt bởi vì mỗi bước là một phần tử nhỏ hơn, và điều đó không thể đi mãi mãi trong một mảng hữu hạn.

Vấn đề với phương pháp này là các "cán" có thể quanh co khắp nơi:

20 100 12 11 10 100 2 
19 100 13 100 9 100 3 
18 100 14 100 8 100 4 
17 16 15 100 7 6 5 

Nếu bạn bắt đầu ở phía trên bên trái và "cuộn xuống dốc", bạn sẽ ghé thăm khoảng một nửa trong số các yếu tố trong mảng. Đó là quá nhiều, vì vậy chúng ta phải hạn chế nó một chút.

Bắt đầu bằng cách kiểm tra cột giữa và hàng giữa. Tìm yếu tố nhỏ nhất trong số đó và bắt đầu ở đó.

Cuộn một bước "xuống dưới" từ đó để nhập một trong bốn phần tư. Bạn sẽ nhập một trong các góc tọa độ, bởi vì các phần tử liền kề ở cột giữa và/hoặc hàng lớn hơn, do đó chỉ một trong hai phần tư liền kề có thể là "xuống dốc".

Bây giờ, hãy xem xét điều gì sẽ xảy ra nếu bạn "cuộn xuống dưới" từ đó. Rõ ràng, bạn cuối cùng sẽ đạt đến mức tối thiểu địa phương. (Chúng tôi sẽ không thực sự làm điều này bởi vì nó sẽ mất quá lâu.) Nhưng, trong quá trình lăn xung quanh, bạn sẽ không bao giờ rời khỏi góc phần tư đó ... Bởi vì làm như vậy, bạn sẽ phải vượt qua cột giữa hoặc hàng giữa và không có yếu tố nào nhỏ hơn nơi bạn bắt đầu. Do đó góc phần tư chứa một địa phương tối thiểu ở đâu đó.

Vì vậy, trong thời gian tuyến tính, chúng tôi đã xác định được góc phần tư phải chứa mức tối thiểu địa phương và chúng tôi đã cắt giảm một nửa. Bây giờ chỉ cần recurse.

Thuật toán này cần thời gian 2n + 2n/2 + 2n/4 + ..., bằng 4n, là O (n) vì vậy chúng tôi đã hoàn tất.

Thật thú vị, chúng tôi không sử dụng "lăn xuống dốc" nhiều lắm, ngoại trừ phần quan trọng: Chứng minh rằng thuật toán hoạt động.

[Cập nhật]

Như Incassator points out, câu trả lời này là không hoàn toàn đúng, bởi vì sau khi bạn "chỉ recurse" bạn có thể cuộn ra khỏi góc phần tư một lần nữa ...

Việc sửa chữa đơn giản nhất là tìm ra phần tử nhỏ nhất giữa hàng giữa, cột giữa, và ranh giới trước khi bạn "cuộn xuống dưới".

Answer 2

Tôi nghĩ điều này thực sự rất dễ dàng.

Biến vấn đề thành 3-D để xem tại sao thuật toán hoạt động. Đặt ma trận lên bàn. Giả sử có các cột mở rộng ra khỏi mỗi ô và chiều cao của cột là tỷ lệ thuận với giá trị của nó. Đặt một quả bóng trên bất kỳ trụ cột nào. Có quả bóng luôn rơi vào trụ tiếp giáp đó là độ cao thấp nhất cho đến khi nó ở mức tối thiểu cục bộ.

Answer 3

Xin lỗi, điều này chỉ khiến tôi quan tâm rất lâu sau đó. Tôi nghi ngờ câu trả lời được đưa ra mặc dù. Đây là lý do tại sao.

Để nhận được O (n), giải pháp phải đảm bảo rằng chúng tôi sẽ không bao giờ quay lại trong tìm kiếm của mình, tức là trong thời trang ngược lại. Tuy nhiên, vì các con số đều khác biệt (thực sự không khác biệt làm cho vấn đề khó khăn hơn), điều này có thể xảy ra.

Hãy tưởng tượng một cầu thang xoắn ốc bắt đầu ở một góc là điểm cao nhất và sau đó xoắn ốc vào trong và xuống dưới. Nếu cầu thang vuông, thì trung tâm là minima địa phương duy nhất cũng như minima toàn cầu. Trong trường hợp đó kể từ khi chúng tôi đang bắt đầu trung tâm, chúng tôi chỉ có thể nhận được may mắn. Tuy nhiên, mặt cắt ngang của cầu thang có thể hơi không đối xứng, trong trường hợp đó dung dịch sẽ không hoạt động. Bởi vì chúng ta không thể tránh được lượt quay đầu trong khi tìm kiếm.

Answer 4

Câu trả lời được chấp nhận bởi Nemo là tốt đẹp, nhưng không hoàn toàn chính xác:

Như vậy, trong thời gian tuyến tính, chúng tôi đã xác định được một góc phần tư mà phải chứa tối thiểu địa phương, và chúng tôi đã cắt n một nửa. Bây giờ chỉ cần recurse.

Tôi đang đề cập đến "chỉ cần recurse" bit. Vấn đề là chúng ta không thể làm điều đó trực tiếp vì trên phiên bản kế tiếp chúng ta có thể tìm thấy một tối thiểu địa phương mà là không tối thiểu địa phương cho lưới ban đầu (x dưới đây có nghĩa là một số lượng lớn tùy ý):

x x 39 x x 50 x x x x x 
x x 38 x x 49 x x x x x 
37 36 33 34 35 48 x x x x x 
x x 32 x 1 10 x x x x x 
x x 31 x x 47 x x x x x 
46 45 30 44 43 60 51 52 53 54 55 
x x 2 x x 56 x x x x x 
x x x x x 57 x x x x x 
x x x x x 58 x x x x x 
x x x x x 59 x x x x x 

Tại lặp đầu tiên chúng tôi tìm 10 là tối thiểu hàng giữa và cột giữa. Chúng tôi đi bên trái (như 1 nhỏ hơn 10). Vì vậy, lặp lại tiếp theo của chúng tôi là trên góc phần tư trên bên trái. Nhưng bây giờ tối thiểu giữa hàng và cột sẽ là 31 (hoặc 30 nếu biên giới góc phần tư được coi là một phần của nó). Sau đó, bạn sẽ kết luận rằng đó là mức tối thiểu địa phương. Nhưng nó không phải là cho lưới đầy đủ.

Chúng tôi có thể khắc phục lỗi không may này theo nhiều cách khác nhau. Tôi đã giải quyết nó như sau:

Tại mỗi lần lặp lại ngoài chính lưới, chúng tôi theo dõi ứng viên tối thiểu hiện tại (đó là 1 trong ví dụ trên sau lần lặp đầu tiên; cộng với vô cùng). Chúng tôi tính toán tối thiểu giữa hàng và cột và so sánh nó với ứng cử viên tối thiểu. Nếu sau nhỏ hơn, chúng tôi recurse vào góc phần tư chứa ứng cử viên tối thiểu. Nếu không, chúng ta quên ứng cử viên trước đó và chỉ sau đó kiểm tra xem mức tối thiểu giữa hàng/cột mới có thực sự là mức tối thiểu cục bộ hay không. Và nếu không sau đó recurse như bình thường cho bất kỳ góc phần tư chúng tôi dốc xuống từ nó (và theo dõi ứng viên tối thiểu mới).Ngoài ra, bạn có thể sửa đổi quy trình như được mô tả trong this presumably MIT lecture: tại mỗi lần lặp thay vì nhìn vào hàng/cột giữa, bạn có thể nhìn vào hàng giữa/cột và đường viền lưới. Sau đó, thuật toán một lần nữa là chính xác.

Bạn chọn cách bạn muốn.

Answer 5

Vâng, đây là cách bạn chia và chinh phục nó.

1) Chia ma trận n x n thành bốn ma trận phụ n/2 x n/2.

2) Giữ chia ma trận tiểu đệ quy cho đến khi bạn kết thúc với một ma trận 2 x 2

3) Kiểm tra xem bất kỳ yếu tố của 2 x 2 ma trận là một tối thiểu địa phương.

phương trình tái phát là: T (n) = 4 * T (n/2) + O (1)

4 * T (n/2) cho 4 n/2 xn/2 ma trận phụ và O (1) để kiểm tra xem ma trận phụ 2 x 2 có số tối thiểu cục bộ

định lý chính cho biết đây là trường hợp xấu nhất bị ràng buộc O (n^2).

Nhưng tôi nghĩ rằng chúng tôi có thể nhận được một trường hợp tốt nhất O (n) ràng buộc,

("RED ALERT! --- NHẤT TRƯỜNG HỢP là không có thật, JUST giả --- RED ALERT!").

nếu chúng ta thoát khỏi đệ quy stack sau khi chúng tôi đã đã tìm thấy một địa phương tối thiểu trong bước 3.

Mã giả:

private void FindlocalMin(matrix,rowIndex,colIndex,width){ 
    if(width == 1){ checkForLocalMinimum(matrix,rowIndex,colIndex); return;} //2x2 matrix 
    FindlocalMin(matrix,rowIndex,colIndex,width/2); 
    FindlocalMin(matrix, (rowIndex + (width/2) + 1) ,colIndex,width/2); 
    FindlocalMin(matrix,rowIndex, (colIndex + (width/2) + 1) ,width/2); 
    FindlocalMin(matrix,(rowIndex + (width/2) + 1), (colIndex + (width/2) + 1) ,width/2); 
} 

private void checkForLocalMinimum(.........){ 
    if(found Local Minimum in 2x2 matrix){ exit recursion stack;} 
} 

Đây là một java implementation