Thuật toán

Thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề.

Thuật toán là gì

Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán.

ML-06.png

Tại sao lại là "Thuật toán"?

Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông.

Các đặc trưng của thuật toán

1. Tính xác định

Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn.

Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải ? Tính "không mập mờ" và "có thể thực thi được" gọi chung là tính xác định.

Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được.

2. Tính hữu hạn

Tính "dừng" hay hữu hạn là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau :

B1. Hỏi giá trị của n.
B2. S = 0
B3. i = 1
B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5
B5. Cộng thêm i vào S
B6. Cộng thêm 2 vào i
B7. Quay lại bước B4.
B8. Tổng cần tìm chính là S.

Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n. Thay vì viết là "nếu i lớn hơn n" thì ta thay bằng điều kiện "nếu i bằng n+1" vì theo toán học "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều kiện "i=n+1" không phải lúc nào cũng đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ. Nếu n là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn.

3. Tính đúng

Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học sinh nhất định là có khả năng đưa ra lời giải đúng!

4. Tính hiệu quả

Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán.

5. Tính tổng quát

Thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.

Các thuật toán cơ bản

Thuật toán

Trong khoa học máy tính, thuật toán là một tập hợp các hướng dẫn hoặc quy trình được sử dụng để giải quyết một vấn đề tính toán. Dưới đây là một số thuật toán cơ bản:

  1. Thuật toán sắp xếp: Là thuật toán sắp xếp các phần tử trong một danh sách hoặc mảng theo một thứ tự nhất định, ví dụ như sắp xếp theo thứ tự tăng dần hoặc giảm dần.
  2. Thuật toán tìm kiếm: Là thuật toán tìm kiếm một phần tử hoặc một tập hợp các phần tử trong một danh sách hoặc mảng.
  3. Thuật toán đệ quy: Là thuật toán sử dụng một hàm để gọi lại chính nó để giải quyết một vấn đề.
  4. Thuật toán cây: Là thuật toán sử dụng cấu trúc dữ liệu cây để giải quyết một vấn đề.
  5. Thuật toán đồ thị: Là thuật toán sử dụng cấu trúc dữ liệu đồ thị để giải quyết một vấn đề.

ML-06.png

Các thuật toán này là những thuật toán cơ bản và được sử dụng rộng rãi trong lĩnh vực khoa học máy tính. Việc hiểu và biết cách sử dụng chúng sẽ giúp ích rất nhiều trong quá trình giải quyết các vấn đề tính toán.

Các thuật toán sắp xếp
  1. Sắp xếp nổi bọt (Bubble sort): Sắp xếp bằng cách so sánh hai phần tử liền kề và đổi chỗ chúng nếu chúng không đúng thứ tự.
  2. Sắp xếp chọn (Selection sort): Sắp xếp bằng cách lựa chọn phần tử nhỏ nhất và đưa nó về đầu danh sách, tiếp tục với danh sách còn lại.
  3. Sắp xếp chèn (Insertion sort): Sắp xếp bằng cách chèn mỗi phần tử vào vị trí đúng của nó trong danh sách đã sắp xếp trước đó.
  4. Sắp xếp nhanh (Quick sort): Sắp xếp bằng cách chọn một phần tử làm chốt, chia danh sách thành hai phần dựa trên phần tử chốt đó, và tiếp tục sắp xếp các phần tử con.
  5. Sắp xếp trộn (Merge sort): Sắp xếp bằng cách chia danh sách thành nhiều phần, sắp xếp từng phần, sau đó trộn các phần đã sắp xếp lại với nhau.
Các thuật toán tìm kiếm
  1. Tìm kiếm tuyến tính (Linear search): Tìm kiếm bằng cách so sánh từng phần tử trong danh sách với giá trị cần tìm kiếm.
  2. Tìm kiếm nhị phân (Binary search): Tìm kiếm bằng cách chia đôi danh sách và so sánh giá trị cần tìm kiếm với giá trị ở giữa danh sách đã chia đôi.
Các thuật toán đệ quy
  1. Thuật toán đệ quy tuyến tính (Linear recursive algorithm): Giải quyết bài toán bằng cách giải bài toán con của nó và trở về bài toán ban đầu.
  2. Thuật toán đệ quy nhị phân (Binary recursive algorithm): Giải quyết bài toán bằng cách chia đôi bài toán thành những bài toán con nhỏ hơn và giải quyết chúng.
Các thuật toán cây
  1. Cây nhị phân tìm kiếm (Binary search tree): Một cây nhị phân tìm kiếm là một cây nhị phân mà ở mỗi nút, các nút con bên trái có giá trị nhỏ hơn nút hiện tại và các nút con bên phải có giá trị lớn hơn nút hiện tại.
  2. Cây đỏ đen (Red-black tree): Một cây đỏ đen là một cây nhị phân tìm kiếm được cân bằng với một số quy tắc đặc biệt, điều này đảm bảo rằng thời gian truy cập và thêm, xóa các phần tử là O(log n).
  3. Cây AVL (AVL tree): Một cây AVL là một cây nhị phân tìm kiếm được cân bằng với một số quy tắc đặc biệt, điều này đảm bảo rằng thời gian truy cập và thêm, xóa các phần tử là O(log n).
Các thuật toán đồ thị
  1. Thuật toán Dijkstra: Tìm đường đi ngắn nhất trong đồ thị có trọng số không âm.
  2. Thuật toán Bellman-Ford: Tìm đường đi ngắn nhất trong đồ thị có thể có trọng số âm.
  3. Thuật toán Floyd-Warshall: Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số.
  4. Thuật toán Prim: Tìm cây khung nhỏ nhất trong đồ thị có trọng số.
  5. Thuật toán Kruskal: Tìm cây khung nhỏ nhất trong đồ thị có trọng số.

Thuật giải Heuristic

Trong quá trình nghiên cứu giải quyết các vấn đề – bài toán, người ta đã đưa ra những nhận xét như sau:

heuristicseval.png

Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán: tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiên nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ.

Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở cửa cho chúng ta trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra.

Một trong những thuật giải thường được đề cập đến và sử dụng trong khoa học trí tuệ nhân tạo là các cách giải theo kiểu Heuristic

Thuật giải Heuristic là gì?

Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau:

Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau:

Phương pháp biểu diễn thuật toán

