Tổng quan về thuật toán, thuật toán ứng dụng Robot

Đăng lúc: Thứ ba - 17/11/2015 09:24 - Người đăng bài viết: SuperG
Thuật toán ứng dụng Robot rất đa dạng

Thuật toán ứng dụng Robot rất đa dạng

Thuật toán là một thuật ngữ không mấy xa lạ đối với lập trình viên. Nhưng thật thiếu sót khi chúng ta làm việc với chúng hằng ngày lại quên đi những khái niệm cơ bản nhất về chúng. Trong bài viết này, tôi sẽ trình bày lại những nét chung về thuật toán để giúp các bạn hệ thống lại sau đó hướng tới xây dựng ứng dụng tự động và nghiên cứu chế tạo Robot.

Tiền đề bài viết

Bài viết nằm trong loạt bài giới thiệu tổng quan về lập trình C++.

Đối tượng hướng đến

Bài viết này dành cho những người muốn hiểu rõ hơn về định nghĩa và cách phân loại thuật toán để mở rộng kiến thức của mình.

Thuật toán là gì?

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. Tôi sẽ lấy ví dụ để làm sáng rõ định nghĩa này.

  1. 00000
  2. 0A000
  3. 0000B

Tôi có một con robot đứng tại vị trí A và quay về bên phải. Tôi được yêu cầu giúp đỡ con robot này đến được vị trí B. Con robot này có một số tính năng như sau:

  • move: dời 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, tôi đã cho robot thực hiện chuỗi hành động sau:

move → move → move → turnLeft → turnLeft → turnLeft → move

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

Tính chất của thuật toán

Tính chính xác

Đây là một tính chất cực kỳ quan trọng của một thuật toán. Lấy lại ví dụ tôi đã nêu ở trên, bạn thử 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 tôi sẽ ở những vị trí khác nhau sau mỗi lần chạy. Lúc này thuật toán của tôi nên đổi tên thành thuật toán để robot di chuyển từ A đến một vị trí bất kỳ thì đúng hơn.

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:

move → move → move → turn → turn → turn → move

Như các bạn thấy, hành động turn ở đây quá mơ hồ. Người đọc thuật toán sẽ thắc mắc ngay: 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.

Bây giờ tôi 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:

move → move → move  → move → turnLeft → turnLeft → turnLeft

Với chuỗi hành động này, có lẽ con robot sẽ bị hỏng vì phải va vào tường rồi! 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.

Tôi muốn kiểm tra xe con robot của tôi có chạy tốt trên các điều kiện khác nhau hay không nên tôi đã đặt robot của mình 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 giống hệt 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 mỹ mãn, nó hoàn toàn giống với tính toán trước của tôi. 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 tôi đã 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 tính trước. Dù cho thuật toán của tôi có hoàn hảo đến đâu tôi cũng không thể làm biết trước được môi trường sẽ  ảnh hưởng thế nào đến thuật toán của mình.

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 mình xem có nằm trong dạng chạy không cần nghỉ ngơi không. Nếu thuật toán của bạn thuộc dạng trên, STDIO có thuê thêm vào chục cái server cũng không thể giúp bạn chạy hoàn thành chương trình của bạn.

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

Rất khó để có thể phân loại chính xác mỗi thuật toán, tùy vào tiêu chí phân loại bạn 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ạn 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 nhanh 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 đề bạn gặp trong đời sống đều đã được giải quyết trước đó rồi, 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 bạn hiểu rõ hơn về các khái niệm và lý thuyết giúp các bạn hiểu đầy đủ hơn về chúng. Trong bài viết này, với cách viết đan xen giữa thực hành và lý thuyết, tôi hy vọng hữu ích​ cho các bạn khi tìm hiểu về thuật toán.

 

@Taco Nguyen


 



Nguồn tin: stdio.vn
Từ khóa:

n/a

Đánh giá bài viết
Tổng số điểm của bài viết là: 0 trong 0 đánh giá
Click để đánh giá bài viết
 

Giới thiệu sản phẩm dịch vụ

Giới thiệu sản phẩm dịch vụ: -          Cung cấp giải pháp, thiết kế các sản phẩm Robot gia dụng -          Cung cấp các sản phẩm điện thông minh, nhà thông minh -          Sửa chữa, phục hồi chức năng cho Robot -  ...

Thăm dò ý kiến

Bạn có muốn sở hữu một Robot trong nhà không?

Cần một Robot để dọn dẹp

Cần một Robot trông nhà

Cần một Robot để giải trí

Bạn cần một Robot theo cách khác

Bạn đã có rồi

Bạn không cần

Liên kết