Tại sao lại xảy ra sự bùng nổ tổ hợp thông tin?

Tất cả những cách đi có thể đều thử một lần, sau đó chọn ra phương án hay nhất là có thể làm được. Nhưng thời gian để làm như vậy và không gian lưu trữ thì thật là kinh khủng. Với năng lực của máy tính hiện nay mà giải bài toán khó này là không thể. Bởi vì máy tính nào thì bộ nhớ của nó cũng chỉ có dung lượng có hạn, không thể vô hạn được. Bất kì động tác nào của máy đều cần một thời gian nhất định để hoàn thành.

Để cho dễ hiểu, chúng ta hãy suy xét vấn đề “bùng nổ tổ hợp” theo giác độ tiêu phí thời gian cho máy tính đánh cờ.

Hiện nay tốc độ tính toán của máy tính có thể đạt tới 100 triệu lệnh mỗi ngày. Dùng chương trình được thiết kế hay nhất, đi một nước cờ thì phải chấp hành 10 lệnh. Như vậy, đi một nước thì mất 0,1 micrô giây.

Tốc độ máy tính có thể đạt tới ước chừng 2 miligiây/bước (1 ms = 10-3 s). Tốc độ tối đa về lí thuyết cho máy tính cổng tuần tự (serial máy tính) là 10-12 mili giây/bước, còn tốc độ giới hạn cho loại máy tính cổng song song (parallel máy tính) là 10-11 ms/bước, hoặc 10-104 năm/1 bước đi.

Dù cho tính toán với tốc độ lí thuyết tối đa trên máy tính cổng song song thì việc tìm nghiệm cho cờ vua phải mất 10 ngàn tỉ năm (1016) mới có thể hoàn thành. Thế nhưng, chúng ta biết rằng lịch sử Vũ Trụ cũng chỉ mới là 15 tỉ năm thôi.

Từ khóa: Bùng nổ tổ hợp thông tin; Bài toán người bán hàng; Tiêu phí thời gian.