Giới thiệu

Xin chào các bạn, trong cái xã hội ngày nay thì việc con người giao tiếp với con người không còn khó khăn như ngày xưa, thời mà công nghệ còn chưa phát triển. Bởi vậy mà hầu hết chúng ta đều có rất nhiều các mối quan hệ, bạn bè... cá nhân mình nghĩ thì điều này là tốt. Nhưng, việc có nhiều các mối quan hệ, hoặc có nhiều người quen, bạn bè quá thì khả năng cao sẽ dẫn tới sự việc là không thể nào chia sẻ, bao quát và liên lạc thường xuyên với nhau được. Có những người bạn thì suốt ngày gặp mặt, gặp nhau nhiều tới nỗi nhìn mà phát ớn(ví von vậy thôi ). Trong khi đó cũng có những người bạn thì thi thoảng gặp gần, hoặc 1 tuần, 1 tháng hoặc thậm chí cả năm mới gặp nhau một lần tùy hoàn cảnh, hay người ta còn gọi là tùy duyên đấy.

Ô thế việc này thì liên quan gì tới cái tiêu đề là "để công nghệ chọn gấu". À nó là như thế này. Công nghệ càng phát triển, với con gái: những ứng dụng như là 360 độ, phấn son, thẩm mỹ ngày càng tinh vi, haha. Với vài dòng chat chít, gọi thoại hoặc cafe buổi chiều hay buổi tối thì cũng không thể nào mà đánh giá được "phần nào" người đó như thế nào. Theo mình chọn gấu là một việc quan trọng, chọn gấu phù hợp sẽ tiết kiệm cho mình khá nhiều thời gian cũng như những lợi ích về sau này. Việc lựa chọn này không dành cho những con người ba hoa, trăng hoa hay lăng nhăng hoặc sở khanh nhé. hihi.

Ah, tới đây chắc các bạn lại vẫn hỏi tiếp, thế thì lan quyên gì tới việc chấm điểm chọn gấu, lan quyên gì tới pattern giới thiệu ngày hôm nay. Xin lỗi về màn chào hỏi hơi dài dòng, luyên thuyên của mình. Bài toán đặt ra của chúng ta là như thế này:

Bài toán chọn gấu

Bài toán chọn gấu của một người đang chưa có gấu(tạm gọi tên là ST). ST là một người có quyền lực, mối quan hệ bạn bè cũng như quen biết rất rộng, hiện anh đang là chủ chuỗi hơn 20 quán ăn tối khắp Hà Nội, anh muốn chọn một người làm gấu mà anh ấy vừa ưng ý, "đặc biệt" lại hay tới quán ăn của anh ăn tối. Đếm sơ qua số người quen mà ST ưng ý và có thể chọn làm gấu đã là hơn trăm người rồi(lấy tạm 150 người). Nhưng mà ST thấy con số này thật sự là đông quá trời, biết chọn ai bây giờ. Chợt nhận ra ST có một anh bạn thân làm lập trình viên(là tôi =)) kaka ), ST gọi điện cho tôi. ST muốn tôi bày xem có cách nào để chọn được một người tốt nhất trong số tất cả những người mà mình đã ưng kia không. Sau một lúc suy nghĩ tôi bày cho ST một cách vừa không tốn kém thời gian, lại vừa chọn được người ưng ý. Lúc đó tôi nói với ST như thế này: "Nếu không vội vàng quá thì cậu có thể làm theo cách này trong một năm. Hiện giờ cậu có danh sách 150 người kia đúng không? Cậu hãy đặt mức điểm yêu thích cho từng người ban đầu là ngang bằng nhau(một năm 365 ngày - 365 điểm). Trong những người này một năm mà không tới ăn ở của hàng của cậu lần nào -> loại luôn. Tới ăn 1 lần +1 điểm. Khi tới ăn nhân viên phát hiện ra tật xấu -1 điểm. Thực hiện nó sau một năm và hãy chọn người có số điểm cao nhứt". ST bảo: "Tớ đang công tác bên Lào, tớ chưa hình dung ra được, cậu mô phỏng rồi gửi qua tớ xem trên điện thoại được không?"

Đơn giản hóa vị trí, không gian các địa điểm

Để đơn giản nhất cho công việc mô phỏng cũng như tính toán, quy chiếu vùng chứa tất cả các quán ăn trên vào một hệ tọa độ 2D hoặc 3D(trong ví dụ này chúng ta sẽ đơn giản hóa vùng tính toán với hệ tọa độ 3D như hình dưới, thuận tiện cho việc mô phỏng các chuyển động).

Hình minh họa sưu tầm từ internet Như vậy, vị trí các quán ăn sẽ được đặt cố định tại các vị trí trên tọa độ không gian trên. Danh sách hơn 100 người kia sẽ di chuyển random trên tọa độ không gian. Việc xác định khi nào những người kia là tới quán sẽ tạm xác định bằng việc tính khoảng cách từ quán tới người đó nhỏ hơn một khoảng nào đó.

Xác định một người vào quán

Việc xác định một người trong danh sách nhóm người trên là vào quán hay chưa thì theo cách thông thường nhất sẽ sử dụng đoạn mã giả gần gần như sau:

**for** danh sách tất cả các quán
    **for** danh sách tất cả hơn 100 người
        **if** khoảng cách quán thứ i tới người thứ j < minDistance
             +1 điểm
        **end_if**        
    **end_for**
**end_for**

