Tầm quan trọng của giải thuật trong việc xử lý các bài toán

Để hiểu được tại sao kiến thức về giải thuật và việc hiểu biết về giải thuật lại quan trọng chúng ta cần định nghĩa chính xác xem giải thuật là gì? Một định nghĩa về giải thuật được viết trong cuốn ” Introduction to Algorithms ” khá phổ biến như sau: Một giải thuật là thủ tục hay trình tự thực hiện các công việc của máy tính được định nghĩa rõ ràng, trong đó nó nhận vào giá trị hoặc một tập giá trị (gọi là input) và sinh ra giá trị hoặc một tập giá trị (gọi là output). Nói cách khác giải thuật như là tấm bản đồ, chỉ dẫn để hoàn thành công việc.Ví dụ một đoạn code tính toán các giá trị của dãy số fibonaci là một cài đặt cho một giải thuật cụ thể, mặc dù giải thuật đó đơn giản chỉ là cộng 2 số liền nhau . Một số giải thuật như ví dụ trên tính toán số tiếp theo của dãy fibonaci, có thể dễ dàng nhận biết và thậm chí được cài đặt một cách bẩm sinh trong hệ thống tư duy logic và khả năng giải quyết vấn đề của chúng ta.Tuy nhiên với hầu hết chúng ta những giải thuật phức tạp chính là những “best studied” để từ đó chúng ta có thể sử dụng một phần của chúng để xây dựng những giải thuật tốt cho những vấn đề khác trong tương lai.Trên thực tế con người sử dụng những giải thuật rất phức tạp để làm những việc đơn giản như check email, nghe nhạc … Bài viết này giới thiệu một số ý tưởng cơ bản nhất về phân tích giải thuật và áp dụng chúng vào những ví dụ minh họa để làm rõ hơn tầm quan trọng của giải thuật.

Runtime Analysis

Một trong những vấn đề qua trọng nhất của giải thuật đó là: giải thuật nhanh tới mức nào? Thông thường các giải thuật không tốn nhiều thời gian để xử lý một vấn đề nào đó, tuy nhiên trong trường hợp giải thuật quá chậm thì chúng ta cần xem xét lại giải thuật đó. Tốc độ chính xác của giải thuật phụ thuộc vào việc nó chạy trên nền tảng nào cũng như việc giải thuật đó được cài đặt tốt tới mức nào, một yếu tố nữa thường được các nhà khoa học máy tính nhắc đến là độ lớn của input. Ví dụ một bài toán có độ lớn input là n số tự nhiên, một giải thuật có runtime tỷ lệ thuận với N2 (được gọi là O(N2)) thì khi chạy cài đặt của giải thuật này trên máy tính với độ lớn của input là N thì máy tính sẽ mất C*N2 giây để đưa ra được kết quả. Với C là một hằng số không phụ thuộc vào N. Tuy nhiên độ nhanh của thuật toán không chỉ phụ thuộc vào size của input mà còn phụ thuộc nhiều yếu tố khác, ví dụ một giải thuật sắp xếp sẽ chạy nhanh hơn nếu đầu vào của nó đã được sắp xếp một phần theo thứ tự hơn khi chạy giải thuật đó với đầu vào với thứ tự ngẫu nhiên. Yếu tố này tạo ra “worst-case runtime”, “average-case runtime” mà chúng ta thường nghe. worst-case runtime: là thời gian chạy của giải thuật trong trường hợp giải thuật tốn nhiều thời gian nhất với bộ input đầu vào. average-case runtime: là thời gian chạy trung bình của giải thuật đối với tất cả các bộ input. Thông thường việc tính toán worst-case runtime dễ dàng hơn là average-case runtime nên nó thường được dùng như một tiêu chí phổ biến trong việc đánh giá giải thuật. Rất khó để chạy giải thuật cho tất cả các trường hợp input, do đó người ta thường dùng một số mẹo để tính một cách gần chính xác average-case runtime cho các giải thuật. Dưới đây là một số nguồn tham khảo về average-case runtime:

Sorting

