Bài toán tìm đoạn ít đường nhất. (3 người xem)

[tamhoang.pm]

Tôi có 65 cột và mỗi cột rải rác (random) các số 1 và ô trắng.

Xin mọi người giúp tôi đoạn code tìm ra ít nhất các cột ghép lại thỏa mãn điều kiện tổng của tất cả các dòng phải lớn hơn hoặc = 1.

Nếu có nhiều kết quả thì ... lấy hết các kết quả ít nhất đó.

Cảm ơn mọi người.

 

[haonlh]

Tôi có 65 cột và mỗi cột rải rác (random) các số 1 và ô trắng.

Xin mọi người giúp tôi đoạn code tìm ra ít nhất các cột ghép lại thỏa mãn điều kiện tổng của tất cả các dòng phải lớn hơn hoặc = 1.

Nếu có nhiều kết quả thì ... lấy hết các kết quả ít nhất đó.

Cảm ơn mọi người.

Nếu đúng như bạn nhấn mạnh ở từ in đậm thì tôi ấy cột nào cũng được (1 cột, tức là ít nhất là 1 cột), tổng các số trên cột đó của tất cả các dòng đều >=1 (bạn có tính ở dòng 61)

Xin hãy nói rõ câu hỏi

 

[Ba Tê]

Tôi có 65 cột và mỗi cột rải rác (random) các số 1 và ô trắng.

Xin mọi người giúp tôi đoạn code tìm ra ít nhất các cột ghép lại thỏa mãn điều kiện tổng của tất cả các dòng phải lớn hơn hoặc = 1.

Nếu có nhiều kết quả thì ... lấy hết các kết quả ít nhất đó.

Cảm ơn mọi người.

Tìm ra rồi làm sao?
Bạn có cột cuối là tổng các cột, dòng 55 là 2, là số nhỏ nhất >1, tô màu dòng 55 là xong.
Hay là tôi chưa hiểu rõ yêu cầu........

 

[doveandrose]

Tìm ra rồi làm sao?
Bạn có cột cuối là tổng các cột, dòng 55 là 2, là số nhỏ nhất >1, tô màu dòng 55 là xong.
Hay là tôi chưa hiểu rõ yêu cầu........

cái chữ tổng của tất cả các dòng không phải là công thức ở cột BN đâu bác Ba à , nó chỉ là tượng trưng thôi .
Tổng ở đây là tổng của mỗi dòng trên những cột nào mà bác Ba chọn phải lớn hơn 1 .
Ví dụ bác Ba chọn cột tổ hợp cột (BL,BM) thì mỗi phép toán sum(BL2:BM2) cho tới sum(BL60:BM60) đều phải >=1 .
Bài toán này là tìm ra tổ hợp cột nào đó có số cột ít nhất để thỏa mãn điều kiện trên .

 

[huuthang_bd]

Tôi có 65 cột và mỗi cột rải rác (random) các số 1 và ô trắng.

Xin mọi người giúp tôi đoạn code tìm ra ít nhất các cột ghép lại thỏa mãn điều kiện tổng của tất cả các dòng phải lớn hơn hoặc = 1.

Nếu có nhiều kết quả thì ... lấy hết các kết quả ít nhất đó.

Cảm ơn mọi người.

Tôi không đủ kiên nhẫn để test dữ liệu của bạn.
Bạn thử sửa code để test dữ liệu của bạn xem mất mấy giờ .

Code này có thể sửa lại để cải thiện tốc độ nhưng với dữ liệu của bạn chắc cũng không ăn thua.

Sub CallMe()
Dim ArrData, ArrMissing() As Long, Min As Long, Result() As Long, ArrResult()
ArrData = Sheet3.Range("A2:Z20").Value
Min = UBound(ArrData, 2) + 1
ReDim Result(0 To 0)
ReDim ArrMissing(0 To UBound(ArrData, 1))
For i = 1 To UBound(ArrMissing, 1)
    ArrMissing(i) = i
Next
ReDim ArrResult(0 To 0)
FindResult ArrResult, Result, ArrMissing, ArrData, 1, Min
Sheet2.UsedRange.ClearContents
For i = 1 To UBound(ArrResult, 1)
    Sheet2.Cells(i, 1).Resize(, Min + 1).Value = ArrResult(i)
Next
End Sub

Private Sub FindResult(ByRef ArrResult, ByVal Result, ByVal ArrMissing, ByRef ArrData, ByVal Col As Long, ByRef Min As Long)
Dim i As Long, Result0() As Long, ArrMissing0() As Long
If Col > UBound(ArrData, 2) Then Exit Sub
If UBound(Result, 1) >= Min Then Exit Sub
Result0 = Result
ArrMissing0 = ArrMissing
If Not CheckCol(Result, ArrMissing, ArrData, Col) Then
    FindResult ArrResult, Result, ArrMissing, ArrData, Col + 1, Min
