Liệt kê tổ hợp chập k của nhóm n phần tử.

[NguyenNgocThuHien]

Giới thiệu cùng mọi người một file dùng để liệt kê tổ hợp chập k của n phần tử. Có một số thành viên có hỏi về vấn đề này nên mình làm thử, cũng thấy ngon ngon. Chỉ việc chạy macro, bấm, bấm, chọn chọn là có thể có kết quả như ý muốn.
Link file: https://drive.google.com/drive/folders/1hpD6jvBPgaYTGOaQdCyYtNYr4a2ltIbj

Mọi chi tiết tham khảo video sau:

 

[VetMini]

Thế có bạn nào biết cách giải tối ưu bài toán qua sông không?
Thuật toán này cũng khá dễ viết code.

 

[anhtuanle123]

mình nghĩ thuật toán trên là tối ưu rùi đó !
nhưng mà tuân theo quy tắc 2 người qua 1 người về , và nó là vét cạn các trường hợp ,
mình chưa cài nhánh cận để loại các trường hợp thời gian lớn hơn thời gian đã tìm được ( để bác nào quan tâm thì nghiên cứu thêm ^^ )!
nếu tìm được trường hợp nào <29S thì cũng thank vì có cách mới ^^

 

[VetMini]

Tôi hỏi thuật toán giải a(1 to n) với a(1) = t1, a(2) = t2, ..., a(n) = tn

 

[NguyenNgocThuHien]

Thế có bạn nào biết cách giải tối ưu bài toán qua sông không?
Thuật toán này cũng khá dễ viết code.

Uổi, nếu là tìm cách để sang sông nhanh nhất thì cứ chọn một người lái thuyền cố định, người này là người qua sông nhanh nhất là được.

 

[VetMini]

Uổi, nếu là tìm cách để sang sông nhanh nhất thì cứ chọn một người lái thuyền cố định, người này là người qua sông nhanh nhất là được.

Chúng ta nói chuyện toán số chơi cho vui.
Theo thuật toán của bạn thì nếu ta có mảng { t1, t2, ...., tn } sẽ tính ra thời gian tối ưu là

t(n) + t(1) + t(n-1) + t(1) + ... + t(2)
= t(n) + t(n-1) + ... t(2) + (n-2)*t(1)
= t(n) + t(n-1) + ... t(1) + (n-3)*t(1)
Đương nhiên là bài toán chỉ tính nếu n > 2

 

[VetMini]

Tiếp tục thuật toán qua sông:
Ví dụ ta có 4 người, thời gian qua sông của mỗi người là t1, t2, t3, t4. Sắp xếp t1 <= t2 <= t3 <= t4

Dùng thuật toán như đề nghị ở bài #24 và diễn đạt ở bài #25, tạm gọi là thuật toán "chọn người cố định" thì thời gian như sau:
( >>> có nghĩa là qua sông, <<< có nghĩa là về, tg là thời gian )
t1 + t4 >>> ; tg = t4
t1 <<< ; tg = t1
t1 + t3 >>> ; tg = t3
t1 <<< ; tg = t1
t1 + t2 >>> ; tg = t2
Tổng tg = 2 * t1 + t2 + t3 + t4

Thử một thuật toán, tạm gọi là "cặp đôi gần nhất":
t1 + t2 >>> ; tg = t2
t1 <<< ; tg = t1
t3 + t4 >>> ; tg = t4
t2 <<< ; tg = t2
t1 + t2 >>> ; tg = t2
Tổng tg = t1 + 3 * t2 + t4

So sánh:
2 * t1 + t2 + t3 + t4 :: t1 + 3 * t2 + t4
t1 + t3 <> t2 + t2
Điều này cho thấy nếu t3 tương đối lớn so với t2 thì phương pháp bài #24 không cho ra tối ưu.