Có 3 phương pháp biểu diễn thuật toán:

1. Ngôn ngữ tự nhiên

Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1...

2. Lưu đồ - sơ đồ khối

Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý.

Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác. Một thao tác là thao tác chọn lựa dựa theo một điều kiện nào đó. Chẳng hạn: thao tác "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" là thao tác chọn lựa. Các thao tác còn lại không thuộc loại chọn lựa được xếp vào loại hành động. Chẳng hạn, "Chọn một hộp bất kỳ và để lên đĩa cân còn trống." là một thao tác thuộc loại hành động.

2.1. Thao tác chọn lựa (decision)

Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.

algorithm_decision.png

2.2. Thao tác xử lý (process)

Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.

al_process.GIF

2.3. Ðường đi (route)

Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình thực hiện sẽ lần lượt đi từ bước trước đến bước sau (trừ khi có yêu cầu nhảy sang bước khác). Trong ngôn ngữ lưu đồ, do thể hiện các bước bằng hình vẽ và có thể đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình tự thực hiện các thao tác.

Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện. Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1, B2, B3.

Từ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với điều kiện thỏa và một hướng ứng với điều kiện không thỏa. Do vậy, ta dùng hai cung xuất phát từ các đỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện không thỏa.

Ví dụ: Lưu đồ thuật toán giải phương trình bậc 2

al_route.GIF

2.4. Ðiểm cuối (terminator)

Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn bằng hình ovan, bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end. Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu) hoặc cung đi vào (điểm kết thúc). Xem lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách sử dụng của điểm cuối.

2.5. Ðiểm nối (connector)

Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với nhau. Bên trong điểm nối, ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối.

al_connector.GIF

2.6. Ðiểm nối sang trang (off-page connector)

Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang.

al_off-page_connector.GIF

Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ.

3. Mã giả

Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp.

Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên.

Ví dụ:

if Delta > 0 then begin
	x1=(-b-sqrt(delta))/(2*a)
	x2=(-b+sqrt(delta))/(2*a)
	xuất kết quả : phương trình có hai nghiệm là x1 và x2
else if delta = 0 then
	xuất kết quả : phương trình có nghiệm kép là -b/(2*a)
else {trường hợp delta < 0 }
	xuất kết quả : phương trình vô nghiệm

Thuật toán quay lui

1. Khái niệm

Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.

ba-state-space-tree.png

2. Phương pháp thực hiện

Giả thiết cấu hình cần liệt kê có dạng (x1, x2,…, xn). Khi đó thuật toán quay lui thực hiện qua các bước sau:

Bước 1: Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x1 sẽ thực hiện bước tiếp theo.

Bước 2: Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3 … cứ tiếp tục như vậy đến bước n.

Bước n: Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (x1, x2, …, xn).

Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các cấu hình n phần tử dạng (x1, x2, .., xn) bằng cách thử cho x1 nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x1 lại liệt kê tiếp cấu hình n - 1 phần tử (x2, x3, …, xn).

3. Cài đặt thuật toán

Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)

{Thủ tục này thử cho xi nhận lần lượt các giá trị mà nó có thể nhận}
procedure Try(i: Integer);
begin
	for (mọi giá trị V có thể gán cho xi) do
		begin
			<Thử cho xi := V>;
			if (xi là phần tử cuối cùng trong cấu hình) then
				<Thông báo cấu hình tìm được>
			else
			begin
				<Ghi nhận việc cho xi nhận giá trị V (Nếu cần)>;
				Try(i + 1); {Gọi đệ quy để chọn tiếp xi+1}
				<Nếu cần, bỏ ghi nhận việc thử xi := V, để thử giá trị khác>;
			end;
		end;
end;

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort) là thuật toán sắp xếp một mảng số bằng cách đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự (số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi không thể đổi chỗ được nữa.

thuat-toan-sap-xuat-bubble-sort.webp

Việc sắp xếp có thể tiến hành từ trên xuống hoặc từ dưới lên.

Ví dụ minh họa: sắp xếp dãy số [5 1 4 2 8] tăng dần.

#include <stdio.h>

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}
 
// Hàm sắp xếp bubble sort
void bubbleSort(int arr[], int n)
{
    int i, j;
    bool haveSwap = false;
    for (i = 0; i < n-1; i++){
    // i phần tử cuối cùng đã được sắp xếp
        haveSwap = false;
        for (j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
                haveSwap = true; // Kiểm tra lần lặp này có swap không
            }
        }
        // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
        if(haveSwap == false){
            break;
        }
    }
}
 
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {5 1 4 2 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Dãy số tăng dần: n");
    printArray(arr, n);
    return 0;
}

Thuật toán sắp xếp chọn (Selection sort)

Thuật toán sắp xếp chọn (Selection sort) là thuật toán sắp xếp đơn giản nhất trong các thuật toán sắp xếp cơ bản. Cách thức hoạt động của thuật toán này như sau:

  1. Tìm phần tử nhỏ nhất trong danh sách.
  2. Đưa phần tử nhỏ nhất này về vị trí đầu tiên của danh sách.
  3. Lặp lại quá trình trên với danh sách còn lại cho đến khi danh sách được sắp xếp hoàn toàn.

Độ phức tạp của thuật toán sắp xếp chọn (Selection sort) là O(n^2), tương đương với thuật toán sắp xếp nổi bọt (Bubble Sort). Tuy nhiên, Selection Sort thường hiệu quả hơn Bubble Sort do có ít hoán đổi hơn.

Dưới đây là đoạn code Python mẫu để sắp xếp một danh sách sử dụng thuật toán sắp xếp chọn:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Tìm phần tử nhỏ nhất trong danh sách chưa sắp xếp
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Đưa phần tử nhỏ nhất về đầu danh sách chưa sắp xếp
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

Ví dụ: Cho danh sách [64, 25, 12, 22, 11]. Sử dụng thuật toán sắp xếp chọn, ta có kết quả sau khi sắp xếp là [11, 12, 22, 25, 64].

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr) # Kết quả là [11, 12, 22, 25, 64]

Thuật toán sắp xếp chèn (Insertion sort)

