Giải thuật là gì!!!

1.Giải thuật là gì?

1 cách cơ bản, có thể coi giải thuật là 1 tập các thủ tục, hàm, cấu trúc điều khiển theo 1 trình tự thực hiện nào đó nhằm thực hiện bài toán được đặt ra cho chương trình.

Người ta thường chia ra 2 loại giải thuật cơ bản:

+ Giải thuật xác định: là các loại giải thuật được áp dụng cho những vấn đề mà lời giải có thể biểu diễn được dưới dạng toán học 1 cách rõ ràng. Trong loại giải thuật này các bước để thực hiện, số lần lặp... đã được xác định trước và rất dễ dàng để tính toán chi phí phải bỏ ra cho nó. Và thường thì loại giải thuật này ít khi có chứa cấu trúc điều khiển rẽ nhánh.

Vd: Vẽ 100 điểm ngẫu nhiên trên màn hình.

+ Giải thuật không xác định: loại giải thuật này áp dụng cho những vấn đề mà lời giải chưa có sẵn mà được lựa chọn qua 1 số lần chọn lựa những khả năng có thể nào đó ở những bước nào đó.

Vd: Cho 1 hình chữ nhật cụ thể. Vẽ các điểm có giá trị tọa độ x,y được phát sinh ngẫu nhiên cho tới khi điểm ngẫu nhiên nằm ngoài hình chữ nhật thì dừng.

+ Chắc bạn cũng thấy thì trong thực tế, các vấn đề thường nằm dưới dạng bài toán không xác định là chính.

+ Ngoài ra còn 1 loại giải thuật heuristic: nói 1 cách dễ hiểu thì đây là 1 loại giải thuật mang tính “may mắn” rất nhiều. Loại thuật toán này dựa trên 1 thứ “cảm tính” (được trừu tượng hoá thành 1 hàm đánh giá heuristic) nào đó của con người trong việc giải quyết vấn đề. Bạn cảm thấy giải quyết bài toán theo hướng nào là tốt hơn thì đi theo hướng đó. Và nếu “cảm tính” của bạn sai thì bài toán có thể trở thành dài hoặc đi vào lối cụt. Nhưng nếu “cảm tính” của bạn đúng thì bài toán có thể được giải quyết rất nhanh.

Vd: Cho 1 tập các trạm điện thoại và khoảng các giữa các trạm đã được xác định. Hãy tìm 1 cách nối dây để các trạm được nối với nhau và tốn ít dây nhất. Thì có 1 loại heuristic theo nguyên lí “tham lam” là: chọn ra trong các trạm chưa nối, dây trạm có khoảng cách ngắn nhất tới trạm đang xét. (Thật ra thuật toán này có thể thực hiện được 1 cách tối ưu bằng cách “vét cạn” tất cả các đường dây có thể tạo ra rồi chọn đường ngắn nhất, nhưng trong trường hợp số trạm là quá nhiều thì giải thuật này sẽ không hiệu quả do tốn quá nhiều thời gian, chi phí tính toán, chi phí lưu giữ kết quả...)

2 thứ để cấu thành chương trình là Cấu trúc đữ liệu và Giải thuật. Và giải thuật thì hoạt động dựa trên cấu trúc dữ liệu. Như vậy sẽ có 1 sự ảnh hưởng qua lại giữa CTDL mà bạn chọn lựa và thuật toán.

Nếu ngay từ đầu bạn chọn 1 CTDL “ngon lành”, thích hợp thì việc viết giải thuật sẽ rất đơn giản và tốc độ của giải thuật cũng nhanh hơn. Còn nếu bạn chọn lựa 1 CTDL không tốt thì giải thuật của bạn sẽ có thể rất rườm rà và rắc rối, ảnh hưởng tới tốc độ.

+ Cho nên yêu cầu của 1 CTDL trong giải thuật là phải đơn giản, tiết kiệm tài nguyên hệ thống nhưng đầy đủ và biểu diễn được bài toán. Đồng thời những toán tử, những hàm xử lí trên dữ liệu đó phải đảm bảo đơn giản và được thực hiện nhanh chóng. Để làm được điều này đòi hỏi ở người lập trình viên những bước phân tích lúc ban đầu rất quan trọng. Bạn phải hiểu rõ những yêu cầu của đề bài, phải thấy rõ bản chất, cũng như phải biết cách thu gọn, đơn giản hoá bài toán. Cũng như bạn phải biết rõ những thao tác nào sẽ thường xuyên được thực hiện trên CTDL về sau, đây là 1 yêu cầu rất quan trọng để bạn có thể cân nhắc CTDL cho hợp lí. (Điểm này thì thút thật là snow còn phải học hỏi dài dài...)