Các giải thuật sắp xếp là những ví dụ điển hình về thuật toán và thường được sử dụng. Cách đơn giản nhất để sắp xếp các phần tử trong một nhóm là lấy phần tử nhỏ nhất khỏi nhóm và đưa lên đầu tiên, tuy nhiên độ phức tạp của giải thuật này là O(N^2) có nghĩa là thời gian chạy của giải thuật sẽ tỷ lệ thuận với bình phương của độ lớn input. Nếu như thực hiện sắp xếp 1tỷ phần tử thì cần thực hiện 10^18 phép tính. Một pc thông thường có thể chạy khoảng 10^9 phép tính mỗi giây và nếu thực hiện sắp xếp theo cách ở trên thì phải mất đến hàng năm mới thực hiện xong. Thật may là có những giải thuật khác tốt hơn (quicksort, heapsort, mergesort..) những giải thuật này đã được phát hiện ra từ nhiều năm trước, phần lớn giải thuật trong số này có độ phức tạp O(N * Log(N)). Điều này sẽ giảm thiểu một lượng lớn các phép tính cần thực hiện và giúp thời gian xử lý bài toán nhanh hơn nhiều dù chạy trên máy tính cùi bắp hơn. Thay vì thực hiện 10^18 phép tính, giải thuật này chỉ thực hiện 10^10 phép tính, có nghĩa là nhanh hơn 100 triệu lần.

Shortest Path

Bài toán tìm đường đi ngắn nhất đã được nghiên cứu trong nhiều năm và có nhiều ứng dụng. Tuy nhiên hãy cứ nghĩ đơn giản là bạn muốn tìm đường đi từ điểm A đến điểm B thông qua vài con đường và các ngã tư. Có khá nhiều giải thuật xử lý bài toán này với những ưu điểm cũng như đánh đổi khác nhau để có được ưu điểm đó. Trước khi tìm hiểu sâu về cách giải quyết thì chúng ta hãy thử tính xem một giải thuật thông thường sẽ mất bao lâu nếu nó tính toán tất cả các khả năng đường đi. Nếu giải thuật cân tính toán hết các khả năng đi từ A đến B (không tính đi vòng tròn) thì sẽ mất nhiều thời gian hơn cả đời người, kể cả là A và B chỉ ở trong một thành phố nhỏ. Độ phức tạp của giải thuật thông thường cho bài toán này là hàm mũ của input O(CN) với C là một hằng số. Và kể cả trong trường hợp C nhỏ thì CN cũng trở nên vô cùng lớn khi số điểm N tăng lên. Một trong những giải thuật nhanh nhất xử lý bài toán này có độ phức tạp O(EVLog(V)), với E là số đường đi giữa các điểm và V là các điểm giao nhau. Với độ phức tạp này thì giải thuật sẽ xử lý bài toán trong 2s đối với 10000 điểm giao nhau và 20000 đường đi. Giải thuật Djikstra’s khá phức tạp và yêu cầu cài đặt cấu trúc dữ liệu như là hàng chờ ưu tiên.Trong một số trường hợp giải thuật này vẫn còn rất chậm (ví dụ trong trường hợp tính toán đường đi ngắn nhất giữa New York đến San Francisco – với hàng triệu điểm giao nhau), vì thế các programer tìm những cách khác nhau để cải tiến gọi là heuristics (mẹo). Heuristic là cách tính xấp xỉ giá trị nào đó liên quan đến bài toán và thường được sử dụng để tính toán trong giải thuật.Ví dụ trong bài toán đường đi ngắn nhất thì giá trị quãng đường từ điểm hiện tại đến đích việc ước tính được giá trị này sẽ cải thiệnt giải thuật một cách đáng kể (như giải thuật A* khi áp dụng mẹo này sẽ chạy nhanh đáng kể so với Djikstra’s). Áp dụng heuristics trong hầu hết trường hợp không cải thiện được worst-case runtime nhưng cải thiện đáng kể average-case runtime.

Approximate algorithms

Trong một vài trường hợp kể cả khi đã áp dụng những giải thuật tốt nhất, kèm theo sử dụng những heuristics trên những máy tính nhanh nhất nhưng runtime vẫn quá chậm. Trong những trường hợp này để xử lý được vấn đề buộc phải đánh đổi độ chính xác của kết quả ở một mức độ nào đó.Ví dụ như tìm đường ngắn nhất thì giải thuật chỉ cần tìm ra đường đi thuộc top 10% ngắn nhất.

