Category: Khám phá

Author: Gia Đào

Trước khi diễn giải khái niệm tính kế thừa (Inheritance) trong lập trình hướng đối tượng, chúng ta cùng đến với một vài ví dụ trong thực tế để nắm bắt sơ qua về khái niệm này. Trong cuộc sống, tính kế thừa xuất hiện ở khắp mọi nơi. Chúng ta kế thừa những đặc điểm của bố mẹ chúng ta, chẳng hạn như màu mắt, màu tóc, thậm chí là tính cách. Ngoài tự nhiên, loài khỉ đột, khỉ đầu chó, đười ươi, hay vượn má trắng… mặc dù chúng có bề ngoài khác nhau, nhưng đều được các nhà sinh vật học xếp vào bộ Linh Trưởng bởi khả năng leo trèo tuyệt vời, não bộ lớn, sử dụng chi trước linh hoạt,… Chúng đều kế thừa những đặc điểm này từ loài vượn cổ xưa, tổ tiên của chúng trong lịch sử. Dù chưa đề cập tới khái niệm tính kế thừa trong lập trình nhưng với những ví dụ trên, chúng ta có thể hình dung qua nội dung cơ bản của nó: khi một tập con sở hữu những đặc điểm sẵn có từ tập cha và phát triển những đặc điểm riêng của mình, gọi là kế thừa. Hổ là sinh vật hoạt động cá nhân, có vằn, sinh trưởng thích hợp trong môi trường rừng rậm, trong khi đó sư tử sinh hoạt theo bầy và chỉ xuất hiện ở vùng đồng cỏ với khí hậu khô. Hổ và sư tử là hai loài vật hoàn toàn khác nhau với những đặc điểm khác nhau đã tiến hóa, tuy vậy, chúng vẫn được xếp chung vào lớp họ Mèo bởi những đặc tính chung được kế thừa như săn mồi bằng cách mai phục, hoạt động mạnh về đêm, là động vật có vú ăn thịt đi bằng bốn chân… 

Trong ảnh là 1 ví dụ về Animal class, lớp Thú nói chung có các loài 4 chân như chó, mèo, và bò. 

Tính kế thừa thú vị ở chỗ một cá thể được phát triển dựa trên những gì sẵn có và tự tạo nên những đặc tính riêng của mình. Trong khoa học, tính kế thừa được áp dụng để tận dụng những phát minh đã có sẵn nhằm tiết kiệm thời gian và công sức. Chẳng hạn, tập đoàn Apple sẽ không phát triển iPhone 13 bằng cách bắt đầu từ con số 0 mà chắc chắn, họ sẽ sử dụng lại những thiết kế, chức năng cơ bản của những đời iPhone trước để phát triển những tính năng mới cho iPhone 13. Ta có thể nói, iPhone 13 ‘kế thừa’ iPhone 11 hay 12 và được thêm những tính năng như chụp ảnh ‘nét’ hơn, giao diện thân thiện hơn hay pin dùng được lâu hơn.  

Tính kế thừa trong lập trình hướng đối tượng được định nghĩa là, khi một lớp con (derived or child class) được thừa hưởng các thuộc tính (property) và phương thức (method) của lớp cha (base or parent class) mà nó kế thừa.  

Trước khi đến với cách hoạt động của tính kế thừa, chúng ta cùng tìm ôn lại hai khái niệm cơ bản trong lập trình hướng đối tượng, đó là: Lớp (Class) và Đối tượng (Object). 

Chúng ta có thể liên kết khái niệm trên thông qua một ví dụ: ‘Ngôi nhà’ được coi là một ‘đối tượng’ và khi chúng ta nhắc tới ‘Ngôi nhà’, chúng ta đều biết ‘ngôi nhà’ phải có những đặc điểm như ‘có cửa sổ’, ‘có cửa ra vào’, ‘mái che’, ‘phòng ngủ’… Những đặc điểm chung cơ bản nêu trên của một ngôi nhà mà tất cả chúng ta đều biết được gọi là ‘thuộc tính’ (Attributes). Tuy vậy, để xây được ngôi nhà, chúng ta cần có bản thiết kế. Lớp (Class), chính là bản thiết kế này, là nơi chúng ta sẽ thiết kế ngôi nhà trông ra sao, có màu gì, có bao nhiêu phòng… 