Thuật toán của tôi là lấy ra 1 căp đầu, cộng với một cặp cuối thành ra 4. Dùng công thức trên để so sánh.
- Nếu "cặp đôi gần nhất" ưu việt hơn thì theo cách đó để đưa cặp đôi ấy sang, và tiếp tục lại với cặp cuối kế tiếp.
- Nếu "chọn người cố định" bằng hoặc ưu việt hơn thì kể từ đó dùng thuật toán này.

Nếu số phần tử là số lẻ thì lấy phần tử thứ 3 tính riêng. Chỗ còn lại sẽ là số chẵn bình thường.

 

[anhtuanle123]

thuật toán 1 nếu kết hợp với quay lui thì cũng ko vét cạn đc các trường hợp ,
thuật toán chọn cặp đôi gần nhất ko bít có xét ưu tiên gì để sớm tìm ra kết quả ko , và ko bít cách chọn cặp đôi có xét đc các trường hợp ko nếu quay lui!

mượn mô tả của bác ^^
" quay lui vét cạn các trường hợp " :
i=1->4 , j =i+1->5 , k=1->5 (cho mỗi bước )

t(i) + t(j) >>> ; tg = t(j)
t(k) <<< ; tg = t(k) --- quay lại bước 1
t(i) + t(j) >>> ; tg = t(j) --- quay lại bước 2
t(k) <<< ; tg = t(k) --- quay lại bước 3
t(i) + t(j) >>> ; tg = t(j) --- quay lại bước 4
t(k) <<< ; tg = t(k) --- quay lại bước 5
t(i) + t(j) >>> ; tg = t(j) --- quay lại bước 6

Tổng cách qua sông = (chỉnh hợp chập 2 của 5 cách qua sông)* (2 cách về ) * (chc 2 của 4 ) * (3)* (chc 2 của 3 ) * (4) * (chc 2 của 2)
Tổng tg=4*t(j)+3*t(k)

nói chung 2 người qua 1 người về thì luôn là 7 bước mới xong , mỗi bước sẽ có chiến thuật qua sao cho tối ưu và gọn nhẹ nhất !

 

[VetMini]

Cái chuyện tìm số cách đi nó chỉ là tìm số tổ hợp, không phải là bài toán tối ưu cho nên chả liên quan gì đến tốc dộ của mỗi người. Có chăng là chỉ dùng để tính thời gian cho mỗi cách đi.

Bài này thì cách tính tối ưu mới là bài tính cần nói.
Để tính tối ưu thì điểm cần phải biết là nếu hai ngừoi đi chung thì thời gian tính theo ngừoi chậm hơn. Vì vậy người đi nhanh chỉ có hiệu quả khi đi 1 mình (lượt về). Giải pháp ở bài #24 chính là nắm cái hiệu quả này. Tuy nhiên, giải pháp ấy đã bỏ qua đặc điểm thứ hai của hiệu quả là người đi chậm nhất sẽ có hiệu quả khi đi chung với ngừoi gần mình nhất. Bài toán ở #26 là bài toán chứng minh điểm biến đổi của hiệu quả từ phép đi 2 ngừoi chậm kèm nhau sang phép người nhanh kèm ngừoi chậm.

Dựa vào đó, tôi có thể viết code tính ra thời ngian ngắn nhất để đưa đoàn ngừoi sang sông.

 

[anhtuanle123]

người đi gần mình thì cũng nằm trong các trường hợp vét cạn thôi , người gần mình , người hơi gần mình , người nằm xa mình , người nằm hơi xa mình , nói chung phải phân ra thống kê thành từng nhóm mới biết đc hiệu quả , phương pháp thống kê tất nhiên cũng phải dùng 1 công cụ vét cạn nào đó để lọc ra tất cả các trường hợp , và họ tìm ra đặc điểm các cặp nằm gần nhau thì sẽ nhanh tìm ra kết quả hơn , nhưng nó là 1 kỹ thuật hẹp trong 1 kỹ thuật tổng quát , và kết quả cũng nằm trong 1 nhóm hẹp nào đó !
bài này nói chung mình ko nghiên cứu nhiều , nhưng mình nghĩ chắc có người dựa vào kết quả thống kê toàn bộ các bước đã tìm ra đc nguyên lý qua sông tối ưu , như là cặp đôi gần nhau chẳng hạn ^^

 