Thuật toán sắp xếp chèn (Insertion sort) là một trong số thuật toán sắp xếp đơn giản nhất trong các thuật toán sắp xếp cơ bản. Cách thức hoạt động của thuật toán này như sau:

  1. Bắt đầu với danh sách chưa sắp xếp, ta lấy phần tử đầu tiên và chèn nó vào danh sách đã sắp xếp.
  2. Tiếp tục lấy phần tử tiếp theo, so sánh với các phần tử trong danh sách đã sắp xếp để tìm vị trí thích hợp để chèn phần tử đã lấy.
  3. Lặp lại quá trình trên cho đến khi danh sách được sắp xếp hoàn toàn.

Độ phức tạp của thuật toán sắp xếp chèn (Insertion sort) là O(n^2), tương đương với thuật toán sắp xếp nổi bọt (Bubble Sort) và thuật toán sắp xếp chọn (Selection Sort). Tuy nhiên, Insertion Sort thường hiệu quả hơn với các danh sách đã gần sắp xếp.

Dưới đây là đoạn code Python mẫu để sắp xếp một danh sách sử dụng thuật toán sắp xếp chèn:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

    return arr

Ví dụ: Cho danh sách [64, 25, 12, 22, 11]. Sử dụng thuật toán sắp xếp chèn, ta có kết quả sau khi sắp xếp là [11, 12, 22, 25, 64].

arr = [64, 25, 12, 22, 11]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # Kết quả là [11, 12, 22, 25, 64]

Thuật toán sắp xếp nhanh (Quick Sort)

Thuật toán Quick Sort được phát triển bởi C.A.R

Đúng như tên gọi, thuật toán sắp xếp nhanh là một thuật toán cho kết qua nhanh, gọn, nhẹ. Thuật toán này dựa trên việc chia một mảng thành các mảng nhỏ hơn.

Nếu so với các thuật toán sắp xếp khác như Insertion Sort hay sắp xếp nổi bọt (Bubble Sort), thì thuật toán sắp xếp nhanh cho tốc độ nhanh hơn đáng kể.

Thuật toán Quick sort là một thuật toán chia để trị (divide and Conquer Algorithm). Nó sẽ chọn một phần tử trong mảng làm điểm đánh dấu (pivot). Sau khi lựa chọn được điểm pivot, bước tiếp theo sẽ chia mảng thành nhiều mảng con dựa vào pivot đã chọn. Và lặp đi lặp lại như vậy cho đến khi kết thúc.

Tốc độ của thuật toán bị ảnh hưởng bởi việc chọn pivot. Có nhiều cách chọn pivot, dưới đây là một số cách:

Để mình họa cho thuật toán sắp xếp nhanh, chúng ta cùng thực hành một bài toán: Sắp xếp mảng sau theo thứ tự tăng dần: [10, 7, 8, 9, 1, 5]

#include<iostream>
#include<cstdlib>
 
using namespace std;
 
// Swapping two values.
void swap(int *a, int *b)
{
    int temp; 
    temp = *a;
    *a = *b;
    *b = temp;
}
 
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
    int pivot, index, i;
    index = low;
    pivot = high;
 
    // Getting index of the pivot.
    for(i=low; i < high; i++)
    {
        if(a[i] < a[pivot])
        {
            swap(&a[i], &a[index]);
            index++;
        }
    }
    // Swapping value at high and at the index obtained.
    swap(&a[pivot], &a[index]);
 
    return index;
}
 
// Random selection of pivot.
int RandomPivotPartition(int a[], int low, int high)
{
    int pvt, n, temp;
    n = rand();
    // Randomizing the pivot value in the given subpart of array.
    pvt = low + n%(high-low+1);
 
    // Swapping pivot value from high, so pivot value will be taken as a pivot while partitioning.
    swap(&a[high], &a[pvt]);
 
    return Partition(a, low, high);
}
 
int QuickSort(int a[], int low, int high)
{
    int pindex;
    if(low < high)
    {
        // Partitioning array using randomized pivot.
        pindex = RandomPivotPartition(a, low, high);
        // Recursively implementing QuickSort.
        QuickSort(a, low, pindex-1);
        QuickSort(a, pindex+1, high);
    }
    return 0;
}
 
int main()
{
    int n, i;
    cout<<"\nEnter the number of data elements to be sorted: ";
    cin>>n;
 
    int arr[n];
    for(i = 0; i < n; i++)
    {
        cout<<"Enter element "<<i+1<<": ";
        cin>>arr[i];
    }
 
    QuickSort(arr, 0, n-1);
 
    // Printing the sorted data.
    cout<<"\nSorted Data ";
    for (i = 0; i < n; i++)
            cout<<"->"<<arr[i];
 
    return 0;
}

 

Thuật toán sắp xếp trộn (Merge sort)

Thuật toán sắp xếp trộn (Merge sort) là một thuật toán sắp xếp đệ quy được sử dụng rộng rãi trong các ứng dụng thực tế. Cách thức hoạt động của thuật toán này như sau:

  1. Chia danh sách cần sắp xếp thành hai phần bằng nhau.
  2. Sắp xếp hai phần đó bằng cách sử dụng thuật toán sắp xếp trộn (Merge Sort).
  3. Trộn hai phần đã sắp xếp lại với nhau để tạo thành danh sách đã sắp xếp.

Thuật toán sắp xếp trộn được chia làm hai phần chính: quá trình chia đôi danh sách và quá trình trộn hai danh sách đã sắp xếp. Quá trình chia đôi danh sách được thực hiện đệ quy cho đến khi danh sách chỉ còn một phần tử.

Độ phức tạp của thuật toán sắp xếp trộn (Merge sort) là O(n log n), tốc độ nhanh hơn so với các thuật toán sắp xếp cơ bản khác.

Dưới đây là đoạn code Python mẫu để sắp xếp một danh sách sử dụng thuật toán sắp xếp trộn:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

    return arr

Ví dụ: Cho danh sách [64, 25, 12, 22, 11]. Sử dụng thuật toán sắp xếp trộn, ta có kết quả sau khi sắp xếp là [11, 12, 22, 25, 64].

arr = [64, 25, 12, 22, 11]
sorted_arr = merge_sort(arr)
print(sorted_arr) # Kết quả là [11, 12, 22, 25, 64]

Thuật toán tìm kiếm tuyến tính (Linear search)

Tìm kiếm tuyến tính (Linear search) là một thuật toán đơn giản nhất trong các thuật toán tìm kiếm dữ liệu.