Ví dụ: 1 ví dụ đơn giản là bài toán 8 con hậu. Cho 1 bàn cờ vua 8x8. Hãy liệt kê ra tất cả các cách đặt 8 con hậu trên bàn cờ sao cho trên mỗi hàng hoặc mỗi cột của bàn cờ chỉ có duy nhất 1 con hậu mà thôi.

Phân tích đề bài thì bạn thấy vì bài toán yêu cầu liệt kê tất cả nên chắc chắn nó sẽ được giải bằng phương pháp “vét cạn”. Vấn đề còn lại là bạn cần lưu lại kết quả của những lần “vét cạn” như thế nào.

Ở đây đơn giản nhất ta sẽ nghĩ ngay tới 1 mô hình mô phỏng rất tốt bàn cờ đó là 1 mảng 2 chiều 8x8. Các ô trống ko đặt quân cờ sẽ được đặt giá trị là False (0). Các ô có đặt quân cờ sẽ được đặt giá trị là True (1).

Nhưng vấn đề là, như vậy mỗi một trường hợp tìm được bạn lại phải lưu nó bằng 1 mảng 2 chiều 8x8 là rất tốn bộ nhớ, thứ 2 là việc duyệt trên 1 mảng 2 chiều sẽ khiến cho thuật giải của bạn trong mỗi lần duyệt kiểm tra sẽ phải tốn chi phí (n*n) làm ảnh hưởng tới tốc độ của bài toán.

Vậy bạn sẽ phải tìm ra 1 CTDL tốt hơn là mảng 2 chiều đề biểu diễn bài toán này. Nhìn đi nhìn lại tự nhiên bạn thấy “người anh em” của mảng 2 chiều là mảng 1 chiều sao mà “dễ sương” quá à... Vậy là bạn sẽ bắt đầu nghĩ xa hơn 1 chút với mảng 1 chiều và bạn sẽ tìm được 1 cách biểu diển tiết kiệm hơn nhiều.

Đó là bạn chỉ cần 1 mảng 1 chiều 8 phần tử. Mỗi phần tử của mảng được coi là biểu diễn toạ độ của lần lượt 8 con cờ trên bàn cờ theo qui ước sau: chỉ số của phần tử a[i] sẽ biểu diễn cho toạ độ hàng. Giá trị lưu trong mổi một phần tử sẽ biểu diễn cho toạ độ cột của các con hậu.

a[3]=5 <=== con hậu trên dòng thứ 3 được đặt trên cột thứ 5.

Như vậy việc lưu giữ kết quả sẽ được tiết kiệm tài nguyên bộ nhớ hơn và việc duyệt kiểm tra cũng nhanh hơn do chỉ duyệt trên 1 mảng 1 chiều 8 phần tử mà thôi.

+ Ngoài ra đã nói ở bài trên các kiểu dữ liệu càng phức tạp thì các toán tử làm việc trên nó sẽ phức tạp và chậm hơn.

Vd: khi làm việc với các con số bạn phải hạn chế việc sử dụng kiểu số thực (float) nếu không cần thiết thì bạn nên thay nó bằng kiểu nguyên (integer) nếu có thể...

Vd: 1 ví dụ khác cho việc chọn kiểu dữ liệu. Chẳng hạn bạn cần xây dựng 1 chương trình quản lí các nhân viên cho 1 công ty nào đó. Các nhân viên có thông tin Tên, Số điện thoại, địa chỉ.

Nếu bạn chỉ dừng ở đây mà không biết cách tự phát triển tiếp, bạn sẽ ngay lập tức tạo ra 1 cấu trúc như sau (trong C):

CODE c++:

struct NhanVien{ char Ten[255]; char DiaChi[255]; int DT[7];}

Thật ra là có hơi “hoang” như nảy đã nói vì int tới 2 byte trong 1 mỗi một số trong số điện thoại chỉ có từ 0 -> 9 tức chưa vượt quá 1 byte. Vậy ta có thể chọn kiểu là char (trong C char còn có thể coi là 1 kiểu số nguyên 1 byte) 