class House: 

Ở đây chúng ta thấy, sau khi có bản thiết kế ngôi nhà, nói cách khác, khi khởi tạo class House, chúng ta có 2 đặc tính là color, house_number. Sample_house là 1 đối tượng được xây dựng dựa trên bản thiết kế House, và chúng ta có thể cho chúng các đặc điểm cụ thể.  

Biến color và house_number được gọi bằng dấu ‘.’ và chúng ta lưu giá trị ‘blue’ cho color và 10 cho house_number. 

Ở bức ảnh trên, ta thấy 3 lớp, xe buýt (Bus), xe con (Car), và xe tải (Truck) đều có chung các phương thức hoạt động như fuelAmount() (kiểm tra xăng), capacity() (số người có thể chứa), applyBrakes() (có phanh). Ta có thể thấy, đây là một vài đặc điểm cơ bản chung của các loại xe được nêu trên, tuy nhiên, nếu khai báo tất cả các lớp này với các phương thức lặp đi lặp lại như vậy sẽ tốn rất nhiều thời gian và công sức, do đó, ta sẽ sử dụng tính kế thừa, bằng cách tạo 1 lớp chung, gọi là ‘Phương tiện’ (Vehicle) với các phương thức như trên, và xe buýt, xe con, và xe tải sẽ là những lớp con kế thừa từ lớp cha này: 

Trong ảnh là một ví dụ đơn giản để mô phỏng tính kế thừa. Lớp cha đại diện cho các phương tiện giao thông nói chung (Vehicle) mà trong đó, những phương thức của lớp cha bao gồm fuelAmount(), capacity(), applyBrakes(), sẽ được thừa hưởng bởi lớp con. Việc tạo ra lớp cha rồi sử dụng tính kế thừa khi tạo những lớp con giúp ta tiết kiệm rất nhiều thời gian và tránh được việc lặp lại các phương thức khi phải tạo ra nhiều lớp.  

Mô phỏng tính kế thừa bằng Python: 

# define a superclass
class super_class:
# attributes and method definition

# inheritance
class sub_class(super_class):
# attributes and method of super_class
# attributes and method of sub_class 

Super class ở đây là lớp cha và sub_class là lớp con kế thừa từ lớp cha. Ví dụ trên là cách khai báo lớp nói chung và dưới đây là ví dụ cụ thể: 

class Animal:

# attribute and method of the parent class
name = “”

def eat(self):
    print(“I can eat”)

# inherit from Animal
class Dog(Animal):

# new method in subclass
def display(self):
    # access name attribute of superclass using self
    print(“My name is “, self.name)

# create an object of the subclass
labrador = Dog()

# access superclass attribute and method 
labrador.name = “Rohu”
labrador.eat()

# call subclass method 
labrador.display() 

Ở đây ta khởi tạo lớp cha là Animal với 1 biến name và phương thức eat(). Phương thức eat khi được gọi sẽ in ra dòng “I can eat”. Dog là 1 lớp con cụ thể được tạo ra bằng việc kế thừa từ lớp cha. Để khởi tạo lớp con Dog, ta truyền lớp cha Animal vào trong 2 dấu ngoặc tròn. Lưu ý rằng, bởi lớp con Dog được kế thừa từ lớp cha và thông qua những ví dụ ở trên, ta biết rằng lớp con Dog có thể thừa hưởng những biến và phương thức của lớp cha.  

Thật vậy, phương thức display() trong lớp Dog, có thể gọi biến name trong lớp cha thông qua biến self: self.name. Nói 1 cách cụ thể, khi phương thức display() được gọi, kết quả sẽ in ra “My name is “ với biến name sở hữu bất kỳ giá trị nào. 

Cuối cùng, ta khởi tạo labrador = Dog() để có thể sử dụng lớp con Dog. Labrador chính là 1 đối tượng (Object) mà chúng ta đã đề cập tới trong bài học. Một lần nữa, ta thấy 3 dòng: 

Labrador.name = “Rohu” => Lưu trữ giá trị xâu “Rohu” vào trong biến name 

Labrador.eat() => gọi phương thức eat (sử dụng dấu ‘.’) 