[NguyenNgocThuHien]

Sub LietKe()
    Dim cItem As Collection
    Dim kq(1 To 100, 1 To 2) As Variant
    Dim lIndex As Long
    Dim lTime As Long
    Set cItem = New Collection
    
    
    cItem.Add 1
    cItem.Add 3
    cItem.Add 6
    cItem.Add 8
    cItem.Add 12
    'cItem.Add 100
    
    kq(1, 1) = "Buoc"
    kq(1, 2) = "Thoi gian"
    lIndex = 1
    
    
    
    Do While cItem.Count <> 0
        If cItem.Count = 1 Then
            lIndex = lIndex + 1
            kq(lIndex, 1) = cItem.Item(1) & "Sang song"
            kq(lIndex, 2) = cItem.Item(1)
            lTime = cItem(1) + lTime
            Exit Do
        ElseIf cItem.Count = 2 Then
            lIndex = lIndex + 1
            kq(lIndex, 1) = "( " & cItem.Item(1) & " , " & cItem(2) & " ) " & " Sang song"
            kq(lIndex, 2) = cItem(2)
            lTime = cItem(2) + lTime
            
            Exit Do
            
        ElseIf cItem.Count = 3 Then
            lIndex = lIndex + 1 '1 2 sang song
            kq(lIndex, 1) = "( " & cItem.Item(1) & " , " & cItem(2) & " ) " & " Sang song"
            kq(lIndex, 2) = cItem(2)
            lTime = cItem(2) + lTime
            
            lIndex = lIndex + 1 '1 quay lai
            kq(lIndex, 1) = cItem.Item(1) & "Quay lai"
            kq(lIndex, 2) = cItem(1)
            lTime = cItem(1) + lTime
            
             lIndex = lIndex + 1 '1 3 sang song
            kq(lIndex, 1) = "( " & cItem.Item(1) & " , " & cItem(3) & " ) " & " Sang song"
            kq(lIndex, 2) = cItem(3)
            lTime = cItem(3) + lTime
            Exit Do
            
            
            
        Else
            lIndex = lIndex + 1 '1 2 sang song
            kq(lIndex, 1) = "( " & cItem.Item(1) & " , " & cItem(2) & " ) " & " Sang song"
            kq(lIndex, 2) = cItem(2)
            lTime = cItem(2) + lTime
            
            lIndex = lIndex + 1 '1 quay lai
            kq(lIndex, 1) = cItem.Item(1) & " quay lai"
            kq(lIndex, 2) = cItem(1)
            lTime = cItem(1) + lTime
            
             lIndex = lIndex + 1 '4 3 sang song
            kq(lIndex, 1) = "( " & cItem.Item(cItem.Count - 1) & " , " & cItem(cItem.Count) & " ) " & " Sang song"
            kq(lIndex, 2) = cItem(cItem.Count)
            lTime = cItem(cItem.Count) + lTime
            
             lIndex = lIndex + 1 '2 quay lai
            kq(lIndex, 1) = cItem.Item(2) & " quay lai"
            kq(lIndex, 2) = cItem(2)
            lTime = cItem(2) + lTime
            
            cItem.Remove cItem.Count
            cItem.Remove cItem.Count 'nguoi 1 và nguoi 2 van chua sang song
            
            
        End If
        
    Loop
    
    
    Range("o12").Resize(100, 2).Value = kq
    Range("o12").Offset(-1).Value = lTime
End Sub

 

[NguyenNgocThuHien]

Em chia nhỏ thành từng đợt rồi cho họ di chuyển, nguyên tắc là người nhanh nhất và người nhanh thứ 2 sẽ luân phiên chở khách.

 

[VetMini]

Em chia nhỏ thành từng đợt rồi cho họ di chuyển, nguyên tắc là người nhanh nhất và người nhanh thứ 2 sẽ luân phiên chở khách.