Cách thức hoạt động của thuật toán này như sau:

  1. Để tìm phần tử x trong danh sách đã cho, ta duyệt từ đầu đến cuối danh sách.
  2. Nếu phần tử được tìm thấy, trả về vị trí của nó trong danh sách.
  3. Nếu phần tử không được tìm thấy, trả về giá trị -1.

Độ phức tạp của thuật toán tìm kiếm tuyến tính (Linear search) là O(n), với n là số lượng phần tử trong danh sách.

Dưới đây là đoạn code Python mẫu để tìm kiếm một phần tử trong danh sách sử dụng thuật toán tìm kiếm tuyến tính:

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Ví dụ: Cho danh sách [64, 25, 12, 22, 11] và tìm kiếm phần tử có giá trị là 22. Sử dụng thuật toán tìm kiếm tuyến tính, ta có kết quả là 3.

arr = [64, 25, 12, 22, 11]
x = 22
result = linear_search(arr, x)
print(result) # Kết quả là 3

Thuật toán tìm kiếm nhị phân (Binary search)

Thuật toán Tìm kiếm nhị phân (Binary Search) là một thuật toán cao cấp hơn tìm kiếm tuần tự.

Đối với các dãy số lớn, thuật toán này tốt hơn hẳn so với các thuật toán tìm kiếm khác. Nhưng nó đòi hỏi dãy số phải được sắp xếp từ trước.

Tuy thuật toán binary search có ưu điểm là tìm kiếm nhanh, nhưng cũng có nhược điểm là nếu danh sách bị thay đổi, danh sách đó phải được sắp xếp lại trước khi tiến hành tìm kiếm tiếp. Và thao tác này thường tốn thời gian.

thuat-toan-tim-kiem-nhi-phan-binary-search.webp

Minh họa cho thuật toán tìm kiếm nhị phân, chúng ta cùng làm bài toán sau: Tìm vị trí phần tử có giá trị là 23 trong một mảng A[2,5,8,12,16,23,38,56,72,91] đã được sắp xếp.

#include <iostream> 
using namespace std; 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

Thuật toán tìm đường đi ngắn nhất Dijkstra

Với bài toán tìm đường đi ngắn nhất, chúng ta có một số thuật toán nổi tiếng giải quyết nó như: Dijkstra hay Floyd.

Thuật toán Dijkstra có 2 loại là:

Dưới đây là code minh họa cho loại thứ 1 của thuật toán Dijkstra.

#include<iostream>

#include<conio.h>

using namespace std;

#define MAX 50

#define TRUE 1

#define FALSE 0

#define VOCUNG 10000000

int n; //số đỉnh của đồ thị.

int s; //đỉnh đầu.

int t; //đỉnh cuối

char chon;

int truoc[MAX]; //mảng đánh dấu đường đi.

int d[MAX]; //mảng đánh dấu khoảng cách.

int Matrix[MAX][MAX]; //ma trận trọng số

int chuaxet[MAX]; //mảng đánh dấu đỉnh đã được gán nhãn.

void Init(void) {

  freopen("DIJKSTRA.IN", "r", stdin);

  cin >> n;

  cout << "So dinh : " << n << endl;

  cin >> s >> t; //nhập đỉnh đầu và đỉnh cuối của đồ thị.

  //nhập ma trận của đồ thị.

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= n; j++) {

      cin >> Matrix[i][j];

      if (Matrix[i][j] == 0) Matrix[i][j] = VOCUNG;

    }

  }

}

void Result(void) {

  cout << "Duong di ngan nhat tu " << (char)(s + 'A' - 1) << " den " << (char)(t + 'A' - 1) << " la" << endl;

  cout << (char)(t + 'A' - 1) << "<="; //in đỉnh cuối dưới dạng char.

  int i = truoc[t];

  while (i != s) {

    cout << (char)(i + 'A' - 1) << "<="; //in ra kết quả dưới dạng char.

    i = truoc[i];

  }

  cout << (char)(s + 'A' - 1); //in đỉnh đầu dưới dạng char.

  cout << endl << "Do dai duong di la : " << d[t];

}

void Dijkstra(void) {

  int u, minp;

  //khởi tạo nhãn tạm thời cho các đỉnh.

  for (int v = 1; v <= n; v++) {

    d[v] = Matrix[s][v];

    truoc[v] = s;

    chuaxet[v] = FALSE;

  }

  truoc[s] = 0;

  d[s] = 0;

  chuaxet[s] = TRUE;

  //bươc lặp

  while (!chuaxet[t]) {

    minp = VOCUNG;

    //tìm đỉnh u sao cho d[u] là nhỏ nhất

    for (int v = 1; v <= n; v++) {

      if ((!chuaxet[v]) && (minp > d[v])) {

        u = v;

        minp = d[v];

      }

    }

    chuaxet[u] = TRUE; // u la dinh co nhan tam thoi nho nhat

    if (!chuaxet[t]) {

      //gán nhãn lại cho các đỉnh.

      for (int v = 1; v <= n; v++) {

        if ((!chuaxet[v]) && (d[u] + Matrix[u][v] < d[v])) {

          d[v] = d[u] + Matrix[u][v];

          truoc[v] = u;

        }

      }

    }

  }

}

void main(void) {

  Init();

  Dijkstra();

  Result();

  getch();

}

Input:

9
1 9
0 6 5 0 8 0 0 0 0
6 0 4 0 0 7 0 0 0
5 4 0 4 0 0 0 0 0
0 0 4 0 4 0 6 0 0
8 0 0 4 0 0 0 6 0
0 7 0 0 0 0 5 0 6
0 0 0 6 0 5 0 4 3
0 0 0 0 6 0 4 0 5
0 0 0 0 0 6 3 5 0

dinh nghia.

1 tuong ung voi dinh A
2 tuong ung voi dinh B
3 tuong ung voi dinh C
4 tuong ung voi dinh D
5 tuong ung voi dinh E
6 tuong ung voi dinh F
7 tuong ung voi dinh G
8 tuong ung voi dinh H
9 tuong ung voi dinh I

Output:

So dinh: 9

Duong di ngan nhat tu A den I la

I<=G<=D<=C<=A

Do dai duong di la: 18

Thuật toán Hashing