Trên thực tế, có nhiều vấn đề quan trọng mà kể cả những giải thuật tốt nhất ở thời điểm hiện tại cũng không thể đưa ra được câu trả lời tối ưu một cách đủ nhanh. Những nhóm vấn đề này được gọi là NP-problems, ví dụ như non-deterministic polynomial. Nếu một bài toán được gọi là NP-complete hoặc NP-hard, có nghĩa là chưa ai tìm ra được cách tối ưu để giải quyết nó. Nếu ai đó tìm ra giải thuật hiệu quả để giải quyết 1 NP-complete problem, thì giải thuật đó có thể được áp dụng cho tất cả NP-complete problems.

Một ví dụ điển hình về NP-hard problem là (famous traveling salesman problem)[https://simple.wikipedia.org/wiki/Travelling_salesman_problem]: một người bán hàng cần đi qua n thành phố và anh ta biết phải mát bao lâu để đi từ thành phố này đến thành phố khác, câu hỏi là mất bao lâu để anh ta đi hết tất cả thành phố. Khi ngay cả cách giải thuật nhanh nhất cũng tốn quá nhiều thời gian, các programer tìm kiếm những giải thuật đưa ra kết quả tốt nhưng không phải tối ưu.

Random Algorithms

Một cách tiếp cận khác để giải quyết các vấn đề là bằng cách nào đó sử dụng ngẫu nhiên trong giải thuật.Việc này không cải thiện được thời gian chạy của giải thuật trong trường hợp tệ nhất của input (worst case) nhưng thường cải thiện trong average-case. Quicksort là một ví dụ về sử dụng ngẫu nhiên để cải thiện thuật toán. Trong trường hợp tệ nhất , runtime của quicksort là O(N^2), với N là số lượng phần tử cần sort. Nếu sử dụng ngẫu nhiên trong giải thuật trường hợp tệ nhất vẫn có thể xảy ra nhưng với xác suất rất nhỏ, tính trung bình thì quicksort có runtime O(NLog(N)). Có một số giải thuật khác đảm bảo được thời gian chạy O(NLog(N)), ngay cả trong trường hợp tệ nhất nhưng nó sẽ chậm ở ở average case. Mặc dù giải thuật có runtime tỷ lệ với NLog(N), tuy nhiên quicksort cũng có những yếu tố cố định – cần tối thiểu CNLog(N) phép tính trong khi những giải thuật khác cần nhiều hơn 2CNLog(N) phép tính.

Một số giảii thuật khác sử dụng ngẫu nhiên để tìm ra phần tử chính giữa với runtime O(N). Điều này thực sự có ý nghĩa trong việc áp dụng để sắp xếp tìm phần tử chính giữa có runtime O(N*Log(N)). Thuật toán tất định (không sử dụng ngẫu nhiên) tìm ra phần tử ở giữa với runtime O(N), trong khi giải thuật ngẫu nhiên rất đơn gian và lại còn nhanh hơn trong hầu hết các trường hợp.

Ý tưởng chính của giải thuật tìm phần tử chính giữa trong group là lấy một phần tử bất kỳ và đếm xem có bao nhiêu phần từ nhỏ hơn nó. Gỉa sử có N phần tử và có K phần tử nhỏ hơn phần tử ngẫu nhiên được chọn. Nếu K < N/2 thì phần tử chính giữa đứng thứ (N/2-K) trong số những phần tử lớn hơn phần tử ngẫu nhiên đã chọn, loại bỏ K phần tử <= phần tử ngẫu nhiên đã chọn và tiếp tực bài toán tìm kiếm phần tử thứ (N/2-K) trong các phần tử còn lại. Giải thuật được thực hiện lặp lại, chọn 1 phần tử ngẫu nhiên và thực hiện các bước như trên.

Compression

Một dạng khác của giải thuật là các bài toán nén dữ liệu. Những bài toán này không có output cụ thể (như bài toán sắp xếp), nhưng nó sẽ tối ưu hóa theo những tiêu chuẩn. Trong bài toán nén dữ liệu các thuật toán (ví dụ: LZW) tìm cách giảm thiểu số lượng byte lưu trữ dữ liệu một cách tối đa và sau đó trả lại dữ liệu gốc. Trong một vài trường hợp các giải thuật này cũng sử dụng kỹ thuật như các giải thuật cho bài toán thông thường là đưa ra kết quả đủ tốt thay vì tối ưu. Giải thuật nén JPG và MP3 compression là một ví dụ, sau khi nén và giải nén thì kết quả cuối cùng có chất lượng thấp hơn file ban đầu nhưng dung lượng lại nhỏ hơn.

The Importance of Knowing Algorithms

Với các nhà khoa học máy tính việc hiểu và áp dụng các giải thuật một cách chính xác là rất cần thiết. Nếu như bạn đang làm việc để tạo ra những phần quan trọng của phần mềm bạn cần phải ước lượng được mức độ nhanh của giải thuật. Việc ước lượng thời gian chạy sẽ không thể chính xác nếu như bạn không hiểu được cách phân tích runtime. Hơn thế, bạn cần hiểu rõ về giải thuật liên quan đến bài toán để dự đoán được những trường hợp đặc biệt mà phần mềm sẽ chạy chậm hoặc sinh ra những kết quả không như mong đợi.

Trong hầu hết các trường hợp bạn sẽ phải xử lý các vấn đề chưa từng gặp trước đó. Vì thế bạn cần phải viết một giải thuật mới hoặc áp dụng một giải thuật đã biết theo một cách khác. Càng có kiến thức về giải thuật thì bạn càng có nhiều khả năng tìm ra được cách tốt hơn để xử lý bài toán. Phần lớn các bài toán sẽ được giải quyết bằng cách áp dụng những bài toán trước đó và không tốn quá nhiều công sức, tuy nhiên sự hiểu biết cơ bản về giải thuật của những bài toán trước đó là điều kiện tiên quyết để bạn có thể làm được việc này. Một ví dụ hay về vấn đề này là switch làm việc với các gói tin trên internet. Một switch nối với N cables, và nhận các gói tin đến từ cables. Switch cần phần phân tích gói tin sau đó gửi chúng đến đúng địa chỉ thông qua các cables. Switch gửi các gói tin một cách riêng biệt qua từng khoảng thời gian (intervals).Ở những switch càng nhanh thì sẽ gửi càng nhiều gói tin/ 1 intervals mà không để chúng bị dồn lại hoặc bị xóa mất. Mục tiêu của giải thuật là gửi càng nhiều gói tin trong thời gian ngắn và gói tin đến trước sẽ được gửi đi trước. Vấn đề này liên quan đến bài toán “stable matching” và có thể áp dụng cho nhiều bài toán thực tế. Bằng việc thông qua các thuật toán đã có từ trước chúng ta có thể tìm ra những mối liên quan để giải quyết những vấn đề khác.

Maximum Flow

Bài toán maximum-flow (bài toán luồng cực đại) nhằm tìm ra cách tốt nhất để vận chuyển lượng hàng hóa từ một địa điểm đến địa điểm khác thông qua một mạng lưới. Cụ thể , bài toán này xuất hiện lần đầu tiên vào khoảng những năm 1950 liên quan tới mạng lưới ray tàu của liên bang Soviet. Phía Mỹ muốn biết Soviet có thể vận chuyển hàng hóa tới miền đông châu âu nhanh tới mức độ nào thông qua mạng lưới đường ray hiện tại. Từ đó phía Mỹ sẽ phá hủy những tuyến đường quan trọng và dễ phá hủy nhất để làm ngưng trệ sự vận chuyển này. Vấn đề này liên quan tới 2 bài toán max -low và min-cut.

Kết luận

Càng nhiều vấn đề được giải quyết thì càng có nhiều giải thuật. Thông qua việc hiểu biết về các giải thuật bạn sẽ có khả năng lựa chọn được giải thuật hợp lý cho vấn đề cần giải quyết và áp dụng nó một cách chính xác.

Techtalk via Viblo