Else
    If UBound(Result, 1) < Min Then
        Min = UBound(Result, 1)
        ReDim ArrResult(0 To 1)
        ArrResult(1) = Result
    Else
        ReDim Preserve ArrResult(0 To UBound(ArrResult, 1) + 1)
        ArrResult(UBound(ArrResult, 1)) = Result
    End If
End If
FindResult ArrResult, Result0, ArrMissing0, ArrData, Col + 1, Min
End Sub

Private Function CheckCol(ByRef Result, ByRef ArrMissing, ByRef ArrData, ByRef Col As Long) As Boolean
Dim i As Long
For i = UBound(ArrMissing, 1) To 1 Step -1
    If ArrData(ArrMissing(i), Col) > 0 Then
        ArrMissing(i) = ArrMissing(UBound(ArrMissing, 1))
        ReDim Preserve ArrMissing(0 To UBound(ArrMissing, 1) - 1)
    End If
Next
ReDim Preserve Result(0 To UBound(Result, 1) + 1)
Result(UBound(Result, 1)) = Col
CheckCol = (UBound(ArrMissing, 1) = 0)
End Function

 

[tamhoang.pm]

Dùng thuật toán vét cạn để xử lý. (Đáp án là 14 cột)
Nhưng phải áp dụng điều kiện để bẻ gãy các nhánh (nhằm bỏ qua các trường hợp thừa).

Cái này như lập trình giải thuật giải Sudoku... nhưng khó hơn. Tôi post lên để mọi người giúp làm sao bẻ gãy các nhánh không cần thiết .... (Nếu như chạy bo thì chắc phải mất cả ngày mới xong).....

Chính vì quá lâu nên mong mọi người giúp .....

 

[tamhoang.pm]

cái chữ tổng của tất cả các dòng không phải là công thức ở cột BN đâu bác Ba à , nó chỉ là tượng trưng thôi .
Tổng ở đây là tổng của mỗi dòng trên những cột nào mà bác Ba chọn phải lớn hơn 1 .
Ví dụ bác Ba chọn cột tổ hợp cột (BL,BM) thì mỗi phép toán sum(BL2:BM2) cho tới sum(BL60:BM60) đều phải >=1 .
Bài toán này là tìm ra tổ hợp cột nào đó có số cột ít nhất để thỏa mãn điều kiện trên .

Như ở trên tôi nói! Đáp án bài này là 14 cột mà (ít cột nhất) phù hợp điều kiện Dòng nào cũng có ít nhất 1 giá trị 1 (Nghĩa là tổng của bất kỳ dòng nào của 14 cột đó đều >=1).

Nhưng hiện tại nếu quét hết trường hợp (Ví dụ chưa biết KQ là 14) thì phải mất cả ngày mới ra ...
Mong anh em giúp đỡ giải thuật nào đó đơn giản mà code chạy nhanh giúp mình ... Để sau này phát triển lên ma trận lớn hơn với n cột, m dòng ... cũng sẽ xử lý dễ dàng hơn.

 

[HieuCD]

HuHu chỉ tìm được 15 cột không biết sai chổ nào
[TABLE="width: 427"]
[TR]
[TD="class: xl64, width: 35"]2[/TD]
[TD="class: xl63, width: 27"]3[/TD]
[TD="class: xl63, width: 27"]5[/TD]
[TD="class: xl63, width: 27"]1[/TD]
[TD="class: xl63, width: 27"]16[/TD]
[TD="class: xl63, width: 27"]7[/TD]
[TD="class: xl63, width: 34"]10[/TD]
[TD="class: xl63, width: 34"]54[/TD]
[TD="class: xl63, width: 27"]34[/TD]
[TD="class: xl63, width: 27"]57[/TD]
[TD="class: xl63, width: 27"]9[/TD]
[TD="class: xl65, width: 27"]19[/TD]
[TD="class: xl63, width: 27"]14[/TD]
[TD="class: xl63, width: 27"]23[/TD]
[TD="class: xl63, width: 27"]41[/TD]
[/TR]
[/TABLE]

 

[tamhoang.pm]

HuHu chỉ tìm được 15 cột không biết sai chổ nào
[TABLE="width: 427"]
[TR]
[TD="class: xl64, width: 35"]2[/TD]
[TD="class: xl63, width: 27"]3[/TD]
[TD="class: xl63, width: 27"]5[/TD]
[TD="class: xl63, width: 27"]1[/TD]
[TD="class: xl63, width: 27"]16[/TD]
[TD="class: xl63, width: 27"]7[/TD]
[TD="class: xl63, width: 34"]10[/TD]
[TD="class: xl63, width: 34"]54[/TD]
[TD="class: xl63, width: 27"]34[/TD]
[TD="class: xl63, width: 27"]57[/TD]
[TD="class: xl63, width: 27"]9[/TD]
[TD="class: xl65, width: 27"]19[/TD]
[TD="class: xl63, width: 27"]14[/TD]
[TD="class: xl63, width: 27"]23[/TD]
[TD="class: xl63, width: 27"]41[/TD]
[/TR]
[/TABLE]