Hashing là một thuật toán giúp phân biệt giữa các khối dữ liệu với nhau. Ứng dụng nổi bật và quan trọng nhất của thuật toán này đó chính là cho phép tìm kiếm và tra cứu một bản ghi dữ liệu đã cho trước và mã hóa bản ghi đó một cách nhanh chóng.

Thuật toán này cho phép phát hiện và sửa lỗi khi dữ liệu bị làm nhiễu bởi các quá trình ngẫu nhiên.

thuat-toan-hashing-1.webp

Ngoài ra, thuật toán này cũng có thể sử dụng cho phép tạo ra các giá trị dữ liệu không trùng lặp (Unique) và ứng dụng trong các bộ định tuyến để lưu trữ địa chỉ IP.

Ví dụ đơn giản về thuật toán Hash trong C++:

Key Index (using a hash function) Data
12 12%10 = 2 23
10 10%10 = 0 34
6 6% 10 = 6 54
23 23 % 10 = 3 76
54 54 %10 = 4 75
82 81 %10 = 1 87

Vị trí trong bảng hash sẽ là:

0             1            2            3            4           5            6             7          8            9

34 87 23 76 75
54
  
#include <iostream>

#include <list>

using namespace std;
class HashMapTable {
  // size of the hash table
  inttable_size;
  // Pointer to an array containing the keys
  list < int > * table;
  public:
    // creating constructor of the above class containing all the methods
    HashMapTable(int key);
  // hash function to compute the index using table_size and key
  inthashFunction(int key) {
    return (key % table_size);
  }
  // inserting the key in the hash table
  void insertElement(int key);
  // deleting the key in the hash table
  void deleteElement(int key);
  // displaying the full hash table
  void displayHashTable();
};
//creating the hash table with the given table size
HashMapTable::HashMapTable(intts) {
  this -> table_size = ts;
  table = new list < int > [table_size];
}
// insert function to push the keys in hash table
void HashMapTable::insertElement(int key) {
  int index = hashFunction(key);
  table[index].push_back(key);
}
// delete function to delete the element from the hash table
void HashMapTable::deleteElement(int key) {
  int index = hashFunction(key);
  // finding the key at the computed index
  list < int > ::iterator i;
  for (i = table[index].begin(); i != table[index].end(); i++) {
    if ( * i == key)
      break;
  }
  // removing the key from hash table if found
  if (i != table[index].end())
    table[index].erase(i);
}
// display function to showcase the whole hash table
void HashMapTable::displayHashTable() {
  for (inti = 0; i < table_size; i++) {
    cout << i;
    // traversing at the recent/ current index
    for (auto j: table[i])
      cout << " ==> " << j;
    cout << endl;
  }
}
// Main function
intmain() {
  // array of all the keys to be inserted in hash table
  intarr[] = {
    20,
    34,
    56,
    54,
    76,
    87
  };
  int n = sizeof(arr) / sizeof(arr[0]);
  // table_size of hash table as 6
  HashMapTableht(6);
  for (inti = 0; i < n; i++)
    ht.insertElement(arr[i]);
  // deleting element 34 from the hash table
  ht.deleteElement(34);
  // displaying the final data of hash table
  ht.displayHashTable();
  return 0;
}

Output:

C-Hash-Table-1.1.png.webp

Thuật toán đệ quy nhị phân (Binary recursive algorithm)

Thuật toán đệ quy nhị phân (Binary recursive algorithm) là một thuật toán sắp xếp đặc biệt được sử dụng để tìm kiếm các giá trị trong một danh sách đã sắp xếp.

Cách thức hoạt động của thuật toán này như sau:

  1. Tìm giá trị trung bình của danh sách đã sắp xếp.
  2. So sánh giá trị trung bình với giá trị cần tìm.
  3. Nếu giá trị trung bình bằng giá trị cần tìm, trả về vị trí của giá trị đó trong danh sách.
  4. Nếu giá trị trung bình lớn hơn giá trị cần tìm, tìm kiếm trong nửa đầu tiên của danh sách.
  5. Nếu giá trị trung bình nhỏ hơn giá trị cần tìm, tìm kiếm trong nửa thứ hai của danh sách.
  6. Lặp lại quá trình trên cho đến khi tìm thấy giá trị cần tìm hoặc không còn phần tử nào để tìm kiếm.

Độ phức tạp của thuật toán đệ quy nhị phân (Binary recursive algorithm) là O(log n), tốc độ nhanh hơn so với các thuật toán tìm kiếm khác.

Dưới đây là đoạn code Python mẫu để tìm kiếm một phần tử trong danh sách sử dụng thuật toán đệ quy nhị phân:

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2

        if arr[mid] == x:
            return mid

        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        return -1

Ví dụ: Cho danh sách [11, 12, 22, 25, 64] và tìm kiếm phần tử có giá trị là 25. Sử dụng thuật toán đệ quy nhị phân, ta có kết quả là 3.

arr = [11, 12, 22, 25, 64]
x = 25
result = binary_search(arr, 0, len(arr)-1, x)
print(result) # Kết quả là 3

Thuật toán đệ quy tuyến tính (Linear recursive algorithm)

Thuật toán đệ quy tuyến tính (Linear recursive algorithm) là một phương pháp tìm kiếm giá trị trong một danh sách đã cho bằng cách sử dụng đệ quy. Quá trình tìm kiếm được thực hiện bằng cách so sánh giá trị cần tìm với từng phần tử trong danh sách theo thứ tự tuyến tính.

Cách thức hoạt động của thuật toán này như sau:

  1. Bắt đầu với phần tử đầu tiên trong danh sách.
  2. Nếu phần tử được tìm thấy, trả về vị trí của nó trong danh sách.
  3. Nếu phần tử không được tìm thấy, di chuyển đến phần tử tiếp theo và lặp lại quá trình trên.
  4. Nếu đến cuối danh sách mà không tìm thấy phần tử cần tìm, trả về giá trị -1.

Độ phức tạp của thuật toán đệ quy tuyến tính (Linear recursive algorithm) là O(n), với n là số lượng phần tử trong danh sách. Tuy nhiên, khi danh sách được sắp xếp, thuật toán tìm kiếm này có thể được cải thiện bằng cách sử dụng thuật toán tìm kiếm nhị phân.

Dưới đây là đoạn code Python mẫu để tìm kiếm một phần tử trong danh sách sử dụng thuật toán đệ quy tuyến tính:

def linear_recursive_search(arr, x, i):
    if i >= len(arr):
        return -1
    elif arr[i] == x:
        return i
    else:
        return linear_recursive_search(arr, x, i+1)

Ví dụ: Cho danh sách [64, 25, 12, 22, 11] và tìm kiếm phần tử có giá trị là 22. Sử dụng thuật toán đệ quy tuyến tính, ta có kết quả là 3.

arr = [64, 25, 12, 22, 11]
x = 22
result = linear_recursive_search(arr, x, 0)
print(result) # Kết quả là 3

Thuật toán cây nhị phân tìm kiếm (BST)

Cây nhị phân tìm kiếm (BST) là một cấu trúc dữ liệu rất mạnh mẽ và được sử dụng rộng rãi trong các ứng dụng thực tế. Nó là một cấu trúc dữ liệu dạng cây, trong đó mỗi nút chứa một giá trị và hai con trỏ tới hai nút con của nó: nút con bên trái và nút con bên phải. Giá trị của nút con bên trái luôn nhỏ hơn giá trị của nút cha, và giá trị của nút con bên phải luôn lớn hơn giá trị của nút cha.

BST được sử dụng để lưu trữ tập hợp các phần tử và cung cấp các thao tác tìm kiếm, chèn và xóa phần tử với độ phức tạp O(log n). Điều này làm cho nó trở thành một trong những cấu trúc dữ liệu phổ biến nhất trong lĩnh vực khoa học máy tính.

Các thao tác trên cây nhị phân tìm kiếm

Tìm kiếm (search)

Thao tác tìm kiếm trong BST được thực hiện bằng cách so sánh giá trị cần tìm với giá trị của nút hiện tại. Nếu giá trị cần tìm bằng giá trị của nút hiện tại, trả về nút đó. Nếu giá trị cần tìm nhỏ hơn giá trị của nút hiện tại, chuyển đến nút con bên trái và tiếp tục tìm kiếm. Nếu giá trị cần tìm lớn hơn giá trị của nút hiện tại, chuyển đến nút con bên phải và tiếp tục tìm kiếm.

Chèn (insert)

Thao tác chèn một giá trị vào BST được thực hiện bằng cách tìm kiếm vị trí phù hợp cho giá trị đó và thêm giá trị đó vào BST.

Xóa (delete)

Thao tác xóa một giá trị khỏi BST được thực hiện bằng cách tìm kiếm giá trị đó trong BST và xóa nút chứa giá trị đó. Trong trường hợp nút chứa giá trị đó có ít hơn hai con, nút đó được loại bỏ khỏi BST. Trong trường hợp nút chứa giá trị đó có hai con, nút đó được thay thế bằng giá trị lớn nhất trong cây con bên trái của nó hoặc giá trị nhỏ nhất trong cây con bên phải của nó. Sau đó, nút đó được loại bỏ khỏi BST.

Code mẫu

Dưới đây là một số đoạn mã Python cho các thao tác trên cây nhị phân tìm kiếm:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def search(self, val):
        return self._search(val, self.root)

    def _search(self, val, node):
        if node is None or node.val == val:
            return node
        elif val < node.val:
            return self._search(val, node.left)
        else:
            return self._search(val, node.right)

    def insert(self, val):
        self.root = self._insert(val, self.root)

    def _insert(self, val, node):
        if node is None:
            node = TreeNode(val)
        elif val < node.val:
            node.left = self._insert(val, node.left)
        else:
            node.right = self._insert(val, node.right)
        return node

    def delete(self, val):
        self.root = self._delete(val, self.root)

    def _delete(self, val, node):
        if node is None:
            return node
        elif val < node.val:
            node.left = self._delete(val, node.left)
        elif val > node.val:
            node.right = self._delete(val, node.right)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                temp = self._max(node.left)
                node.val = temp.val
                node.left = self._delete(temp.val, node.left)
        return node

    def _max(self, node):
        while node.right is not None:
            node = node.right
        return node

Với các thao tác tìm kiếm, chèn và xóa trong cây nhị phân tìm kiếm được triển khai trong đoạn mã trên, bạn có thể sử dụng BST để giải quyết các bài toán liên quan đến tìm kiếm, chèn và xóa phần tử. Việc hiểu và ứng dụng cấu trúc dữ liệu này sẽ giúp các nhà phát triển tăng cường hiệu suất và tính ổn định cho các ứng dụng của họ.

Thuật toán cây đỏ đen (Red-black tree)

Cây đỏ đen (Red-black tree) là một cấu trúc dữ liệu dạng cây nhị phân tương tự như cây nhị phân tìm kiếm (BST). Tuy nhiên, cây đỏ đen được thiết kế để giảm thiểu chi phí của các phép cập nhật, bao gồm cả chèn và xóa. Các nút trong cây đỏ đen được đánh dấu bằng màu đỏ hoặc màu đen, và phải tuân thủ một số quy tắc nhất định để đảm bảo rằng cây luôn cân bằng và có độ cao O(log n).

Quy tắc

Các quy tắc sau đây phải được tuân thủ để đảm bảo rằng cây đỏ đen luôn cân bằng:

  1. Mỗi nút là màu đỏ hoặc đen.
  2. Nút gốc luôn luôn phải là màu đen.
  3. Nếu một nút là màu đỏ, thì hai nút con của nó phải là màu đen.
  4. Tất cả các đường đi từ nút gốc đến lá phải có số lượng nút đen bằng nhau.
  5. Nếu một nút là lá, thì nó phải là màu đen.
Các thao tác trên cây đỏ đen

Các thao tác trên cây đỏ đen bao gồm:

Các thao tác này được triển khai bằng các hàm phù hợp. Dưới đây là đoạn mã Python mẫu cho các thao tác trên cây đỏ đen:

class Node:
    def __init__(self, val, color='RED'):
        self.val = val
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        new_node = Node(val, 'RED')
        self._insert(new_node)

    def _insert(self, node):
        if self.root is None:
            self.root = node
            node.color = 'BLACK'
            return

        current = self.root
        parent = None

        while current is not None:
            parent = current
            if node.val < current.val:
                current = current.left
            else:
                current = current.right

        node.parent = parent

        if parent is None:
            self.root = node
            node.color = 'BLACK'
            return

        if parent.color == 'BLACK':
            return

        grandparent = parent.parent
        if parent == grandparent.left:
            uncle = grandparent.right
            if uncle is not None and uncle.color == 'RED':
                parent.color = 'BLACK'
                uncle.color = 'BLACK'
                grandparent.color = 'RED'
                self._insert(grandparent)
            else:
                if node == parent.right:
                    self._rotate_left(parent)
                    node, parent = parent, node
                self._rotate_right(grandparent)
                parent.color = 'BLACK'
                grandparent.color = 'RED'
        else:

 

