Lộ trình ngẫu nhiên

Trước khi tìm hiểu về sự phức tạp của véctơ và các chuyển động vật lý, hãy cùng suy nghĩ về bản chất khi một thứ gì đó di chuyển xung quanh màn hình. Ta cùng bắt đầu với một trong những mô phỏng chuyển động đơn giản và phổ biến nhất, đó là lộ trình ngẫu nhiên (còn được gọi là bước đi ngẫu nhiên).

Giả sử bạn đang đứng giữa một thanh xà thăng bằng. Cứ sau 10 giây, bạn tung một đồng xu. Nếu tung được mặt ngửa, bạn bước lên trước một bước. Nếu tung được mặt sấp, bạn lùi về sau một bước. Khi bước khỏi thanh xà xuống sàn nhà, bạn tiếp tục thực hiện lộ trình ngẫu nhiên trong không gian hai chiều bằng cách tung đồng xu hai lần với các kết quả như bảng dưới. Toàn bộ quá trình trên được gọi là một lộ trình ngẫu nhiên. Lộ trình ngẫu nhiên là lộ trình được xác định bởi một chuỗi các bước có kết quả ngẫu nhiên.

Tung lần 1	Tung lần 2	Kết quả
Ngửa	Ngửa	Bước lên trước
Ngửa	Sấp	Bước sang phải
Sấp	Ngửa	Bước sang trái
Sấp	Sấp	Bước về sau

Đây có vẻ là một thuật toán khá đơn giản. Tuy nhiên trên thực tế, lộ trình ngẫu nhiên được sử dụng để mô hình hóa các hiện tượng xảy ra trong thế giới thực, từ chuyển động của các phân tử chất khí đến hành vi của người chơi trong sòng bạc. Hãy cùng bắt đầu nghiên cứu chủ đề này ngay bây giờ!

Đối tượng thực hiện lộ trình ngẫu nhiên (Random Walker)

Trước tiên, hãy cùng ôn tập một chút về lập trình hướng đối tượng (object-oriented programming - OOP) bằng cách tạo một đối tượng mới với tên gọi Walker. Nếu chưa bao giờ sử dụng kỹ thuật này, bạn có thể tìm hiểu thêm trong phần lập trình hướng đối tượng trên JavaScript.

Trong JavaScript, đối tượng là một kiểu dữ liệu có cả thuộc tính và chức năng đính kèm trên nguyên mẫu của nó. Chúng ta cần thiết kế đối tượng Walker sao cho vừa có thể theo dõi được dữ liệu của đối tượng (vị trí trên màn hình) vừa có thể cho đối tượng thực hiện một số hành động cụ thể (ví dụ như vẽ chính nó hoặc đi một bước).

Để tạo các thực thể Walker, chúng ta cần định nghĩa kiểu đối tượng mới Walker. Ta sẽ sử dụng kiểu đối tượng tổng quát đó như một dụng cụ cắt bánh quy và mỗi thực thể Walker mới là một chiếc bánh.

Đầu tiên, ta cần định nghĩa kiểu đối tượng Walker. Đối tượng Walker chỉ cần hai dữ liệu

-

một số biễu diễn hoành độ x và một số biểu diễn tung độ y. Chúng ta sẽ thiết lập hai dữ liệu này trong hàm khởi tạo sao cho vị trí tương ứng nằm chính giữa khung kết quả:

var Walker = function() {
    this.x = width/2;
    this.y = height/2;
};

Bên cạnh việc theo dõi tọa độ x và y, đối tượng Walker cũng sẽ có các phương thức riêng mà ta có thể gọi sau. Phương thức đầu tiên cho phép đối tượng tự hiển thị dưới dạng một chấm đen. Hãy nhớ rằng chúng ta thêm phương thức vào một đối tượng trong JavaScript bằng cách đính kèm chúng vào prototype của đối tượng.

Walker.prototype.display = function() {
    stroke(0, 0, 0);
    point(this.x, this.y);
};

Phương thức thứ hai sẽ dịch chuyển đối tượng Walker một bước. Ở ví dụ trên, chúng ta có giả thuyết về các bước ngẫu nhiên trên sàn nhà. Bây giờ, ta sẽ hiện thực hóa giả thuyết đó trên khung kết quả. Có 4 bước để lựa chọn. Bước sang phải có thể được mô phỏng bằng cách tăng x (x++), bước sang trái có thể được mô phỏng bằng cách giảm x (x--), bước lên trước có thể được mô phỏng bằng cách đi xuống một pixel (y++) và bước về sau có thể được mô phỏng bằng cách đi lên một pixel (y--). Vấn đề tiếp theo là làm sao để chọn ra một trong bốn lựa chọn này? Ở trong thế giới thực, ta có thể tung hai đồng xu. Còn trong ProcessingJS, khi muốn chọn ngẫu nhiên từ một danh sách các lựa chọn, ta có thể chọn một số ngẫu nhiên bằng cách sử dụng hàm random().

Walker.prototype.walk = function() {
    var choice = floor(random(4));
};

Dòng mã trên đây chọn một số thực dấu phẩy động ngẫu nhiên trong khoảng từ 0 đến 4 và chuyển thành số nguyên bằng cách sử dụng hàm floor(). Khi đó, các kết quả bao gồm 0, 1, 2 hoặc 3. Thực tế, số lớn nhất sẽ không bao giờ là 4,0 mà là 3,999999999 (số lượng chữ số 9 là vô hạn). Vì hàm floor() trả về số nguyên gần nhất nhỏ hơn hoặc bằng đối số nên kết quả lớn nhất sẽ là 3. Tiếp theo, ta sẽ thực hiện bước tương ứng (trái, phải, lên, xuống) tùy theo số ngẫu nhiên nhận được.