Trong bài #26 tôi đã lập luận toán cho thấy "ngừoi nhanh nhất và nhanh thứ hai luân phiên" chỉ có hiệu quả khi
2*t2 < t1 + t3

 

[VetMini]

Function CheoThuyen(mang, n)
' hàm tính thời gian ngắn nhất để mọi người cùng sang
' mang = mảng chứa thời gian của mỗi người, đã săp xếp thứ tự lớn dần
' n = số người còn chưa qua
Select Case n
Case 0
    CheoThuyen = 0
Case 1
    CheoThuyen = mang(1)
Case 2
    CheoThuyen = mang(2)
Case 3
    CheoThuyen = mang(3) + mang(1) + mang(2)
Case Else
    ' chọn  cách đi
    If (2 * mang(2) < mang(1) + mang(n - 1)) Then
        CheoThuyen = mang(1) + 2 * mang(2) + mang(n)      '___ 1&2 >>>, 1 <<<, n&n-1 >>>, 2 <<<
    Else
        CheoThuyen = 2 * mang(1) + mang(n - 1) + mang(n)      '___ 1&n >>>, 1 <<<, 1&n-1 >>>, 1 <<<
    End If
    ' tiếp tục chỗ còn lại
    CheoThuyen = CheoThuyen + CheoThuyen(mang, n - 2)
End Select
End Function

Sub t()
Debug.Print CheoThuyen([ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } ], 10) ' kết quả là 50
Debug.Print CheoThuyen([ { 1, 3, 6, 8, 12 } ], 5) ' kết quả là 29
End Sub

 

[NguyenNgocThuHien]

Function CheoThuyen(mang, n)
' hàm tính thời gian ngắn nhất để mọi người cùng sang
' mang = mảng chứa thời gian của mỗi người, đã săp xếp thứ tự lớn dần
' n = số người còn chưa qua
Select Case n
Case 0
    CheoThuyen = 0
Case 1
    CheoThuyen = mang(1)
Case 2
    CheoThuyen = mang(2)
Case 3
    CheoThuyen = mang(3) + mang(1) + mang(2)
Case Else
    ' chọn  cách đi
    If (2 * mang(2) < mang(1) + mang(n - 1)) Then
        CheoThuyen = mang(1) + 2 * mang(2) + mang(n)      '___ 1&2 >>>, 1 <<<, n&n-1 >>>, 2 <<<
    Else
        CheoThuyen = 2 * mang(1) + mang(n - 1) + mang(n)      '___ 1&n >>>, 1 <<<, 1&n-1 >>>, 1 <<<
    End If
    ' tiếp tục chỗ còn lại
    CheoThuyen = CheoThuyen + CheoThuyen(mang, n - 2)
End Select
End Function

Sub t()
Debug.Print CheoThuyen([ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } ], 10) ' kết quả là 50
Debug.Print CheoThuyen([ { 1, 3, 6, 8, 12 } ], 5) ' kết quả là 29
End Sub

trường hợp còn hơn4 người phải xét thêm điều kiện

 

[NguyenNgocThuHien]

Function CheoThuyen(mang, n)
' hàm tính thời gian ngắn nhất để mọi người cùng sang
' mang = mảng chứa thời gian của mỗi người, đã săp xếp thứ tự lớn dần
' n = số người còn chưa qua
Select Case n
Case 0
    CheoThuyen = 0
Case 1
    CheoThuyen = mang(1)
Case 2
    CheoThuyen = mang(2)
Case 3
    CheoThuyen = mang(3) + mang(1) + mang(2)
Case Else
    ' chọn  cách đi
    If (2 * mang(2) < mang(1) + mang(n - 1)) Then
        CheoThuyen = mang(1) + 2 * mang(2) + mang(n)      '___ 1&2 >>>, 1 <<<, n&n-1 >>>, 2 <<<
    Else
        CheoThuyen = 2 * mang(1) + mang(n - 1) + mang(n)      '___ 1&n >>>, 1 <<<, 1&n-1 >>>, 1 <<<
    End If
    ' tiếp tục chỗ còn lại
    CheoThuyen = CheoThuyen + CheoThuyen(mang, n - 2)
