Không chỉ đang nhanh hơn đâu, chúng sẽ luôn luôn nhanh hơn!
Ấy là vì có những bài toán tối ưu tổ hợp cần được giải quyết, những bài toán có ứng dụng thực tế quan trọng— cùng với nhu cầu sức mạnh tính toán vô tận để giải những bài toán đó với tốc độ nhanh nhất có thể (theo nghĩa chất lượng của giải pháp).
Dưới đây là một ví dụ thô thiển mà tôi đang nghiên cứu. Tại một cảng container, những chiếc container được chồng lên nóc nhau, như thế này: [ẢNH]
trong lúc chờ được vận chuyển. Đối với mỗi chiếc container, khi một xe tải đến nơi, cần cẩu sẽ nhấc nó lên khỏi sân và đặt lên xe tải rồi khởi hành.
Ô khoan, chờ chút đã… có thực thế không? Điều gì sẽ xảy ra nếu xe tải tới lấy container màu trắng được chỉ bằng mũi tên đỏ trong hình?
[Ảnh 2]
Có bốn container khác nằm trên nó đang chờ được chuyển đi cơ… vì thế trước khi đưa được nó lên xe tải, cần cẩu phải di chuyển những container trước đó ra chỗ nào đó chỉ để lôi được một chiếc ra — tốn một lượng thời gian rất lớn chẳng để làm gì: Chỉ cần chiếc màu trắng đó nằm trên cùng khi chiếc xe tải đến nơi thôi mà!
Trong thực tế, cần nhiều container được chuyển đi để có thể dọn chỗ cho những chiếc cần lấy, hơn là số container được chuyển lên — và những lần vận chuyển lãng phí này tốn tới hàng triệu đô về mặt hiệu quả.
Giờ thì, hóa ra việc đặt chỗ cho các container có thể được tối ưu (khi đã biết được thời gian đến và đi), từ đấy trong phần lớn thời gian, container sắp đi đều ở (gần) trên cùng cột đó.
Bạn có thể nghĩ rằng “Tuyệt cú mèo! Cứ viết một chương trình cho nó đi — ngày nay máy tính mạnh lắm, dễ như bê lễ ấy mà!”
Chậc, vấn đề là thế này này, những chiếc tàu chở container lớn chứa hàng ngàn container, vì thế khi một chiếc đến cảng, hàng ngàn chiếc container sẽ cần được hạ xuống bến. Mặt khác (như hình đầu tiên đã chỉ ra), thông thường sẽ có khoảng vài trăm cột trên bến — và với mỗi container trong số đó, cần chọn ra được cột tốt nhất.
Điều này tạo ra một bài toán tối ưu cực kỳ phức tạp. Để minh họa thì, tôi đang “chơi” dữ liệu một chút, 6000 container cần được xếp chỗ một cách tối ưu trong bến có 600 cột, từ đó giảm thiểu tối đa số lần di chuyển kém hiệu quả. Tức là về cơ bản, thuật toán của tôi cần chọn một trong 600 cột để đặt container đầu tiên, một trong 600 cột để đặt container thứ hai, và cứ như vậy, 6000 lần tất cả.
Từ đó, số lượng khả năng chọn ra cột tốt nhất có thể có (tức là kích thước của không gian tìm kiếm của bài toán) là 600^6000=10^16668, một con số có 16.668 chữ số.
Để mô tả cho bạn biết được đôi chút về độ lớn của con số đó, hãy nghĩ về số lượngtất cả các hạt cơ bản có trong cả Vũ trụ là một số có “khoảng” 100 chữ số hoặc tương tự thế (ước lượng tạm thời, không bao gồm vật chất đen (dark matter): WIKI ).
Vì thế, đó là… một bài toán khó giải— nói nhẹ một chút là vậy. Với những thuật toán cực kỳ thông minh việc này có thể được giải quyết (thực sự thì với chỗ dữ liệu này, tôi đang làm rất tốt đó), nhưng độ khó của nó là do bạn muốn có được lời giải có chất lượng tốt hơn (rất, rất ít những lần di chuyển container không hiệu quả) một cách nhanh chóng, để phản ứng trong thời gian thực với những thông tin mới liên tục được cảng cập nhật về container đến và đi.
Và đó là lúc tốc độ máy tính trở thành thứ cốt lõi: thật tuyệt vời nếu như bài toán có thể được giải một cách tối ưu chỉ trong vòng một giây! Tuy nhiên, từ độ hại não của vấn đề, người ta còn nghi ngờ rằng không biết liệu có giải quyết được hay không nữa.
Có được một chiếc máy tính nhanh hơn một triệu lần chiếc tiền nhiệm ư? May mắn nhỏ nhoi nè: bạn đã loại ra được sáu chữ số của con số 16668 ở trên rồi đó — bạn chỉ còn lại 16662 thôi nhé.
Và nếu như chuyện này khả thi thì sao? Chậc… thì sau đó họ sẽ yêu cầu bạn xếp chỗ không chỉ 6000 mà là 20000 container (đã có những con tàu mang theo từng ấy rồi đó!), và bạn sẽ có một con số 55561 chữ số! Về cơ bản thì, bạn lại bắt đầu từ đầu thôi.
Và đó là bản chất của tối ưu tổ hợp: bài toán đang — và sẽ luôn là như vậy — luôn luôn lớn hơn những gì mà máy tính có thể giải quyết theo thời gian đủ ngắn.
Update: Trời, 1.8k upvote… tôi choáng mất rồi, và rất vui nữa — xin cảm ơn vì sự trân trọng và chia sẻ của các bạn với câu trả lời mang tính kỹ thuật của tôi!
Nhưng ngoài việc kiếm được “Fame Quora” (tôi chẳng bao giờ cần làm vậy), tôi rất vui khi thấy rằng thành công này có được ít nhiều nhờ vào thông điệp chính của mình, tức là tối ưu tổ hợp là một việc thực sự khó nhằn đó — cũng như sự khác biệt của nó khi so sánh với việc “lập trình”, hệt như liệu pháp gen rất khác so với việc dán băng vào vết thương ấy: cả hai cái sau đều là “thuốc”… và hai cái trước đều là “lập trình” — quá nhiều luôn đó.
Hi vọng là, bài post này của tôi sẽ giúp bạn hiểu rõ sai lầm lớn về mặt nhận thức mà nhiều người vẫn nghĩ bấy lâu nay trong nghề nghiệp của tôi, tức là được sử dụng thông tin không đồng nghĩa với việc bạn có thể ngay lập tứctận dụng được chỗ thông tin đó. Vâng, bạn cần có dữ liệu… nhưng đó chỉ là một phần rất nhỏ, thậm chí là không đáng kể (và trong nhiều trường hợp, là tầm thường) trong việc thực sự giải quyết được vấn đề.
Vậy mà vẫn rất nhiều lần, mọi người (khách hàng đó) yêu cầu có được bất kỳ giao diện nào có thể mà còn không thèm hỏi xem liệu chúng tôi có thể thực sự giải quyết được vấn đề hay không — bởi lẽ đối với họ, có được thông tin (dữ liệu) đồng nghĩa với việc giải quyết được vấn đề! từ đó, họ phải đi “giải” bằng tay đó, dùng những giao diện cực kỳ đẹp mắt do những bên thầu rẻ nhất cung cấp… và chẳng có khả năng tối ưu thực sự nào— chỉ vì nhà cung cấp đó có được chứng nhận SAP hoặc thứ gì đó tương tự.
Chẳng cần phải nói, liệu họ có cơ hội giải bài toán với chất lượng ra sao khi làm bằng tay cơ chứ? Tuyệt đối là không nhé— nhưng họ vẫn tin rằng mình có thể xử lý bằng cách dùng bảng trắng (hoặc cái giao diện đẹp đẽ tương ứng), bởi lẽ họ không nhận ra rằng vấn đề này có thể bùng nổ tới mức độ khủng khiếp ra sao.
Tôi hi vọng rằng bài viết của tôi đã chỉ ra rằng câu nói “dùng được dữ liệu = giải quyết được bài toán” là mệnh đề sai hoàn toàn khi xem xét đến những bài toán thực sự khó khăn (như việc đặt container vừa rồi đó).
Cũng như ai đó chia sẻ câu trả lời này đã nói, “bài này sẽ làm bạn thay đổi quan điểm…”. Nếu thực vậy thì tôi xúc động lắm. Một lần nữa, xin cảm ơn!