Walker.prototype.walk = function() {
    var choice = floor(random(4));
    if (choice === 0) {
        this.x++;
    } else if (choice === 1) {
        this.x--;
    } else if (choice === 2) {
        this.y++;
    } else {
        this.y--;
    } 
};

Chúng ta đã lập trình xong lớp. Tiếp theo, ta sẽ tạo một đối tượng Walker thật trong chương trình. Giả sử ta muốn mô hình hóa một lộ trình ngẫu nhiên đơn, ta sẽ khai báo và khởi tạo một biến toàn cục thuộc kiểu Walker bằng cách gọi hàm khởi tạo với toán tử mới.

var w = new Walker();

Tiếp theo, ta định nghĩa hàm draw(), yêu cầu đối tượng kiểu walker di chuyển một bước và vẽ chính nó mỗi khi được gọi:

draw = function() {
    w.walk();
    w.display();
};

Vì ta đã không gọi hàm background() bên trong hàm "draw" nên người xem có thể thấy toàn bộ các bước của lộ trình ngẫu nhiên trên khung kết quả:

Cải tiến Random Walker

Có một số cách để cải tiến random walker. Ví dụ, lựa chọn hướng đi của đối tượng walker này đang giới hạn trong 4 lựa chọn: lên, xuống, trái, phải. Tuy nhiên, bất kỳ pixel nào trong cửa sổ đều nằm cạnh 8 pixel khác và cũng hoàn toàn có thể giữ nguyên vị trí.

Để lập trình sao cho đối tượng Walker có thể di chuyển tới bất kỳ pixel lân cận nào (hoặc giữ nguyên vị trí), ta có thể chọn một số từ trong khoảng 0 đến 8 (9 lựa chọn khả thi). Tuy nhiên, một cách hiệu quả hơn đó là chọn từ 3 bước dọc theo trục x (-1, 0 hoặc 1) và ba bước khả thi dọc theo trục y.

Walker.prototype.walk = function() {
  var stepx = floor(random(3))-1;
  var stepy = floor(random(3))-1;
  this.x += stepx;
  this.y += stepy;
};

Hơn thế nữa, nếu môi trường lập trình có thể hiển thị sự khác biệt giữa "2,2" và "2,4", ta có thể sử dụng số thập phân để biểu diễn tọa độ x và y, sau đó di chuyển theo một giá trị ngẫu nhiên tùy ý trong khoảng từ -1 đến 1:

Walker.prototype.walk = function() {
  var stepx = random(-1, 1);
  var stepy = random(-1, 1);
  this.x += stepx;
  this.y += stepy;
};

Tất cả các biến thể của lộ trình ngẫu nhiên "truyền thống" đều có một điểm chung. Đó là tại bất kỳ thời điểm nào, xác suất để đối tượng Walker chọn bước theo một hướng nhất định (hoặc không di chuyển) bằng với xác suất đối tượng Walker chọn bất kỳ lựa chọn nào khác. Nói cách khác, nếu có bốn bước khả thi thì xác suất Walker thực hiện bất kỳ bước nào là 25%. Nếu có chín bước khả thi thì xác suất là 1 phần 9 (11,1%).

May mắn thay, đây cũng là cơ chế hoạt động của hàm random(). Hàm tạo số ngẫu nhiên này có kết quả được phân phối một cách "đồng đều". Chúng ta có thể kiểm tra phân phối kết quả của hàm này bằng một chương trình đếm số lần một số ngẫu nhiên được chọn và vẽ biểu đồ cột minh họa tương ứng:

Sau một vài phút chạy chương trình, chiều cao của các cột không hoàn toàn bằng nhau. Lí do là bởi, kích thước mẫu (tức là số lượng số ngẫu nhiên mà ta chọn) khá nhỏ và đôi khi sẽ có sự chênh lệch giữa các kết quả, trong đó một vài số nhất định được chọn thường xuyên hơn. Điều này sẽ được khắc phục nếu có một trình tạo số ngẫu nhiên hoạt động tốt.

Các số ngẫu nhiên mà ta có được từ hàm random() không thực sự là ngẫu nhiên. Ta có thể gọi chúng là “giả ngẫu nhiên”. Những số này là kết quả của một hàm toán học mô phỏng tính ngẫu nhiên. Hàm này sẽ tạo ra một tập hợp số cho một khoảng thời gian, tuy nhiên khoảng thời gian đó quá dài nên có thể coi đó là sự ngẫu nhiên thuần túy.

Trong phần tiếp theo, chúng ta sẽ tìm hiểu những cách khác nhau để tạo đối tượng "walker" có "xu hướng" di chuyển theo những hướng nhất định. Và trước đó, có một thử thách đang chờ đợi bạn!

Khóa học "Mô phỏng tự nhiên" này được biên soạn dựa trên cuốn "The Nature of Code" (tạm dịch: Bản chất của lập trình) của tác giả Daniel Shiffman, được sử dụng theo giấy phép Creative Commons Attribution-NonCommercial 3.0 Unported License.

Tham gia cuộc thảo luận?

Đăng nhập

Sắp xếp theo:

Chưa có bài đăng nào.

Bạn có hiểu Tiếng Anh không? Bấm vào đây để thấy thêm các thảo luận trên trang Khan Academy Tiếng Anh.