Độ phức tạp của bài toàn 8 Hậu

[10520559]

Em với thằng bạn cãi nhau bài toán 8 Hậu : đặt 8 con hậu lên bàn cờ vua sao cho chúng không ăn nhau.
Phương pháp, Quay lui như sau :
B1:đặt con hậu thứ i lên hàng thứ i , cột thứ j của bàn cờ, xong rồi đánh dấu là cột j không được đặt con hậu nào lên nữa.
B2: tiếp tục đặt con hậu thứ i 1 lên hàng i 1, với điều kiện là đặt vô một cột nào mà chưa có con hậu trước đó.
Độ phức tạp : lí luận 1 : bài này giống bài mã đi tuần, mỗi lần là phải tìm cách đặt lên 8 cột của 1 hàng nào đó : O(8^n) ( n= 8 con hậu ).
lí luận 2 : mỗi lần đặt 1 con hậu là mất đi 1 cột trên bàn cờ vậy lần 1 đặt con hậu : chọn vị trí trên 8 cột, lần 2 : chọn trên 7 cột ... lần thứ 8 : còn 1 cột.
vậy T(n)=(8-i)*T(n-i) C; với T(0)=1; i chạy từ 0 tới 8; độ phức tạp O(n!).

Cái nào đúng vậy mọi người ?

[truonganpn]

Em với thằng bạn cãi nhau bài toán 8 Hậu : đặt 8 con hậu lên bàn cờ vua sao cho chúng không ăn nhau.
Phương pháp, Quay lui như sau :
B1:đặt con hậu thứ i lên hàng thứ i , cột thứ j của bàn cờ, xong rồi đánh dấu là cột j không được đặt con hậu nào lên nữa.
B2: tiếp tục đặt con hậu thứ i + 1 lên hàng i + 1, với điều kiện là đặt vô một cột nào mà chưa có con hậu trước đó

Thế lỡ con hậu thứ i (Hi) và con hậu thứ i+1 (Hi+1) được đặt thế này thì sao em, nó đớp nhau mất tiêu rồi.

                     +       +       +        +        +
                     |       |       |        |        |
                     |       |       |        |        |
            +--------|-------|-------|--------|--------|----------->
                     |       |       |  Hi+1  |        |
              i+1    |       |       |        |        |
            +--------|-------|-------|--------|--------|----------->
                     |       | Hi    |        |        |
              i      |       |       |        |        |
            +--------|-------|-------|--------|--------|----------->
                     |       |       |        |        |
              i-1    |       |       |        |        |
            +--------|-------|-------|--------|--------|----------->
                     |       |       |        |        |
                     |   j-1 |   j   |  j+1   |  j+2   |
                     |       |       |        |        |
                     |       |       |        |        |
                     v       v       v        v        v

Em cần phân biệt độ phức tạp của bài toán với độ phức tạp của một thuật toán cụ thể cho bài toán đó. Nếu xét độ phức tạp của cả bài toán thì số các trường hợp cần phải xét là tổ hợp chập 8 của n^2 vì trong bàn cờ n^2 ô ta cần chọn ra 8 ô để đặt hậu. Nhưng nếu chỉ cần tìm được 1 cách đặt hậu thoả mãn thì không hẳn phải vét toàn bộ trường hợp mà với từng thuật toán ta sẽ có độ phức tạp khác nhau.

Mà thuật toán của em sai mất tiêu rồi thì chắc khỏi phải bàn nữa

[09520019]

Em với thằng bạn cãi nhau bài toán 8 Hậu : đặt 8 con hậu lên bàn cờ vua sao cho chúng không ăn nhau.
Phương pháp, Quay lui như sau :
B1:đặt con hậu thứ i lên hàng thứ i , cột thứ j của bàn cờ, xong rồi đánh dấu là cột j không được đặt con hậu nào lên nữa.
B2: tiếp tục đặt con hậu thứ i + 1 lên hàng i + 1, với điều kiện là đặt vô một cột nào mà chưa có con hậu trước đó
Độ phức tạp : lí luận 1 : bài này giống bài mã đi tuần, mỗi lần là phải tìm cách đặt lên 8 cột của 1 hàng nào đó : O(8^n) ( n= 8 con hậu ).
lí luận 2 : mỗi lần đặt 1 con hậu là mất đi 1 cột trên bàn cờ vậy lần 1 đặt con hậu : chọn vị trí trên 8 cột, lần 2 : chọn trên 7 cột ... lần thứ 8 : còn 1 cột.
vậy T(n)=(8-i)*T(n-i)+C; với T(0)=1; i chạy từ 0 tới 8; độ phức tạp O(n!).