Labrador.display() => gọi phương thức display (sử dụng dấu ‘.’) 

Ba dòng code trên đều cho thấy rằng, labrador là 1 đối tượng của lớp con nhưng bởi tính kế thừa, nó hoàn toàn có thể sở hữu những phương thức và biến của lớp cha và truy cập tới chúng. Khi chạy toàn bộ đoạn code trên, chúng ta có kết quả như sau: 

Output:  

I can eat
My name is Rohu 

Tác giả: Quốc Huỳnh

Python cung cấp cho người dùng nhiều công cụ hỗ trợ tính toán và vẽ đồ thị, giúp cho việc trực quan hóa dữ liệu trở nên dễ dàng hơn bao giờ hết. Trong Python, có rất nhiều thư viện và module hỗ trợ vẽ đồ thị.

Trong bài viết này, chúng ta sẽ tìm hiểu về một số công cụ vẽ đồ họa và biểu đồ trong Python.

1. Turtle:

Turtle là một thư viện vẽ hình đơn giản trong Python, được thiết kế để giúp các em học lập trình và vẽ hình ảnh đơn giản một cách dễ dàng.

Khi sử dụng Turtle, bạn có thể tạo ra những hình dạng đơn giản như hình vuông, hình tam giác, hình tròn và các hình khác. Bạn cũng có thể điều khiển con rùa (turtle) để vẽ hình theo ý muốn của mình.

Ví dụ:

Để vẽ lá cờ Việt Nam bằng Turtle, ta có thể dùng lệnh sau đây

Ta vẽ nền đỏ của cờ, bắt đầu bằng cách nâng bút lên (penup), di chuyển đến vị trí (-200, 200) (tọa độ này nằm ở góc trên bên trái của cửa sổ vẽ), đặt bút xuống (pendown), thiết lập màu đỏ và bắt đầu tô màu (begin_fill). Với mỗi vòng lặp i trong khoảng từ 0 đến 1, di chuyển về phía trước 400 đơn vị, quay sang phải 90 độ, di chuyển về phía trước 266 đơn vị và quay sang phải 90 độ nữa để hoàn thành một hình chữ nhật. Khi vẽ xong hình, kết thúc tô màu (end_fill).

Vẽ ngôi sao, bắt đầu bằng cách nâng bút lên (penup), di chuyển đến vị trí (-90, 90) (tọa độ này nằm ở giữa cửa sổ vẽ), đặt bút xuống (pendown), thiết lập màu và bắt đầu tô màu (begin_fill). Với mỗi vòng lặp i trong khoảng từ 0 đến 4, di chuyển về phía trước 180 đơn vị, quay sang phải 144 độ để tạo ra 5 góc của ngôi sao. Khi vẽ xong hình, kết thúc tô màu (end_fill).

Đây là kết quả thu được

2. Matplotlib

Matplotlib là một trong những thư viện vẽ đồ họa và biểu đồ phổ biến nhất trong Python. Thư viện này có thể được sử dụng để vẽ nhiều loại biểu đồ khác nhau, bao gồm biểu đồ đường, biểu đồ thanh, biểu đồ hộp, biểu đồ phân tán và nhiều hơn nữa. Matplotlib cho phép người dùng tùy chỉnh hoàn toàn các phần của biểu đồ, từ tiêu đề cho đến các trục và các chú thích.

Đây là một số kết quả thu được khi dùng Matplotlib để vẽ biểu đồ trong việc phân tích dữ liệu

3. Seaborn

Seaborn là một thư viện vẽ biểu đồ dựa trên Matplotlib, được thiết kế để giúp người dùng vẽ các biểu đồ phức tạp một cách dễ dàng hơn. Seaborn cho phép người dùng vẽ các biểu đồ phân tán với các đường hồi quy và các biểu đồ phân phối với các đường cong phù hợp. Thư viện này cũng có thể được sử dụng để vẽ các biểu đồ hộp và các biểu đồ đường.

Matplotlib và Seaborn là hai thư viện phổ biến trong việc trực quan hóa dữ liệu trong Python.

Dưới đây là một số khác biệt chính giữa hai thư viện này:

