TẠI SAO CÓ THỂ XẢY RA ''BÙNG NỔ TỔ HỢP'' TIN TỨC?
Không biết bạn đã nghe qua hay chưa, tin tức tăng nhanh sẽ gây ra “bùng nổ”. Điều này rốt cục là như thế nào? Sau khi xem xong ví dụ đơn giản dưới đây, bạn sẽ hiểu ra ngay.
Có một tấm bản đồ thành phố, nhân viên bán hàng phải đi hết từng thành phố và phải làm sao để chỉ đi qua một lần. Giữa hai thành phố trong bản đồ có một con đường, bên trên có đánh dấu khoảng cách giữa hai thành phố. Bây giờ yêu cầu thiết kế ra một con đường đi bộ cho nhân viên bán hàng để người này xuất phát từ bất kỳ một thành phố nào trong những thành phố này, sau đó trở về thành phố xuất phát, làm thế nào để đường đi là ngắn nhất. Đây chính là ''câu hỏi'' rất nổi tiếng.
Yêu cầu giải câu hỏi này dường như không khó, chỉ cần tìm ra các con đường có thể trong bản đồ rồi tiến hành so sánh và chọn ra con đường ngắn nhất là được. Nếu số lượng thành phố ít thì phương pháp này rất thiết thực và khả thi. Nhưng khi số lượng các thành phố nhiều lên thì phương pháp này cũng sẽ thất bại. Nếu số lượng thành phố là N thì các con đường khác nhau giữa các thành phố là N! (N! = 1.2.3. . .N) (đường). Nếu tổng thời gian để tính độ dài mỗi con đường là 0,1 micro giây (= 10-7 giây) thì tổng thời gian để tính độ dài tất cả các con đường là N!x10-7 giây. Trong thực tế, yêu cầu nhân viên bán hàng ''viếng thăm'' 24 thành phố cũng không phải là một chuyện kỳ lạ, nhưng 24! là quá lớn. Tổng thời gian để tính ra độ dài của tất cả các con đường giữa 24 thành phố là 24! X 0,l micro giây (tức là 6,204484017.1022 micro giây, khoảng 1,96 tỉ năm). Lúc này nếu N tăng thêm 1, tức 24+1=25 thì thời gian dùng hết tất cả là hơn 25 lần, tức là 25!x0,1 micro giây (khoảng 49,05 tỉ năm), N tăng thêm 1 tức là tổng thời gian dùng hết sẽ tăng (N+1) lần. Tốc độ tăng nhanh như vậy khiến mọi người không thể tưởng tượng ra nổi. Hiện tượng này thành là vấn đề được gọi là ''bùng nổ tổ hợp''.
Còn có một loại câu hỏi gọi là câu hỏi Boyi. Nếu người và máy đánh cờ, để bảo đảm thắng lợi cuối cùng, máy vi tính có thể thử một lúc tất cả các bước đi có thể, sau đó chọn ra bước đi giành thắng lợi. Mỗi lần thử một bước đi sẽ có một dạng thế cờ mà số lượng các thế cờ là vô cùng lớn. Ví dụ số lượng các thế cờ khác nhau trong cờ tướng quốc tế là 10120 thế, cờ vây là 10761 thế.
Tìm ra tất cả các bước đi có thể và thử một lúc, sau đó chọn ra ''phương án tốt nhất'' là điều có thể làm được nhưng thời gian tiêu tốn và không gian lưu trữ nếu làm như vậy là vô cùng đáng sợ. Dùng khả năng của máy tính thể hiện nay để giải ''cái khó'' trên là điều không thể, bởi vì dung lượng của bất kỳ máy lưu trữ nào trong máy tính đều có hạn cả, không thể có dung lượng lớn vô hạn như vậy được. Mỗi động tác của bất kỳ một máy tính nào đều cần phải hoàn thành trong một thời gian nhất định.
Để tiện cho việc lý giải, chúng ta hãy xem xét câu hỏi ''bùng nổ tổ hợp'' từ thời gian hao phí của việc đánh cờ trên máy vi tính.
Ngày nay tốc độ tính toán của máy vi tính có thể đạt tới 100 triệu lệnh/giây. Dùng phương pháp tốt nhất để lập trình, mỗi bước đi cần chấp hành 10 lệnh, như vậy thời gian mỗi bước đi cần là 0,1 micro giây. Tốc độ thực tế có thể đạt được của máy vi tính là khoảng 2.10-3 giây/bước. Giới hạn tốc độ theo lý luận máy vi tính là 2.10-5 giây/bước, còn giới hạn tốc độ theo lý luận đồng hành của máy vi tính là 2.10-14 giây/bước hoặc 10-l04 năm/bước.
Mặc dù tính toán tốc độ theo giới hạn lý luận đồng hành của máy tính thì để tính các bước đi trong cờ tướng quốc tế cũng phải mất 1016 năm mới xong. Trong khi đó lịch sử vũ trụ mà chúng ta đã biết mới chỉ được 15 tỷ năm.