Thuật toán cây AVL

Cây AVL là một cấu trúc dữ liệu tương tự như cây đỏ đen, được thiết kế để giảm thiểu chi phí của các phép cập nhật, bao gồm cả chèn và xóa. Các nút trong cây AVL được đánh số thứ tự theo giá trị các nút, và phải tuân thủ một số quy tắc nhất định để đảm bảo rằng cây luôn cân bằng và có độ cao O(log n).

Quy tắc

Các quy tắc sau đây phải được tuân thủ để đảm bảo rằng cây AVL luôn cân bằng:

  1. Chiều cao của cây con trái và cây con phải của một nút không quá chênh lệch 1.
  2. Cả cây con trái và cây con phải của một nút đều là cây AVL.
Các thao tác trên cây AVL

Các thao tác trên cây AVL bao gồm:

Các thao tác này được triển khai bằng các hàm phù hợp. Dưới đây là đoạn mã Python mẫu cho các thao tác trên cây AVL:

class AVLTree:
    def __init__(self):
        self.root = None

    def height(self, node):
        if node is None:
            return 0
        return node.height

    def balance_factor(self, node):
        if node is None:
            return 0
        return self.height(node.left) - self.height(node.right)

    def rotate_left(self, x):
        y = x.right
        z = y.left
        y.left = x
        x.right = z
        x.height = max(self.height(x.left), self.height(x.right)) + 1
        y.height = max(self.height(y.left), self.height(y.right)) + 1
        return y

    def rotate_right(self, y):
        x = y.left
        z = x.right
        x.right = y
        y.left = z
        y.height = max(self.height(y.left), self.height(y.right)) + 1
        x.height = max(self.height(x.left), self.height(x.right)) + 1
        return x

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)
        elif key < node.key:
            node.left = self._insert(node.left, key)
        else:
            node.right = self._insert(node.right, key)

        node.height = max(self.height(node.left), self.height(node.right)) + 1

        balance = self.balance_factor(node)

        if balance > 1 and key < node.left.key:
            return self.rotate_right(node)

        if balance < -1 and key > node.right.key:
            return self.rotate_left(node)

        if balance > 1 and key > node.left.key:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)

        if balance < -1 and key < node.right.key:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)

Thuật toán Dijkstra

Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm. Thuật toán này được đặt tên theo nhà toán học Edsger W. Dijkstra và được công bố lần đầu tiên vào năm 1959.

Bước đầu tiên

Thuật toán bắt đầu bằng cách chọn một đỉnh bất kỳ và đặt khoảng cách từ đỉnh đó đến tất cả các đỉnh khác bằng vô cùng, trừ khoảng cách từ đỉnh đó đến chính nó bằng 0.

Bước thứ hai

Sau đó, thuật toán duyệt qua tất cả các đỉnh của đồ thị, cập nhật khoảng cách từ đỉnh đang xét đến các đỉnh khác. Để cập nhật khoảng cách này, thuật toán sử dụng công thức:

new_distance = distance[current] + weight(current, neighbor)

Trong đó distance[current] là khoảng cách từ đỉnh bắt đầu đến đỉnh hiện tại đang xét, weight(current, neighbor) là trọng số của cạnh nối giữa đỉnh hiện tại đang xét và đỉnh kế tiếp, và new_distance là khoảng cách mới từ đỉnh bắt đầu đến đỉnh kế tiếp.

Bước cuối cùng

Cuối cùng, thuật toán chọn đỉnh có khoảng cách nhỏ nhất và đánh dấu nó đã được xét. Sau đó, thuật toán quay lại bước thứ hai và tiếp tục duyệt đến khi tất cả các đỉnh đều được đánh dấu đã xét hoặc khoảng cách từ đỉnh bắt đầu đến tất cả các đỉnh khác đã được cập nhật.