1. Cú pháp: Matplotlib cung cấp cú pháp đơn giản để tạo ra các biểu đồ cơ bản, trong khi Seaborn cung cấp các biểu đồ trực quan hơn và có cú pháp đơn giản hơn để tạo ra các biểu đồ phức tạp hơn.
2. Kiểu biểu đồ: Matplotlib cung cấp các biểu đồ cơ bản như biểu đồ đường, cột, hình tròn, v.v., trong khi Seaborn cung cấp các biểu đồ trực quan hơn như biểu đồ phân phối, biểu đồ tương quan, biểu đồ hộp, v.v.
3. Màu sắc: Seaborn cung cấp các màu sắc mặc định cho các biểu đồ, trong khi Matplotlib yêu cầu người dùng tự định nghĩa màu sắc.
4. Tích hợp với Pandas: Seaborn được thiết kế để tích hợp tốt với thư viện Pandas để trực quan hóa dữ liệu, trong khi Matplotlib chỉ hỗ trợ cơ bản tích hợp với Pandas.

Tóm lại, Matplotlib là một thư viện trực quan hóa dữ liệu cơ bản trong Python, trong khi Seaborn cung cấp các biểu đồ phức tạp và trực quan hơn. 

Ngoài những thư viện phổ biến đã kể trên ra thì chúng ta còn có các công cụ vẽ khác có thể được dùng trong Python như Plotly, Bokeh hay Altair, v.v mà các bạn học sinh có thể tìm hiểu thêm.

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Jack Vo

1. Stack

Stack (ngăn xếp) là kiểu dữ hoạt động theo nguyên lý Last In First Out hay LIFO (vào sau ra trước). Chúng ta có thể xem ảnh động bên dưới để hình dung rõ hơn về các hoạt động của kiểu dữ liệu này. Khối vuông màu đỏ sẽ lần lượt được đặt trồng lên nhau trong một cái cốc sau đó khối vuông ở trên cùng sẽ là cái ra khỏi chiếc cốc đầu tiên dựa theo nguyên lý vào sau ra trước hay LIFO.

2. Queue

Queue (hàng chờ) là một kiểu dữ liệu có cách hoạt động hơi khác so với Stack là sẽ dựa vào nguyên lý First In First Out hay FIFO (vào trước ra trước). Chúng ta có thể xem ảnh động ở bên dưới để hình dung rõ hơn về cách hoạt động của kiểu dữ liệu này. Số 8 là số đầu tiên vô hàng cũng như sẽ là số đầu tiên ra khỏi hàng dựa trên nguyên lý vào trước ra trước hay FIFO.

3. Ứng dụng thực tế

• Stack có thể ứng dụng vào việc làm trình duyệt tabs như khi chúng ta đã đi qua một loạt các trang webs và muốn quay lại trang đầu tiên thì chúng ta sẽ nhấn nút mũi tên quay lại thì trang trước trang cuối cùng của chúng ta sẽ được hiển thị lại trước và chúng ta sẽ cứ dùng mũi tên quay lại cho đến khi về lại trang đầu tiên.
• Queue có thể ứng dụng vào làm mấy xuất vé tự động khi mà mỗi người khách tới rút vé thì họ sẽ là người đầu tiên vô cũng là người đầu tiên ra về, tờ vé đầu tiên ra khỏi máy xuất vé cũng là tờ vé đầu tiên mà vị khách đó cầm về.

4. Cách để viết kiểu dữ liệu bằng Python

• Stack

Chúng ta sẽ tạo một class tên Stack và sẽ sử dụng list() để xây dựng lên Stack, trong Stack sẽ bao gồm các functions như peek(), pop(), is_empty(), size(), push()

class Stack:

  def __init__(self):

      self.items = list()

  def push(self, item): // thêm vào stack

      self.items.append(item)

   def pop(self): // lấy số đầu tiên ra khỏi Stack

      return self.items.pop()

   def is_empty(self): // kiểm tra xem Stack có đang rỗng

      return self.items == []

  def peek(self): // xem số trên cùng

      return self.items[len(self.items) – 1]

  def size(self): // kiểm tra xem độ lớn của Stack

      return len(self.items)

• Queue

Chúng ta sẽ tạo một class tên Queue và sẽ sử dụng list() để xây dựng lên Queue, trong Queue sẽ bao gồm các functions của như is_empty(), size(), enqueue(), dequeue()

