STDIO
Tìm kiếm gần đây
    • Nội dung
    • QR Code
    • 0
    • 0
    • Sao chép

    Giải Thuật Là Gì?

    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.
    25/08/2015
    31/08/2020
    5 phút đọc
    Giải Thuật Là Gì?

    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.

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Đề xuất

    Thuật Giải A*
    Giới thiệu và hướng dẫn hiện thực thuật giải A* - A-star tìm kiếm đường ...
    Giải Thuật Tìm Kiếm Minimax
    Giải thuật Minimax là một thuật toán đệ quy lựa chọn bước đi kế tiếp ...

    Khám phá

    Mã Hóa Base64
    Base64 không phải là một thuật toán mã hóa và trong mọi trường hợp, nó ...
    MD5
    MD5 (MD5 Message-Digest Algorithm) là một thuật toán tóm tắt thông điệp, ...
    Thuật Toán Vẽ Đường Thẳng Midpoint
    Đường thẳng trên một màn hình máy tính là một tập hợp các điểm có kích ...
    Thuật Toán Nén Dữ Liệu RLE
    Trong quá trình lưu trữ cũng như truyền dữ liệu, việc nén dữ liệu là ...
    Heap Sort - Thuật Toán Sắp Xếp Vun Đống
    Với độ phức tạp trong trường hợp xấu nhất bằng O (n log n), giải thuật ...
    Thuật Toán PID trong Điều Khiển Tự Động
    Chi tiết về thuật toán PID, các ví dụ thực tế và hướng đưa thuật toán ...
    Affiliate Marketing là gì?
    Tìm hiểu về cách thu lợi từ cộng đồng của bản thân đã gầy dựng và phát ...
    Giải Thuật Cắt Tỉa Alpha-beta
    Cắt tỉa Alpha-beta sẽ giúp loại bỏ những không gian trạng thái không cần ...
    Khi bạn nhấn vào liên kết sản phẩm do STDIO đề xuất và mua hàng, STDIO có thể nhận được hoa hồng. Điều này hỗ trợ STDIO tạo thêm nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    developer@stdio.vn

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020