Dưới đây là đoạn mã Python mẫu cho thuật toán Dijkstra:

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    queue = [(0, start)]

    while queue:
        current_distance, current_vertex = heapq.heappop(queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

 

Thuật toán Bellman-Ford

Thuật toán Bellman-Ford là một thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số âm hoặc không. Thuật toán này được đặt tên theo nhà toán học Richard Bellman và Lester Ford Jr. và được công bố lần đầu tiên vào năm 1958.

Các bước của thuật toán

Thuật toán Bellman-Ford bắt đầu bằng cách đặt khoảng cách từ đỉnh bắt đầu đến tất cả các đỉnh khác bằng vô cùng, trừ khoảng cách từ đỉnh bắt đầu đến chính nó bằng 0. Sau đó, thuật toán duyệt qua tất cả các cạnh của đồ thị, cập nhật khoảng cách từ đỉnh bắt đầu đến các đỉnh khác. Cập nhật này được thực hiện bằng cách sử dụng công thức:

new_distance = distance[current] + weight(current, neighbor)

Trong đó distance[current] là khoảng cách từ đỉnh bắt đầu đến đỉnh hiện tại đang xét, weight(current, neighbor) là trọng số của cạnh nối giữa đỉnh hiện tại đang xét và đỉnh kế tiếp, và new_distance là khoảng cách mới từ đỉnh bắt đầu đến đỉnh kế tiếp. Nếu khoảng cách mới này nhỏ hơn khoảng cách hiện tại, thuật toán sẽ cập nhật lại khoảng cách.

Thuật toán Bellman-Ford tiếp tục duyệt qua tất cả các cạnh của đồ thị, cập nhật khoảng cách đến khi không còn cập nhật được nữa hoặc đã cập nhật đến lần thứ N-1, với N là số lượng đỉnh của đồ thị. Nếu vẫn còn thể cập nhật được sau lần thứ N-1, tức là đồ thị có chu trình âm, điều này có nghĩa là không có đường đi ngắn nhất từ đỉnh bắt đầu đến các đỉnh khác.

Đoạn code Python mẫu

Dưới đây là đoạn mã Python mẫu cho thuật toán Bellman-Ford:

def bellman_ford(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                new_distance = distances[vertex] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance

    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distances[vertex] + weight < distances[neighbor]:
                raise ValueError("Graph contains negative weight cycle")

    return distances

 

Thuật toán Floyd-Warshall

Thuật toán Floyd-Warshall là một thuật toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số. Thuật toán này được đặt tên theo các nhà toán học Robert Floyd và Stephen Warshall, và được công bố lần đầu tiên vào năm 1962.

Các bước của thuật toán

Thuật toán Floyd-Warshall bắt đầu bằng cách khởi tạo ma trận khoảng cách ban đầu. Ma trận này có kích thước bằng số lượng đỉnh trong đồ thị, và khoảng cách ban đầu từ một đỉnh đến một đỉnh khác được lưu trong ma trận này.

Sau đó, thuật toán duyệt qua tất cả các cặp đỉnh trong đồ thị và cập nhật khoảng cách giữa chúng nếu có đường đi ngắn hơn. Cập nhật khoảng cách này được thực hiện bằng cách sử dụng công thức:

new_distance = distance[i][k] + distance[k][j]

Trong đó distance[i][k] là khoảng cách hiện tại từ đỉnh i đến đỉnh k, distance[k][j] là khoảng cách hiện tại từ đỉnh k đến đỉnh j, và new_distance là khoảng cách mới từ đỉnh i đến đỉnh j.

Đoạn code Python mẫu

Dưới đây là đoạn mã Python mẫu cho thuật toán Floyd-Warshall:

def floyd_warshall(graph):
    distance = [[float('inf') if i != j else 0 for j in range(len(graph))] for i in range(len(graph))]

    for i in range(len(graph)):
        for j in graph[i]:
            distance[i][j] = graph[i][j]

    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

    return distance
Các tham số

Thuật toán Floyd-Warshall cần một tham số duy nhất là đồ thị có trọng số. Đồ thị này có thể được biểu diễn dưới dạng một danh sách kề, trong đó mỗi cặp đỉnh được nối với nhau bởi một cạnh có trọng số tương ứng.

Hy vọng thông tin này sẽ giúp bạn hiểu rõ hơn về thuật toán Floyd-Warshall và cách sử dụng nó trong các ứng dụng thực tế.

Thuật toán Prim

Thuật toán Prim là một thuật toán tìm cây khung nhỏ nhất trong đồ thị có trọng số. Thuật toán này được đặt tên theo nhà toán học người Mỹ Robert Prim và được công bố lần đầu tiên vào năm 1957.

Các bước của thuật toán

Thuật toán Prim bắt đầu bằng cách chọn một đỉnh bất kỳ trong đồ thị làm đỉnh bắt đầu, và đưa đỉnh này vào tập các đỉnh đã xét. Sau đó, thuật toán duyệt qua tất cả các cạnh nối đỉnh đã xét với đỉnh chưa xét và chọn cạnh có trọng số nhỏ nhất để thêm đỉnh mới vào tập các đỉnh đã xét. Thuật toán tiếp tục duyệt qua các cạnh và thêm đỉnh mới cho đến khi tất cả các đỉnh trong đồ thị đều đã được đưa vào tập các đỉnh đã xét hoặc không còn cạnh nối đỉnh đã xét với đỉnh chưa xét.

Dưới đây là đoạn mã Python mẫu cho thuật toán Prim:

import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [
        (cost, start, to)
        for to, cost in graph[start].items()
    ]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((cost, frm, to))

            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst
Các tham số

Thuật toán Prim cần hai tham số sau:

Thuật toán Prim là một trong những thuật toán quan trọng trong lý thuyết đồ thị và được sử dụng rộng rãi trong các ứng dụng thực tế như hệ thống điều khiển và quản lý mạng.

Để sử dụng thuật toán Prim, bạn cần biết cách biểu diễn đồ thị và trọng số cạnh dưới dạng dữ liệu. Bạn cũng cần chọn đỉnh bắt đầu để tìm cây khung nhỏ nhất từ đó.

Thuật toán Kruskal

Thuật toán Kruskal là một thuật toán tìm cây khung nhỏ nhất trong đồ thị có trọng số. Thuật toán này được đặt tên theo nhà toán học Joseph Kruskal và được công bố lần đầu tiên vào năm 1956.

Các bước của thuật toán

Thuật toán Kruskal bắt đầu bằng cách sắp xếp tất cả các cạnh của đồ thị theo thứ tự tăng dần theo trọng số. Sau đó, thuật toán duyệt qua từng cạnh của đồ thị và thêm cạnh đó vào cây khung nếu cạnh đó không tạo thành chu trình với các cạnh đã được thêm vào cây khung trước đó. Thuật toán tiếp tục thêm cạnh cho đến khi tất cả các đỉnh trong đồ thị đều đã được đưa vào cây khung hoặc không còn cạnh để thêm vào cây khung nữa.

Dưới đây là đoạn mã Python mẫu cho thuật toán Kruskal:

def kruskal(graph):
    parent = dict()
    rank = dict()

    def make_set(vertex):
        parent[vertex] = vertex
        rank[vertex] = 0

    def find(vertex):
        if parent[vertex] != vertex:
            parent[vertex] = find(parent[vertex])
        return parent[vertex]

    def union(vertex1, vertex2):
        root1 = find(vertex1)
        root2 = find(vertex2)
        if root1 != root2:
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root1] = root2
                if rank[root1] == rank[root2]: rank[root2] += 1

    for vertex in graph['vertices']:
        make_set(vertex)

    minimum_spanning_tree = set()
    edges = list(graph['edges'])
    edges.sort()
    for edge in edges:
        weight, vertex1, vertex2 = edge
        if find(vertex1) != find(vertex2):
            union(vertex1, vertex2)
            minimum_spanning_tree.add(edge)

    return minimum_spanning_tree
Các tham số

Thuật toán Kruskal cần một tham số duy nhất là đồ thị có trọng số. Đồ thị này có thể được biểu diễn dưới dạng một danh sách các cạnh, trong đó mỗi cạnh được biểu diễn bởi một bộ ba (trọng số, đỉnh bắt đầu, đỉnh kết thúc).