class Queue:

  def __init__(self):

      self.items = list()

  def enqueue(self, item): // thêm vào queue

      self.items.insert(0, item)

   def dequeue(self): // lấy số đầu tiên ra khỏi Queue

      return self.items.pop()

   def is_empty(self): // kiểm tra xem Queue có đang rỗng

      return self.items == []

  def size(self): // kiểm tra xem độ lớn của Queue

      return len(self.items)

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Quang Nguyễn

Trong blog này, chúng ta sẽ cùng tìm hiểu qua hai thuật toán tìm kiếm rất phổ biến trong khoa học máy tính là DFS và BFS để giúp máy tính thực hiện nhiệm vụ tìm đường đi trong mê cung này nhé. Hai thuật toán này có sử dụng hai kiểu cấu trúc dữ liệu đã được học ở trong bài 6 của lớp CS101 đấy!!!

1. Mê cung:

Một mê cung của chúng sẽ được biểu diễn như hình dưới đây, với các tường được biểu diễn dưới ô vuông màu xám, đường đi dưới dạng các ô vuông màu vàng đất, điểm bắt đầu với biển bàn tay chỉ dẫn màu xanh lá cây, và điểm kết thúc là lá cờ màu đỏ:

Các bạn có thấy hình ảnh về mê cung có quen không nào?? Chúng ta đã được biết đến khái niệm mảng hai chiều, và mê cung có thể được biểu diễn bằng mảng hai chiều gồm các hàng và cột. Nhiệm vụ của chúng ta là phải tìm ra đường đi từ điểm bắt đầu cho đến điểm kết thúc:

• 

2. Thuật toán Depth-first search (DFS):

Đầu tiên hãy tưởng tượng rằng bạn đang đi du lịch Bà Nà Hills ở Đà Nẵng, và bạn được trải nghiệm giải mã mê cung ngoài đời thật tại Khu vườn bí ẩn. Và bạn chợt nhận ra là trong thực tế, thay vì nhìn trước được toàn bộ mê cung như các trò chơi được in trên báo, giờ đây bạn chỉ có thể nhìn được một vài vị trí xung quanh bản thân để quyết định xem hướng nào sẽ đi tiếp.

Và máy tính của chúng ta cũng vậy, trong thực tế máy tính chỉ có thể nhìn thấy đường đi xung quanh kế bên mình. 

Vậy ở tại mỗi vị trí chúng ta sẽ quyết định đường đi tiếp theo như thế nào nhỉ? Làm sao để chúng ta tránh đi lòng vòng và quay đi quay lại đường mình đã đi? Chọn bừa một hướng đi và hy vọng nó sẽ dẫn đến lối thoát hay có một chiến thuật thông minh hơn? Ở phần này chúng ta sẽ cùng tìm hiểu cách tiếp cận đầu tiên thông qua thuật toán DFS. 

Thuật toán DFS là viết tắt của Depth-First Search, có nghĩa là tìm kiếm theo chiều sâu. Khi thực hiện thuật toán này chúng ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp (stack) đã được học ở trong bài 6. Ý tưởng là chúng ta sẽ tìm theo một nhánh đến khi tìm được đường ra, nếu hết đường thì mới quay lại đến khi thấy nhánh mới.

Để hiểu rõ hơn về thuật toán này chúng ta sẽ giúp bạn Trẩu tìm đường đi từ điểm bắt đầu đến điểm kết thúc qua ví dụ đơn giản dưới đây:

Ở ví dụ này, chúng ta sẽ minh hoạ cấu trúc dữ liệu ngăn xếp bằng một chiếc hộp carton với các phần tử trong stack là các tờ giấy đánh số được bỏ vào hộp. Các bước của thuật toán DFS sẽ như sau:

• Bước 1: Đến điểm xuất phát
• Bước 2: Đánh số vị trí hiện tại (lưu ý rằng các số không được trùng nhau)
• Bước 3: Nhìn xung quanh theo thứ tự Trên – Dưới – Trái – Phải xem có đường nào chưa được đánh dấu không. Nếu có, sang bước 4. Nếu không, sang bước 5.
• Bước 4: Đi sang ô tiếp theo, ghi lại số của ô cũ vào trong tờ giấy rồi bỏ vào hộp. Quay lại bước 2.
• Bước 5: Lấy lại 1 tờ giấy trong hộp, quay lại vị trí trong tờ giấy. Quay lại bước 3.