End Select
End Function

Sub t()
Debug.Print CheoThuyen([ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } ], 10) ' kết quả là 50
Debug.Print CheoThuyen([ { 1, 3, 6, 8, 12 } ], 5) ' kết quả là 29
End Sub

trường hợp còn hơn4 người phải xét thêm điều kiện

 

[VetMini]

trường hợp còn hơn4 người phải xét thêm điều kiện

Điều kiện gì?

Đây là bài toán tôi tính ra theo lý luận toán số, chưa được qua toán heuristic.
Vì vậy, tuy tôi khong nghĩ mình thiếu sót gì, nhưng tôi vẫn mở rộng để đón nhận ý kiến khác.

Các bạn có thể tự đặt ra những mảng với nhiều trường hợp đặc thù để chứng minh rằng có những trường hợp vẫn tính ra được thời gian NHỎ HƠN code trên.
Khi tôi thấy các trường hợp này, tôi sẽ nghiên cứu xem thuật toán của tôi hoặc hoàn toàn sai, hoặc còn khiếm khuyết chỗ nào cần bổ sung.

 

[anhtuanle123]

phương pháp của bác tính bằng tay thì thấy kết quả có vẻ đúng , nhưng ko biết dựa trên phương pháp nào , ko biết có phải là nội suy gì ko , để từ từ phân tích thêm ^^
nhưng hình như nó chỉ tìm đc thời gian ngắn nhất thôi , ko ghi lại thứ tự đc nhỉ !@@

trường hợp còn hơn4 người phải xét thêm điều kiện

những trường hợp bằng hoặc lớn hơn 4 có 1 chỗ gọi đệ quy đó bạn !
CheoThuyen = CheoThuyen + CheoThuyen(mang, n - 2)

 

[VetMini]

Giản dị vậy ghi lại thứ tự mần chi.
Nếu muốn ghi lại thì chỗ chú thích ấy, cứ việc thêm code cho nó ghi xuống

{ 1, 3, 4, 5, 6, 7, 8, 9, 10, 11 } (lưu ý: tôi cố tình chọn phần tử thứ 2 có thời gian là 3 để dễ so sánh)
lấy ra: 1, 2 và 10, 11
so sánh: 2*3 < 1 + 10 ==> chọn cách cặp: 1&3 >>>; 1 <<<; 10&11 >>>; 3 <<<
kết quả là đưa được 9&10 qua; còn lại 1 đến 8
lấy ra: 1, 2 và 8, 9
... (ra tương tự như trên)
lấy ra: 1, 2 và 6, 7
... (ra tương tự như trên)
lấy ra: 1, 2 và 4, 5
so sánh: 2*3 > 1 + 4 ==> chọn cách kèm: 1&4 >>>; 1 <<<; 1&5 >>>; 1 <<<
Còn lại 1&2 : qua luôn

 

[NguyenNgocThuHien]

Điều kiện gì?

những trường hợp bằng hoặc lớn hơn 4 có 1 chỗ gọi đệ quy đó bạn !
CheoThuyen = CheoThuyen + CheoThuyen(mang, n - 2)

Ý em là code ở bài 32 chưa phân thành hai trường hợp ý mà.

 

[NguyenNgocThuHien]

Em đã thử viết code lại dùng phương pháp vét cạn nhưng cho trường hợp tổng quát hơn ( chạy được nhiều người hơn) và so sánh kết quả thời gian so với code ở bài #33 thấy giống nhau, chắc là ok rồi. Chỉ là chưa test được một vài điều sau:

+Có nhất thiết phải sắp xếp dữ liệu không, hay chỉ cần tìm ra hai người nhanh nhất?
+Nếu trường hợp nhiều người có thời gian bằng nhau liệu đã tối ưu chưa?