Cái nào đúng vậy mọi người ?

8! và 8^8 cùng thuộc tập hợp bài toán NP (tức là bài toán có thời gian tăng theo hàm mũ so với kích thước dữ liệu) cho nên
Cả 2 lý luận trên đều đúng đó em. Khác biệt do 2 thuật toán (2 lý luận) khác nhau dẫn tới 2 độ phức tạp khác nhau.
Bạn nào code được O(n!) thì đã code tối ưu nhất có thể rồi.
Bài này còn 1 cách dễ code hơn (và ngắn gọn súc tích hơn), và chỉ cần lưu 1 array 1x8 thôi . Cách này O(n!).

Thế lỡ con hậu thứ i (Hi) và con hậu thứ i+1 (Hi+1) được đặt thế này thì sao em, nó đớp nhau mất tiêu rồi.
[code]

Bạn đó chỉ nói Hậu[i+1] vào hàng i+1, chứ không nói đặt vào cột j+1.

[sinhvien.uit]

8! và 8^8 cùng thuộc tập hợp bài toán NP (tức là bài toán có thời gian tăng theo hàm mũ so với kích thước dữ liệu) cho nên
Cả 2 lý luận trên đều đúng đó em. Khác biệt do 2 thuật toán (2 lý luận) khác nhau dẫn tới 2 độ phức tạp khác nhau.
Bạn nào code được O(n!) thì đã code tối ưu nhất có thể rồi.
Bài này còn 1 cách dễ code hơn (và ngắn gọn súc tích hơn), và chỉ cần lưu 1 array 1x8 thôi . Cách này O(n!).
Bạn đó chỉ nói Hậu[i+1] vào hàng i+1, chứ không nói đặt vào cột j+1.

NP không có nghĩa là hàm mũ. Và khi yêu cầu sự chính xác thì 8^n không thể xem như n!. Điều kiện ràng buộc mà bạn 10520559 đưa ra trong thuật toán ban đầu không loại trừ trường hợp đặt vào cột j+1 nên phương pháp đưa ra mới là sai.

[09520019]

NP không có nghĩa là hàm mũ. Và khi yêu cầu sự chính xác thì 8^n không thể xem như n!.

Anh nên xem lại: Em nói rằng n! và n^n cùng thuộc lớp NP, chứ em chưa bao giờ nói n^n là NP và NP là n^n.
Thứ hai, anh yêu cầu sự chính xác, vậy thì em cũng nói luôn cho anh là hàm O cũng chỉ là hàm tính ước lượng chứ không phải hàm tính chính xác.
Thứ ba, em chẳng bao giờ nói rằng n! và n^n giống nhau cả. Em nói rằng do 2 cách cài đặt khác nhau dẫn tới 2 kết quả khác nhau về độ phức tạp. Nhưng lúc trước em đọc không kỹ nên kết luận sai. Em sẽ post sau.

NP không có nghĩa là hàm mũ. Và khi yêu cầu sự chính xác thì 8^n không thể xem như n!. Điều kiện ràng buộc mà bạn 10520559 đưa ra trong thuật toán ban đầu không loại trừ trường hợp đặt vào cột j+1 nên phương pháp đưa ra mới là sai.