Đầu tiên theo bước 1 và bước 2 bạn Trẩu sẽ đến điểm xuất phát và đánh số vị trí bạn đang đứng hiện tại là số 1 và hiện tại chiếc hộp vẫn đang rỗng:

Sau đó, bạn Trẩu tiếp tục thực hiện bước 3 nhìn xung quanh xem có đường nào theo thứ tự Trên – Dưới – Trái – Phải chưa được đánh dấu không, ở bước này chúng ta thấy chỉ có một đường duy nhất cho bạn Trẩu là đi sang phải:

Bạn Trẩu thực hiện bước 4 quyết định đi sang ô bên phải, đồng thời ghi lại số của ô cũ vào trong tờ giấy và bỏ vào hộp:

Sau đó, chúng ta quay lại bước 2 bằng cách đánh số vị trí hiện tại là 2. Tiếp theo thực hiện bước 3 bằng các xác định đường đi theo thứ tự Trên – Dưới – Trái – Phải và được kết quả như sau:

Ở đây bạn Trẩu của chúng ta có hai lựa chọn di chuyển sang phải hoặc di chuyển xuống dưới. Tại vì trong số 4 hướng di chuyển Trên – Dưới – Trái – Phải, hướng di chuyển Dưới được ưu tiên trước hướng di chuyển Phải nên ở bước này bạn Trẩu sẽ di chuyển xuống dưới, đồng thời ghi lại số của ô cũ là 2 và bỏ vào hộp:

Tiếp tục thực hiện các bước của thuật toán, chúng ta sẽ đến được trạng thái như sau:

Ở bước này, bạn Trẩu có hai hướng di chuyển là lên trên và sang phải, tuy nhiên vì lựa chọn Trên được ưu tiên trước lựa chọn Phải trong bước 3 của thuật toán nên bạn Trẩu tiếp tục di chuyển lên trên và thực hiện tiếp các bước của thuật toán chúng ta sẽ được:

Theo như bước 3, đến vị trí này thì chúng ta thấy xung quanh bạn Trẩu tất ở các đường đều đã được đánh dấu, vì vậy chúng ta sẽ di chuyển đến bước 5 để hướng dẫn bạn Trẩu tiếp tục di chuyển. Đầu tiên chúng ta sẽ lấy 1 tờ giấy ờ trong hộp ra, tờ giấy này có đánh số 8, vì vậy bạn Trẩu sẽ di chuyển đến vị trí được đánh dấu số 8 trên mê cung và quay lại bước 3:

Ở vị trí này chúng ta thấy tất cả các vị trí xung quanh Trẩu đều đã được đánh dấu nên chúng ta sẽ tiến đến thực hiện bước 5 đưa Trẩu quay lại về vị trí 7:

Sau khi quay lại hai vị trí cuối cùng bạn Trẩu cũng tìm được một hướng đi chưa được đánh dấu là di chuyển sang bên phải vị trí số 7:

Bạn Trẩu đi theo hướng bên phải và tiếp tục thực hiện các bước của thuật toán. Và voila, cuối cùng bạn Trẩu của chúng ta cũng đến được vị trí đích:

Vậy bây giờ làm thế nào để đi lại vị trí ban đầu nhỉ? Rất đơn giản, tất cả các thông tin về đường đi từ vị trí ban đầu đã được lưu lại trong chiếc hộp. Thứ tự các mảnh giấy từ trên xuống dưới trong chiếc hộp, bước nào đi sau cùng sẽ được thực hiện trước (Last in First out – LIFO): 12 – 11 – 10 – 7 – 6 – 5 – 4 – 3 – 2 – 1. (Lưu ý rằng các mảnh giấy ví dụ như số 8 sẽ không nằm trong hộp vì đã được loại bỏ ở các bước trước do không thuộc đường đi). 

3. Thuật toán Breadth-First-Search (BFS):

Thuật toán BFS là viết tắt của Breadth-First Search, có nghĩa là tìm kiếm theo chiều rộng. Khi thực hiện thuật toán này chúng ta sẽ sử dụng cấu trúc dữ liệu hàng đợi (queue) đã được học ở trong bài 6. Ý tưởng là chúng ta sẽ duyệt tất cả các nhánh để xem nhánh nào có lối ra thì dừng lại.