Bạn đưa code lên mọi người nghiên cứu được không?
Code của tôi là code dùng vòng lặp nên chạy cả ngày mới xong nên đưa lên anh chị em cười chết ...

Kết quả: [TABLE="width: 546"]
[TR]
[TD="width: 39, align: right"]14[/TD]
[TD="width: 39, align: right"]15[/TD]
[TD="width: 39, align: right"]1[/TD]
[TD="width: 39, align: right"]29[/TD]
[TD="width: 39, align: right"]6[/TD]
[TD="width: 39, align: right"]49[/TD]
[TD="width: 39, align: right"]50[/TD]
[TD="width: 39, align: right"]21[/TD]
[TD="width: 39, align: right"]10[/TD]
[TD="width: 39, align: right"]36[/TD]
[TD="width: 39, align: right"]12[/TD]
[TD="width: 39, align: right"]13[/TD]
[TD="width: 39, align: right"]39[/TD]
[TD="width: 39, align: right"]57[/TD]
[/TR]
[/TABLE]

Đây chỉ là 1 KQ thôi! chưa lấy được hết KQ như code của bạn @huuthang_bd

Chạy ra đc 1kq đã oải quá rồi nên stop lại ...

 

[HieuCD]

Bạn đưa code lên mọi người nghiên cứu được không?
Code của tôi là code dùng vòng lặp nên chạy cả ngày mới xong nên đưa lên anh chị em cười chết ...

Kết quả: [TABLE="width: 546"]
[TR]
[TD="width: 39, align: right"]14[/TD]
[TD="width: 39, align: right"]15[/TD]
[TD="width: 39, align: right"]1[/TD]
[TD="width: 39, align: right"]29[/TD]
[TD="width: 39, align: right"]6[/TD]
[TD="width: 39, align: right"]49[/TD]
[TD="width: 39, align: right"]50[/TD]
[TD="width: 39, align: right"]21[/TD]
[TD="width: 39, align: right"]10[/TD]
[TD="width: 39, align: right"]36[/TD]
[TD="width: 39, align: right"]12[/TD]
[TD="width: 39, align: right"]13[/TD]
[TD="width: 39, align: right"]39[/TD]
[TD="width: 39, align: right"]57[/TD]
[/TR]
[/TABLE]

Đây chỉ là 1 KQ thôi! chưa lấy được hết KQ như code của bạn @huuthang_bd

Chạy ra đc 1kq đã oải quá rồi nên stop lại ...

Khi nào tìm được 14 cột sẽ gởi lên, nếu không được sẽ trốn luôn

 

[tamhoang.pm]

Khi nào tìm được 14 cột sẽ gởi lên, nếu không được sẽ trốn luôn

Quan trọng code của bạn chạy lâu không? chứ tớ đã ngồi nghĩ mãi rồi! không có điều kiện nào khả thi bẻ gãy nhánh mà không bị bỏ sót trường hợp.... vì vậy nếu muốn quét hết trường hợp thì dùng thuật toán vét cạn mà ở đây dữ liệu cũng chưa phải là lớn lắm mà đã chạy mất cả ngày mới xong

 

[huuthang_bd]

Nhưng phải áp dụng điều kiện để bẻ gãy các nhánh (nhằm bỏ qua các trường hợp thừa).

Đây chính là chỗ tôi nói có thể cải thiện tốc độ. Nếu hôm nay rảnh sẽ sửa lại xem có ăn thua không.

 

[tamhoang.pm]

Đây chính là chỗ tôi nói có thể cải thiện tốc độ. Nếu hôm nay rảnh sẽ sửa lại xem có ăn thua không.

Bạn huuthang_bd có facebook không tôi hỏi chút ... vì trong code có nhiều đoạn không hiểu hết tôi cũng mới học lập trình.

 

[huuthang_bd]

Bạn huuthang_bd có facebook không tôi hỏi chút ... vì trong code có nhiều đoạn không hiểu hết tôi cũng mới học lập trình.

Muốn hỏi gì sao bạn không hỏi ở đây luôn. Phương pháp đệ quy hơi trừu tượng. Muốn giải thích cho rõ ràng cũng không dễ.

 

[tamhoang.pm]

Đúng thật là trừu tượng! chạy code phân tích mà chả hiểu gì luôn

Bạn giải thích giúp mình cách tìm cột thỏa mãn điều kiện nào thì bỏ bớt được không?

 

