01/10/2018, 14:12

Xin ý tưởng bài tập về ma trận

Cho ma trận vuông C = (cij) cấp N (1<= i, j <= N<=100) gồm N^2 số tự nhiên (các số không nhất
thiết phải khác nhau) ghi lại trong file matran.in theo khuôn dạng sau :

  • Dòng đầu tiên ghi lại số tự nhiên N là cấp của ma trận vuông C;
  • N dòng kế tiếp ghi lại ma trận vuông C = (cij). Hai phần tử khác nhau của ma trận
    được ghi cách nhau bởi một vài khoảng trống.
    Hãy sử dụng thuật toán quay lui viết chương trình lấy trên mỗi hàng, mỗi cột duy nhất
    một phần tử của ma trận C sao cho tổng các phần tử này là nhỏ nhất. Kết quả tìm được
    ghi lại trong file ketqua.out theo khuôn dạng:
  • Dòng đầu tiên ghi lại tổng giá trị nhỏ nhất của N phần tử tìm được;
  • N dòng kế tiếp, mỗi dòng ghi lại ba số i, j, cij tương ứng với chỉ số hàng, chỉ số cột
    và giá trị phần tử tương ứng của ma trận. Ba số được viết cách nhau một vài khoảng
    trống.
    Ví dụ về file matran.in và ketqua.out:
    matran.in
    6
    10 64 57 29 18 15
    34 20 19 30 16 12
    57 49 40 16 11 19
    29 21 46 26 21 18
    28 16 11 21 21 37
    15 12 15 48 37 30
    ketqua.out
    82
    1 1 10
    2 6 12
    3 4 16
    4 5 21
    5 3 11
    6 2 12
rogp10 viết 16:16 ngày 01/10/2018

Bài này duyệt trâu là 100! nếu là min thì chặt nhánh thôi (max mới phải gần đúng).

Một ý tưởng ta sẽ dùng cả min_col_idx[] và min_row_idx[] để “tham”, tức là gom hết những phần tử khác nhau để làm prefix.

MRI = [1, 6, 5, 6, 3, 2]
MCI = [1, 6, 5, 5, 3, 2]

ta thấy rằng MCI[MRI[2]] = 2 nên ta giữ [1, 6, 5, X, 3, 2].

Lam Ngọc viết 16:22 ngày 01/10/2018

Mình vẫn chưa hiểu cách duyêt lắm. Bạn nói rõ hơn đc không?

viết 16:29 ngày 01/10/2018
en.wikipedia.org

Hungarian algorithm

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm...

coi trên topcoder ko hiểu gì hết @_@

topcoder.com

Community - Data Science - Data Science Tutorials - Assignment Problem and...

Community - Data Science - Data Science Tutorials - Assignment Problem and Hungarian Algorithm

rogp10 viết 16:26 ngày 01/10/2018
  • Lấy mỗi số trên dòng trừ đi min của dòng đó.
  • Rồi lấy mỗi số trên cột trừ đi min của cột đó.

Những số 0 trong ma trận rất quan trọng.

  • Chọn 0 theo dòng: Nếu dòng có đúng 1 số 0 thì đánh dấu nó và gạch bỏ dòng đó.
  • Chọn 0 theo cột: tương tự.

Nếu số số 0 < số dòng thì:

  • Cộng trả lại min của phần chưa gạch vào các giao điểm đường gạch.
  • Trừ những phần tử chưa gạch với min.
  • Làm lại từ đầu.
    Ngược lại, kết quả là vị trí của tất cả số 0 được chọn.

Đây là một ma trận khác:
08 10 12 16
11 11 15 08
09 06 05 14
15 14 09 07
1: [0 2 4 8 | 3 3 7 0 | 4 1 0 9 | 8 7 2 0]
2T: [0 3 4 8 | 1 2 0 6 | 4 7 0 2 | 8 0 9 0]
2: [0 1 4 8 | 3 2 7 0 | 4 0 0 9 | 8 6 2 0]
bỏ: cột 1, cột 4.
Bỏ qua 1, 4: gạch dòng 3. Chỉ mới có 3 số 0 thôi.
Dòng 3 trở thánh: [5 0 0 10].
Ma trận: [0 0 3 8 | 3 1 6 0 | 4 0 0 9 | 8 5 1 0]

Do 0 là min rồi nên ta bỏ: cột 4; dòng 1, dòng 3. Mới có 3 số 0 thôi.

Lam Ngọc viết 16:19 ngày 01/10/2018

yes. mình hiểu rồi. cảm ơn b nhiều nha

Bài liên quan
0