Để hiểu rõ hơn thuật toán này chúng ta sẽ cùng quay lại ví dụ của bạn Trẩu ở phần 2. Ở phần này, chúng ta sẽ minh hoạ cấu trúc dữ liệu hàng đợi là một chiếc thước kẻ với các phần tử bên trong là các mẩu giấy có đánh số được dán lên thước kẻ.

 Các bước của thuật toán BFS sẽ như sau:

• Bước 1: Đến điểm xuất phát và đánh dấu điểm xuất phát.
• Bước 2: Đánh dấu các ô xung quanh có thể đi được. (Lưu ý rằng không dùng các số trùng nhau)
• Bước 3: Ghi số của các ô xung quanh vào mẩu giấy, rồi dán chúng lên thước kẻ theo chiều từ trái qua phải.
• Bước 4: Lấy một mẩu giấy bên trái ngoài cùng ghi trên thước kẻ, đi đến ô ghi trên mẩu giấy. Quay lại bước 2. 

Đầu tiên chúng ta sẽ bắt đầu và đánh số 1 ở vị trí đầu tiên, lúc này thước kẻ vẫn trống chưa có mảnh giấy nào được dán lên:

Sau đó thực hiện bước 2 và bước 3, đánh dấu các ô xung quanh có thể đi được từ vị trí đang đứng và dán các mẩu giấy có ghi số các ô xung quanh lên trên thước kẻ:

Thực hiện bước 4, chúng ta lấy mẩu giấy bên trái ngoài cùng có ghi số 2 trên thước kẻ và bạn Trẩu di chuyển đến vị trí 2 có ghi trên mẩu giấy:

Tiếp tục quay lại thực hiện bước 2 và bước 3, ở vị trí hiện tại bạn Trẩu có hai lựa chọn ở xung quanh có thể đi được, đánh số các ô đó tương ứng với số 3 và 4 và dán các mẩu giấy lên trên thước kẻ:

Thực hiện bước 4 chúng ta lấy ra mẩu giấy bên trái ngoài cùng của thước kẻ là mẩu giấy có chứa số 3 và di chuyển bạn Trẩu đến vị trí số 3:

Quay lại thực hiện bước 2 và bước 3, bạn Trẩu có một lựa chọn bên phải có thể đi được, đánh số vị trí này là 5 và dán mẩu giấy lên trên thước kẻ:

Thực hiện bước 4 chúng ta lấy ra mẩu giấy bên trái ngoài cùng của thước kẻ là mẩu giấy có chứa số 4 và di chuyển bạn Trẩu đến vị trí số 4:

Tiếp tục thực hiện các bước của thuật toán và tada, cuối cùng bạn Trẩu sẽ đến được vị trí đích với các số được đánh dấu trên mê cung như sau:

Để đi lại về vị trí ban đầu, bạn Trẩu của chúng ta chỉ cần đi ngược lại theo các ô có số nhỏ hơn là được (nếu có từ 2 ô số nhỏ hơn, chọn ô có số nhỏ nhất): 13 – 12 – 11 – 9 – 7 – 5 – 3 – 2 – 1. Mảnh giấy ở bên trái trên thước kẻ sẽ được thực hiện trước trong queue (First In First Out – FIFO).

4. So sánh DFS và BFS:

Wow, như vậy là chúng ta đã giúp bạn Trẩu tìm đường di chuyển ra khỏi mê cung bằng hai thuật toán DFS và BFS, thật là ảo diệu phải không các bạn? Để kết thúc blog này, chúng ta sẽ cùng điểm qua một vài sự khác biệt giữa hai thuật toán này nhé:

DFS	BFS
Tìm theo một nhánh đến khi gặp đường cụt hoặc đích Dùng hộp giấy (ngăn xếp) Cả con người và máy tính có thể thực hiện Đường đi tìm được có thể không phải là ngắn nhất	Tìm cùng lúc nhiều nhánh Dùng thước kẻ (hàng đợi) Chỉ áp dụng hợp lý với máy tính Đường đi tìm được luôn là đường đi ngắn nhất

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation