Search…

Giải Thuật Là Gì?

31/08/20205 min read
Giải thuật - thuật toán là một tập hợp hữu hạn các thao tác được thực hiện liên tục nhằm đạt được một mục đích xác định trước.

Giải thuật hay thuật toán là gì?

1 robot đứng tại vị trí A và quay về bên phải, yêu cầu giúp đỡ robot này đến được vị trí B.

00000
0A000
0000B

Robot này có một số tính năng như sau:

  • move: tiến về phía trước 1 ô.
  • turnLeft: quay sang bên trái.
  • canMove: kiểm tra xem phía trước có vật cản hay không?

Để có thể di chuyển đến B, robot cần thực hiện chuỗi hành động sau:

movemovemoveturnLeftturnLeftturnLeftmove

Chuỗi hành động trên của robot được gọi là giải thuật để robot di chuyển từ A đến B.

Tính chất của giải thuật

Tính chính xác

Đây là tính chất cực kỳ quan trọng của một thuật toán, hình dung xem chuyện gì xảy ra nếu sau khi áp dụng thuật toán vào robot, robot của sẽ ở những vị trí khác nhau sau mỗi lần thực hiện thuật toán. Lúc này mục tiêu để robot phải thực hiện như vệ sinh nhà cửa, hoặc cắt tỉa cây sẽ không còn đúng nữa.

Tính rõ ràng

Mỗi hành động trong thuật toán phải minh bạch, rõ ràng và các hành động phải được sắp xếp theo một thứ tự nhất định. Ví dụ:

Để giải quyết bài toán trên, một lập trình viên đề xuất thuật toán như sau:

movemovemoveturnturnturn → move

Hành động turn ở đây mơ hồ, turn nghĩa là quay sang trái, quay sang phải hay quay mặt xuống đất? Điều này cho thấy sự quan trọng của việc mô tả minh bạch từng hành động trong thuật toán.

Sử dụng lại thuật toán ban đầu như thay đổi vị trí của một vài hành động:

movemovemove  → moveturnLeftturnLeftturnLeft

Với chuỗi hành động này, robot sẽ bị hỏng vì va vào tường. Giống như tính minh bạch của mỗi hành động, thứ tự sắp xếp các hành động cũng cần phải xem xét kỹ lưỡng.

Tính khách quan

Một thuật toán do nhiều người hiện thực khác nhau hoặc được thực thi trong những điều kiện khác nhau sẽ cho kết quả khác nhau.

Để kiểm tra robot có chạy tốt trên các điều kiện khác nhau hay không, đặt robot của trên một nền gạch và trong một lần khác trên nền cát. Kích thước của những ô cho robot di chuyển trên cả 2 địa hình này như nhau và giống với bản thiết kế. Kết quả thu được khi robot chạy trên nền gạch thật tốt, hoàn toàn giống với tính toán trước đó. Nhưng với nền cát, vì cát quá nhiều nên mỗi khi xoay trái 90 độ, robot của bị môi trường tác động xoay thêm 5 độ nữa. Điều đó làm cho robot di chuyển lệch so với vị trí B như mong muốn. Dù cho thuật toán của có hoàn hảo đến đâu cũng không thể biết trước được môi trường sẽ ảnh hưởng thế nào đến thuật toán.

Tính phổ dụng

Thuật toán không chỉ áp dụng cho một bài toán nhất định mà nó còn có thể áp dụng cho một số bài toán khác có đầu vào tương tự.

Tính kết thúc

Thuật toán phải gồm một số hữu hạn các hành động. Tính chất này giúp cho các lập trình viên xem xét thuật toán của có nằm trong dạng chạy không cần nghỉ ngơi không.

Nếu thuật toán thuộc dạng này, có thể chương trình sẽ không bao giờ kết thúc, vì rơi vào vòng lẩn quẩn hoặc tốn kém tài nguyên của máy tính.

Phân loại thuật toán

Rất khó để có thể phân loại chính xác thuật toán, tùy vào tiêu chí phân loại có thể phân thuật toán ra thành nhiều loại khác nhau.

Phân loại theo tính năng của thuật toán

  • Thuật toán tìm kiếm: tìm kiếm dữ liệu trong một tập các giá trị.
  • Thuật toán sắp xếp: sắp xếp một tập các giá trị theo một trật tự cho trước
  • Thuật toán đồ thị: xử lý những bài toán liên quan đến đồ thị như tìm đường đi ngắn nhất, tìm đường đi qua 1 điểm, ...

Phân loại theo cách thực hiện thuật toán

  • Thuật toán chia để trị: chia bài toán lớn ra thành những bài toán nhỏ và giải quyết từng bài toán nhỏ đó.
  • Thuật toán tham lam: thuật toán thay đổi trạng thái được thiết đặt để qua mỗi hành động, thuật toán sẽ đi lại gần hơn với bài toán cần giải quyết.

Vai trò của thuật toán

Đi kèm với cách tổ chức dữ liệu (cấu trúc dữ liệu), thuật toán là phần không thể thiếu khi bước chân vào lĩnh vực lập trình.

Thuật toán tốt giúp chương trình chạy tối ưu hơn, ít tốn tài nguyên hơn và giúp chương trình dễ hiểu hơn. Bên cạnh việc nghĩ ra các thuật toán mới thì sử dụng thành thạo các thuật toán có sẵn là điều rất quan trọng. Hầu hết những vấn đề gặp trong đời sống đều đã được giải quyết trước đó vì vậy đừng tự chế tạo lại cái bánh xe khi không phải bắt buộc.

Lời kết

Hầu hết các khái niệm trong lập trình nói riêng và công nghệ thông tin nói chung đều có 2 mặt: lý thuyết và thực hành. Thực hành giúp các hiểu rõ hơn về các khái niệm và lý thuyết giúp các hiểu đầy đủ hơn về chúng.

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024