Em với thằng bạn cãi nhau bài toán 8 Hậu : đặt 8 con hậu lên bàn cờ vua sao cho chúng không ăn nhau.
Phương pháp, Quay lui như sau :
B1:đặt con hậu thứ i lên hàng thứ i , cột thứ j của bàn cờ, xong rồi đánh dấu là cột j không được đặt con hậu nào lên nữa.
B2: tiếp tục đặt con hậu thứ i + 1 lên hàng i + 1, với điều kiện là đặt vô một cột nào mà chưa có con hậu trước đó
Độ phức tạp : lí luận 1 : bài này giống bài mã đi tuần, mỗi lần là phải tìm cách đặt lên 8 cột của 1 hàng nào đó : O(8^n) ( n= 8 con hậu ).
lí luận 2 : mỗi lần đặt 1 con hậu là mất đi 1 cột trên bàn cờ vậy lần 1 đặt con hậu : chọn vị trí trên 8 cột, lần 2 : chọn trên 7 cột ... lần thứ 8 : còn 1 cột.
vậy T(n)=(8-i)*T(n-i)+C; với T(0)=1; i chạy từ 0 tới 8; độ phức tạp O(n!).

Cái nào đúng vậy mọi người ?

Anh nhìn vào đoạn em bôi đỏ. Đoạn đó ý bạn đó là: đặt hậu i+1 vào cột j sao cho không có hậu nào trước đó có thể ăn nó được, nếu anh không đòi hỏi tính chính xác cao thì em nghĩ là nên hiểu đoạn đó như vậy. Nếu không thì thay mặt bạn đó em xin được phép sửa lại chính tả và ngữ pháp cho chính xác

Đoạn bôi xanh là đoạn trả lời cho câu hỏi của bạn kia: Lý luận 2 đúng, 1 sai. Cách giải đưa ra chạy với O(n!) (Khi code, nếu flag[j] == false thì skip ngay)

[sinhvien.uit]

Anh nên xem lại: Em nói rằng n! và n^n cùng thuộc lớp NP, chứ em chưa bao giờ nói n^n là NP và NP là n^n.

Ghi NP xong mở ngoặc ra bảo là thời gian tăng theo hàm mũ thì không phải bảo NP là hàm mũ chứ còn ý nghĩa gì nữa. Big O là một ký pháp (notation) có ý nghĩa toán học riêng của nó, không phải là hàm ước lượng cũng không phải là hàm tính chính xác. Khi yêu cầu sự chính xác thì có nghĩa là việc ghi Big O phải ghi càng chính xác càng tốt, vậy thôi.

Nếu đọc chưa kỹ post chưa chính xác thì edit lại luôn đi, khỏi phải post sau thêm mấy bài nữa cho rườm rà.

[09520019]

Ghi NP xong mở ngoặc ra bảo là thời gian tăng theo hàm mũ thì không phải bảo NP là hàm mũ chứ còn ý nghĩa gì nữa. Big O là một ký pháp (notation) có ý nghĩa toán học riêng của nó, không phải là hàm ước lượng cũng không phải là hàm tính chính xác. Khi yêu cầu sự chính xác thì có nghĩa là việc ghi Big O phải ghi càng chính xác càng tốt, vậy thôi.

Nếu đọc chưa kỹ post chưa chính xác thì edit lại luôn đi, khỏi phải post sau thêm mấy bài nữa cho rườm rà.

Em vừa edit lại (đây là lần thứ 3, thậm chí con trước khi anh post cái đó nữa), chả hiểu tại sao cứ mỗi lần em post hay edit là forum bị ..... database error @_@. Còn việc có lưu post hay không là hên xui...

BTW, ý em không phải là hàm mũ, mà nó có tốc độ tăng rất nhanh tương tự với hàm mũ. Em chỉ chia có 3 loại cho dễ nhớ: log, đa thức, mũ. Nếu muốn chính xác thì có mấy chục loại lận. O(n!) là thời gian tăng theo hàm lũy thừa.

[10520559]

Em xin cảm ơn mọi người đã giải thích cho em hiểu, em xin lỗi vì em ghi ko rõ ý mong mọi người thông cảm :

B1:đặt con hậu thứ i lên hàng thứ i , cột thứ j của bàn cờ, xong rồi đánh dấu là cột j không được đặt con hậu nào lên nữa.
B2: tiếp tục đặt con hậu thứ i 1 lên hàng i 1, với điều kiện là đặt vô một cột nào mà chưa có con hậu trước đó có thể ăn nó