Nhưng sau đó khi bước vào xây dựng các hàm, các chương trình làm việc trực tiếp với CTDL này bạn sẽ thấy ngay ra 1 vấn đề khó khăn. Bạn sẽ thấy thao tác thường xuyên thực hiện trên CTDL NhanVien nhất là tìm kiếm. Nhưng khi tìm kiếm 1 nhân viên bạn sẽ dựa trên khoá là gì?

Nếu theo như struct mà bạn tạo ở trên thì khoá đó sẽ là Ten. Nhưng bạn cần hiểu 1 điều là Ten vốn có kiểu là chuỗi kí tự string (trong C string được coi là mảng 1 chiều của kiểu kí tự char). Mọi thao tác trên chuỗi kí tự luôn đòi hỏi 1 sự phức tạp và tốn kém. Bao gồm việc so sánh các kí tự, độ dài chuỗi, kết thúc chuỗi, các trường hơp upper case và lower case (kí tự viết hoa hoặc thường, thường thì bạn phải chuyển tất cả kí tự trong 2 chuỗi về cùng là upper case hoặc lowercase trước khi xét)... nói chung sẽ ảnh hưởng rất nhiều đến tốc độ và tên càng dài thì càng chậm (do tên không có kích thước cố định trước...).

Cũng có vài cải tiến nho nhỏ trong các hàm có thể giúp cho việc tìm kiếm nhanh hơn. Chẳng hạn như đầu tiên bạn so sánh chiều dài 2 chuỗi tên, nếu thấy ko dài bằng nhau thì bỏ qua không cần so sánh... Nhưng bản thân hàm kiểm tra độ dài chuỗi cũng đã mất 1 chi phí O(n) do phải duyệt đếm từ đầu đến cuối chuỗi kí tự để tìm kí tự đặc biệt đánh dấu cho việc kết thúc chuỗi (hoặc lấy địa chỉ kí tự đầu, trừ địa chỉ kí tự cuối rồi chia cho kích thước kiểu kí tự). Ngay cả những ngôn ngữ “sừng sỏ” trong việc xử lí chuỗi hiện nay cũng còn phải “sợ” các chuỗi kí tự mặc dù vẫn chạy tốt nhưng vẫn chậm và ảnh hưởng tới tốc độ chung của chương trình (như SQL trong cơ sở dữ liệu, mặc dù có các hàm xử lí chuỗi rất tốt, nhưng 1 lập trình viên tốt trên SQL luôn tránh né chuyện so sánh các chuỗi có độ dài ko xác định nếu có thể...).

Tóm lại là bạn thấy việc dùng Ten làm khoá so sánh là điều bất khả thi và chậm. Như vậy bạn phải nghĩ tới chuyện cải tiến lại CTDL của mình 1 tí và bạn nghĩ là bạn phải “thêm thắt” gì đó vào struct ban đầu để cho nó “hay ho” hơn.

Nếu để ý thì chắc bạn thấy rằng các nhân viên trong 1 công ty ngoài Tên thì thường có thêm 1 thông tin nữa là Mã Số Nhân Viên. Vậy ta có thể có 2 kiểu struct Nhân Viên sau đây : CODE c++:

struct NhanVien1{ char Ten[255]; char MSNV[10]; char DiaChi[255]; int DienThoai[7];};

hoặc CODE c++:

struct NhanVien2:{char Ten[255];int MSNV;char DiaChi[255];int DienThoai[7];};

Thấy struct NhanVien1 có MSNV kiểu là string, chắc bạn rủa thầm: “Vớ vẩn quá nha!!! Vậy có khác gì tránh vỏ dưa gặp vỏ dừa đâu, tránh cái Ten kiểu string bằng 1 cái MSNV kiểu string thì có gì khác nhau đâu?”

Thật ra là có khác nhau đó! Thứ nhất đây là MSNV do bạn tạo ra nên nó phải tuân theo 1 số qui tắc nhập mà bạn buộc cho nó và user buộc phải tuân thủ trong quá trình nhập cũng như tìm kiếm. Các qui tắc đó bao gồm độ dài (mã số gồm bao nhiêu kí tự), tất cả phải là upper case hoặc cùng là lower case, các con số nằm ở vị trí nào, kí tự nằm ở vị trí nào...(khác hẳn với tên vốn không có qui định độ dài, kí tự...)

Ví dụ:

HA02321

HA03435

Các bài viết c