Thực thi việc kiểm tra trên sẽ phải thực hiện liên tục bởi vì trong một ngày có thể có người vào liên tục. Như vậy thì ở đây lại có một vấn đề đặt ra rằng: Với số lượng số quán ít, khoảng vài quán và vài người, việc thực thi đoạn mã giả trên là không thành vấn đề gì. Nhưng ở đây, chúng ta có tới tầm 20 quán ăn và cũng có tới khoảng 150 người. Bạn cứ tưởng tượng, chúng ta check liên tục, mỗi lần check chúng ta phải duyệt quán đầu tiên sau đó duyệt tất cả 150 người xem có vào quán không. Rồi lại duyệt quán thứ 2, sau đó duyệt lại 150 người còn lại xem có vào quán hay không. Cứ như thế tới quán thứ 20 chúng ta cũng vẫn phải check lại đủ 150 người. Hoặc nếu nghĩ với một bài toán có phạm vi về chất rộng hơn con số 150 và 20 rất nhiều thì sao? Đây sẽ là một vấn đề rất lớn về performance đặt ra. Mình muốn nhấn mạnh đoạn này. Có thể bạn đã hiểu luôn, nếu chưa hiểu, tiếp tục và tiếp tục bạn sẽ hiểu.

Space Position pattern

Thật ra nhiều lúc có thể các bạn không để ý, những vấn đề lớn, phức tạp nếu bằng cách nào đó đơn giản hóa nó từ cái to nhất tới cái nhỏ nhất, từ cái dễ đơn giản hóa nhất tới cái khó đơn giản hóa hơn thì mọi việc lại trở nên đơn giản hơn bao giờ hết. Và mình thấy nhiều thứ phức tạp, phải tính toán tới vị trí hay các kiểu đo lường, nếu có thể cứ quẳng hết vào hệ tọa độ nào đó là nó lại trở nên đơn giản luôn . Ở đây ta lại tiếp tục đơn giản hóa các vị trí của các đối tượng cần xét cũng như các quán ăn bằng việc map chúng tới từng ô một trong không gian.

Vẽ PTS thì sẽ đẹp hơn nhưng mà mất time lắm, nên tôi tạm vẽ ra exel và paint để minh họa. Các bạn để ý nhé: Sau khi map các đối tượng tới từng các ô trong trong hệ tọa độ thì tưởng tượng nó sẽ như thế đấy. Ở ô D3 sẽ là một quán ăn minh họa, ô C3 là một đối tượng đang đi đâu qua quán ăn đó nhưng không vào quán chẳng hạn. ô D2 sẽ có 2 đối tượng. Đối tượng ở vạch của E2 và F2 kia sẽ được làm tròn là ở E2, tùy trường hợp. Ồ =)) vậy là vấn đề của chúng ta đã được giải quyết rồi. Tới đây chắc hầu hết các bạn đều đã tưởng tượng ra. Nó quá đơn giản phải không. Việc bây giờ của chúng ta chỉ là duyệt qua 20 quán ăn và kiểm tra các đối tượng có trong ô chứa quán ăn kia là xong. Không cần thiết phải kiểm tra các đối tượng không có trong ô chứa quán ăn đó.

Tới đây đoạn mã giả của chúng ta sẽ là:

**for** danh sách tất cả các quán
   ** if** người trong ô của quán thứ i có khoảng cách thỏa mãn
        +1 điểm
    **end_if**
**end_for**

Cuối cùng sau một khoảng thời gian như ví dụ trên là 1 năm. Chúng ta có thể loại được các đối tượng:

• Đã chống lầy.
• Chưa 1 lần tới quán ăn.
• Tật xấu bị âm =)) Còn lại ưu tiên đối tượng không bị trừ điểm tật xấu và tới quán ăn nhiều nhất.

Đây là link githup source https://github.com/daminhtung/PositionPattern một ví dụ mà tôi viết. Thật ra nó có thể áp dụng được cho mọi ngôn ngữ, nhưng ở ví dụ này tôi viết trên Unity 3D cho nó thuật lợi trong việc quy chiếu về tọa độ không gian cũng như chuyển động của đối tượng. Các quán ăn sẽ được thay thế bởi nhân viên ở quán để coi như xác nhận cộng điểm cho đối tượng. Các bạn có thể tham khảo thêm.

Lời kết

Trên đây chỉ là một ví dụ để minh họa cho pattern mà mình đưa vào cho nó dễ hình dung, sinh động và gần gũi thôi chứ không có ý gì, các bạn cũng không nên đặt nặng quá về vào ví dụ mà hãy tập trung vào những phần mình đã nhấn mạnh. Nó sẽ có ích trong khá là nhiều các dự án, ví dụ như các dự án có liên quan tới map, tìm địa điểm trên map, chạy navigating. Thường những dự án kiểu này chúng ta sẽ phải lựa chọn phân chia Position các địa điểm thành từng nhóm tương ứng với từng ô chứa các quán ăn ở trên và duyệt tìm Point trong nó chứ không nên duyệt tất cả các point có trên cả vùng map lớn. Một ví dụ như việc tìm kiếm quán cafe lưu động ở gần bạn nhất trong danh sách tất cả các quán cafe lưu động ở Hà Nội chẳng hạn. Hoặc tìm kiếm một chiếc Grab taxi gần mình nhất trong tổng số hàng mấy trăm chiếc grabtaxi ở Hà Nội chẳng hạn...ta cũng cần phân chia vị trí của chúng thành từng các vùng khác nhau. Một lĩnh vực khác cũng thường xuyên phải áp dụng nó đó là game. Cái này thì hầu như người nào làm game cũng nhận ra và động tới nó gần như là hầu hết các dự án, bởi sao ạ? Bởi vì trong game chúng ta thường xuyên phải quy đổi về các hệ tọa độ, tính toán các vị trí character..., đặc biệt là trong các game rất rất hay sảy ra tương tác giữa player và các static object cũng như các dynamic object. Và chắc chắn là nó sẽ còn hữu ích trong rất rất nhiều các lĩnh vực khác nữa đấy.

Cảm ơn các bạn đã theo dõi.