mã giả của em :
Try(i)
{
For ( j = 1 ; j

[truonganpn]

Em xin cảm ơn mọi người đã giải thích cho em hiểu, em xin lỗi vì em ghi ko rõ ý mong mọi người thông cảm :

B1:đặt con hậu thứ i lên hàng thứ i , cột thứ j của bàn cờ, xong rồi đánh dấu là cột j không được đặt con hậu nào lên nữa.
B2: tiếp tục đặt con hậu thứ i + 1 lên hàng i + 1, với điều kiện là đặt vô một cột nào mà chưa có con hậu trước đó có thể ăn nó

Em nên xem lại các yêu cầu đặt ra cho giải thuật của mình. Nếu em tìm tất cả các lời giải cho bài toán lại theo hướng tiếp cận "đặt con hậu lên sao cho không con nào trước đó ăn được nó" thì em sẽ phải xét tất cả trường hợp của bài toán là tổ hợp chập 8 của n^2, cái này lớn hơn n! rất nhiều.

Nếu em chỉ tìm một lời giải đúng thì xem lại cách làm của mình, trình bày cho rõ ràng ra và tiến hành phân tích độ phức tạp của nó cho thật cẩn thận.

Việc em tính độ phức tạp ra 2 kết quả khác nhau là vì em tính bằng 2 cách mà cả 2 đều sai, nên nó ra 2 kết quả sai.
Đặt một con hậu lên bàn cờ nó kiểm soát tối thiểu là n ô đường chéo chứ làm gì có chuyện chỉ 1 ô. Còn phương trình đệ quy em thiết lập ra C1 với C2 là những gì, lập phương trình cụ thể chứ bê nguyên phương trình tổng quát trong sách vào đây làm gì.

Nếu em muốn trình bày chính xác thì không thể ghi kiểu ... ... ... như thế. Chính thuật toán của em đưa ra mà em còn lười phân tích thì đâu ai muốn phân tích cho em.

Và cuối cùng em nên xem lại định nghĩa của Big O notation, em đang nhầm giữa O và ~

[09520019]

Em nghĩ nó là O(n!) như anh Châu nói nhưng mà còn 1 thắc mắc : Khi đặt con hậu thứ 2 lên thì con hậu thứ 1 đã chiếm 1 cột và 1 ô đường chéo
vậy thì con hậu 2 chỉ có 6 vị trí, con hậu 3 và 4 có 4 vị trí => 8x6x4x4... => ko phù hợp với O(n!)

còn cái này nữa : Phương trình đệ quy : T(n)=nT(n-1)+C1; T(1)=C2;
vậy suy rộng ra : T(n)=nT(n-1)+C2= n(n-1)T(n-2) + nC2 +C2 = n(n-1)(n-2)T(n-3) + nC2 + n(n-1)C2 + C2

=n!(T(1)) + nC2 + n(n-1)C2 + ...
cái phần phía sau ( tổng hợp kết quả ) hình như còn phức tạp hơn n!

1 cột 1 ô đường chéo, nhưng không có nghĩa là con hậu tiếp theo sẽ mất 2 cột (có thể 1, có thể 2, có thể 0). Nhờ tối ưu nên nó bé hơn hàm giai thừa một chút thôi em. Cứ O(n!) cho nó đơn giản.

Cứ như a code một hàm 1 vòng for duy nhất từ 1 -> n, nhưng skip 1 vài trường hợp đặc biệt, thì nó vẫn là O(n). Chừng nào em skip được căn 2, thì nó trở thành O(n^1/2).

Ví dụ khác là anh for i = 1 -> n/2 thì vẫn là O(n).


BTW năm nay em năm 3 rồi mà sao còn hỏi mấy cái này ?

[10520559]

thiệt là em không biết nên mới hỏi anh ơi ! Em học môn phân tích thiết kế thuật toán mà có mấy cái còn chưa vững lắm, cám ơn hai anh An với anh Châu nhiều !