[tamhoang.pm]

Nếu số trường hợp tìm thấy lớn hơn số cột hiện có thì giảm số cột có đi 1 giá trị.

(nghĩa là số cột tối thiểu sẽ giảm đi 1 >> Cứ như vậy..... cho đến khi số trường hợp ít hơn số cột tối thiểu thì dừng)...

Khi số cột của bạn tìm thấy là 4 thì vòng lặp 4 cột cho 26 >>> nhanh
chứ số vòng lặp 14 cho 65 thì không nhanh đc.

Quay về cách xét xem cột nào không thỏa mãn thì bỏ không bao giờ xét đến nó nữa >>> chắc sẽ cải thiện hơn về tốc độ...

 

[huuthang_bd]

Nếu số trường hợp tìm thấy lớn hơn số cột hiện có thì giảm số cột có đi 1 giá trị.

(nghĩa là số cột tối thiểu sẽ giảm đi 1 >> Cứ như vậy..... cho đến khi số trường hợp ít hơn số cột tối thiểu thì dừng)...

Khi số cột của bạn tìm thấy là 4 thì vòng lặp 4 cột cho 26 >>> nhanh
chứ số vòng lặp 14 cho 65 thì không nhanh đc.

Quay về cách xét xem cột nào không thỏa mãn thì bỏ không bao giờ xét đến nó nữa >>> chắc sẽ cải thiện hơn về tốc độ...

Bạn làm đi tôi học hỏi
Theo bạn cột như thế nào là không thỏa mãn và có thể bỏ không xét nữa??? Một cột không thỏa mãn ở nhóm cột này nhưng ghép với các cột khác để có kết quả.

 

[minhtungph]

bài này giống lập trình mấy con engine đánh cờ quá

 

[malang]

Dùng thuật toán vét cạn để xử lý. (Đáp án là 14 cột)
Nhưng phải áp dụng điều kiện để bẻ gãy các nhánh (nhằm bỏ qua các trường hợp thừa).

Cái này như lập trình giải thuật giải Sudoku... nhưng khó hơn. Tôi post lên để mọi người giúp làm sao bẻ gãy các nhánh không cần thiết .... (Nếu như chạy bo thì chắc phải mất cả ngày mới xong).....

Chính vì quá lâu nên mong mọi người giúp .....

Có code rui, sao bạn không post lên mọi người xem sửa cho, đã đi nhờ lại muốn làm từ A..Z chăng, hơn nữa để mọi người xem cóp phát triển được ý tưởng của bạn

Thấy bạn nói về vét cạn chứng tỏ biết lập trình rùi , vậy tôi chỉ góp ý tưởng sơ khai cải thiện tốc độ nhanh ở đây thôi, bạn phải tự làm tiếp và rồi post kết quả lên đây.

trong file của bạn post ở bài 1,
(1)
- Đặt công thức sau

=IF(COLUMN(A:A)>$BN2,"",LARGE(INDEX($A2:$BM2*COLUMN($A2:$BM2),0),$BN2+1-COLUMN(A:A)))

tại BP2,
- Copy công thức trên cho toàn vùng BP2:BU60

- Nhìn vào vùng BP2:BU60 sẽ hiểu, giờ ta cần lặp đêquy hay vét cạn như thế nào cho ít nhất số lặp, và lưu ý cột nào đã xét thì các dòng mà trên cột đó chứa 1 thì sẽ không cần xét nữa, ...

(2) thêm chút cho phần tăng sự nhận biết

tại A63 nhập công thức sau

=IF(ROW(1:1)>A$61,"",LARGE(INDEX(A$2:A$60*ROW(A$2:A$60),0),A$61+1-ROW(1:1)))

copy công thức cho toàn vùng A63:BM70 --> các con số gì đây?



Qua (1) và (2) trên sẽ hiểu nên lập trình sao cho quét ít nhất, như thế giúp chặn các nhánh tốt , ngoài ra thì như ý bạn, là khi tìm được số cột - nếu so với min số cột hiện thời mà bằng hoặc lớn hơn (vẫn chưa ra kết quả)-- thì lùi lại chọn cột khác, Cứ vậy là xong

(*) vậy bạn thử triển khai code theo ý tưởng đó , xem có nhanh hơn không, và up kết quả cuối cho tất cả cùng tham khảo, cũng như cần hỏi gì cứ hỏi tiếp ở đây

 

[tamhoang.pm]

Bạn làm đi tôi học hỏi
Theo bạn cột như thế nào là không thỏa mãn và có thể bỏ không xét nữa??? Một cột không thỏa mãn ở nhóm cột này nhưng ghép với các cột khác để có kết quả.

Tôi mới nghĩ ra như vậy chứ chưa tìm đc cách nào ....