Mẹo nhỏ: Để tìm kiếm chính xác các bài viết của Vuihecungchocopie.vn, hãy search trên Google với cú pháp: "Từ khóa" + "vuihecungchocopie". (Ví dụ: công thức giải rubik 3x3 vuihecungchocopie). Tìm kiếm ngay
58 lượt xem

Các Thuật Toán Rubik – Bí Kíp Giải Rubik Cực Chuẩn Chỉ Trong Nháy Mắt

Bản thân đang say mê tốc độ (giải nhiều câu đố hóc búa càng nhanh càng tốt), tôi luôn bị cuốn hút với Khối Rubik 3x3x3 và cách người ta có thể giảm nó từ bất kỳ trong số 43 nghìn tỷ hoán vị lộn xộn xuống trạng thái giải đơn lẻ của nó. Trong khi con người đã phát triển các thuật toán trực quan khác nhau cho các mục đích tăng tốc, với một số ví dụ là CFOP và Roux. Tuy nhiên, các phương pháp có thể giải được của con người thường mang lại các giải pháp khác xa so với tối ưu, vì vậy nhiều thuật toán có thể giải được bằng máy đã được phát triển với mục tiêu tạo ra các giải pháp tối ưu hoặc gần tối ưu. Trong phần 1 của loạt bài nhỏ này, tôi sẽ chia sẻ hai thuật toán có thể giải quyết bằng máy và cách chúng hoạt động, đồng thời thảo luận về những cải tiến có thể có đối với các ứng dụng trong thế giới thực cho các thuật toán có vẻ thích hợp này trong việc điều khiển cánh tay robot. Trong phần 2, mình sẽ xem xét quá trình xây dựng robot giải khối Rubik từ máy tính Raspberry Pi và LEGO Mindstorms NXT.

Đang xem: Thuật toán rubik

Chính xác thì giải pháp tối ưu cho Khối Rubik 3x3x3 nghĩa là gì?

Nếu chúng ta coi một nước đi là bất kỳ lượt đi nào của bất kỳ mặt nào của Khối Rubik, thì số lượng nước đi tối thiểu cần thiết để giải bất kỳ hoán vị nào của Khối Rubik sẽ luôn nhỏ hơn hoặc bằng 20. Điều này đã được chứng minh bằng cách sử dụng một số lượng lớn sức mạnh tính toán , với 20 hiện được gọi là “Số của Chúa”. Theo mục đích của bài viết này, mức độ tối ưu của một giải pháp sẽ được đo bằng sự khác biệt giữa độ dài của nó và Số của Chúa.

Kí hiệu khối Rubik

Để thảo luận chi tiết về các thuật toán, trước tiên chúng ta phải xác định ký hiệu tiêu chuẩn của Khối Rubik 3x3x3 mà từ đó chúng ta có thể xác định các nhóm. Trong tốc độ quay, ký hiệu được sử dụng phổ biến nhất sử dụng các chữ cái R, L, U, D, F, B để mô tả các mặt phải, trái, trên, dưới, trước và sau của khối lập phương. Bản thân các chữ cái mô tả sự quay theo chiều kim đồng hồ, trong khi dấu nháy đơn theo sau chữ cái (chúng tôi gọi là số nguyên tố) mô tả sự quay ngược chiều kim đồng hồ. Cầm khối lập phương có mặt xanh về phía bộ giải và mặt vàng hướng lên, các lượt được mô tả như sau:

*

Các bước di chuyển khác nhau trên khối Rubik

Các thuật toán phổ biến – Tìm kiếm sâu lặp lại A *

Khối Rubik có thể được mô hình hóa như một bài toán đồ thị trong đó các nút là một tập hợp của tất cả các cấu hình có thể có và các cạnh nằm giữa các cấu hình cách xa nhau. Sau đó, chúng ta có thể sử dụng thuật toán tìm kiếm đường dẫn và duyệt đồ thị để tìm đường đi ngắn nhất từ ​​nút đại diện cho trạng thái hiện tại của khối lập phương (nút nguồn) đến nút đại diện cho trạng thái đã giải quyết của nó (nút mục tiêu). Nhưng chúng ta nên sử dụng thuật toán duyệt đồ thị nào?

XEM THÊM:  Hướng dẫn đổi giao diện tiếng Việt trên Discord

Đối với Khối lập phương Rubik, trước tiên bạn có thể xem xét tìm kiếm đầu tiên theo chiều rộng (BFS) vì nó có thể được sử dụng để tìm đường đi ngắn nhất từ ​​nút nguồn đến nút mục tiêu, vì chúng ta có thể đạt được mục tiêu với số cạnh tối thiểu từ nguồn. Tuy nhiên, việc sử dụng BFS trở nên kém khả thi hơn nếu bạn xem xét số lượng nút trong biểu đồ (gần 43 tạ triệu) và số lượng bộ nhớ mà BFS yêu cầu.

Độ sâu lặp lại A * (IDA *) có lợi thế hơn BFS vì nó là thuật toán tìm kiếm độ sâu đầu tiên, do đó sử dụng ít bộ nhớ hơn, trong khi vẫn tối ưu. IDA * cũng sử dụng hàm chi phí nhiều thông tin hơn bằng cách sử dụng ước tính kinh nghiệm theo từng vấn đề cụ thể về chi phí để đi từ nguồn đến mục tiêu. Đối với vấn đề này, một hàm heuristic giới hạn thấp hơn được sử dụng dựa trên các bảng tra cứu dựa trên bộ nhớ lớn, lưu trữ số lượng chính xác các bước di chuyển cần thiết để giải các mục tiêu con khác nhau của bài toán, trong trường hợp này là các tập con của cấu hình khối.

Các thuật toán phổ biến – Thuật toán của Thistlethwaite

Thuật toán của Thistlethwaite do ông Morwen Thistlethwaite, một nhà lý thuyết và giáo sư toán học nghĩ ra. Khối lập phương ở trạng thái xáo trộn của nó có thể được biểu diễn như một phần tử của một nhóm chứa tất cả các trạng thái khối có thể giải được bằng các chuyển động L, R, F, B, U, D. Chúng tôi gọi nhóm này là 0, hoặc G0. Chúng tôi muốn tiếp tục giảm trạng thái khối lập phương thành các nhóm đơn giản hơn có thể giải được bằng một tập con nhỏ hơn của các nước đi có thể có sẵn, cho đến khi tập hợp con của các nước đi có thể được giảm xuống thành một tập trống, nghĩa là khối lập phương được giải. Từ nhóm 0, chúng ta biến khối lập phương thành một vị trí có thể giải quyết được bằng cách sử dụng các bước di chuyển , G1. Sau đó, nhóm được giảm hai lần thành các nhóm con thích hợp cho đến khi nó có thể được giải quyết chỉ bằng một nửa lượt, G3. Giải quyết từ vị trí này là tầm thường.

XEM THÊM:  Rubik 4X4 Và Cách Giải Rubik 4X4 Xịn, Hướng Dẫn Cách Giải Rubik 4X4 Cơ Bản

Để giảm trạng thái hình lập phương thành các nhóm khác nhau, các bảng tra cứu được sử dụng ở mỗi giai đoạn, mỗi bảng hiển thị một giải pháp cho từng phần tử trong không gian coset thương số. Bảng dưới đây cho thấy số vị trí có thể có trong mỗi nhóm và thứ tự của mỗi không gian coset.

*

Tuy nhiên, thuật toán này không tối ưu vì không có gì đảm bảo rằng một phần tử đi đường ngắn nhất từ ​​một nhóm đến nhóm con thích hợp của nó. Như vậy, thuật toán của Thistlethwaite mang lại độ dài giải pháp trung bình là 52.

Xem thêm: Bảng Kí Tự Alt 2021 ¤Ï¸Â¤Ï¸Â¤Ï¸ Full Facebook, Game, Word

Đề xuất cải tiến

Xem xét số lượng nhóm trong thuật toán của Thistlethwaite. Chúng ta có thể xem xét việc giảm s
ố lượng nhóm bằng cách đi từ G0 đến G2, sau đó từ G2 đến G4, bỏ qua việc giảm xuống các nhóm G1 và G3. Điều này có thể đạt được bằng cách sử dụng thuật toán tìm kiếm IDA * đã nói ở trên, trong đó chúng tôi có thể lập mô hình giảm cả G0 xuống G2 và G2 thành G4 dưới dạng các bài toán đồ thị với tập hợp các phép suy đoán của riêng chúng. Điều này vừa làm giảm số lượng nhóm được xem xét trong thuật toán của Thistlethwaite vừa giảm độ phức tạp của hàm heuristic và chi phí trong một thuật toán tìm kiếm IDA * hoàn chỉnh, đạt được phiên bản hiệu quả hơn của thuật toán Thistlethwaite trong khi vẫn dễ triển khai hơn nhiều so với tìm kiếm IDA * hoàn chỉnh .

Tuy nhiên, có một cảnh báo đối với sự cải tiến này: một thuật toán như vậy chỉ có thể mang lại mức tối ưu cục bộ. Nói cách khác, thuật toán chỉ tối ưu giữa các nhóm khác nhau, và có thể không tối ưu hoàn toàn từ G0 đến G4. Mặc dù vậy, chỉ có hai tập giải pháp để xem xét đường đi ngắn nhất, do đó, giải pháp tổng thể là gần như tối ưu về mặt xác suất.

Các ứng dụng trong thế giới thực – Cánh tay robot

Cải tiến được đề xuất của tôi sử dụng cả lý thuyết đồ thị và nhóm để mô hình hóa một vấn đề có thể được mô tả trong cả hai lĩnh vực và những vấn đề như vậy không chỉ giới hạn trong những câu đố hóc búa. Một ví dụ trong thế giới thực mà tôi minh họa ở đây là điều khiển một cánh tay robot. Để hình dung các bài toán có chiều cao hơn, trước tiên chúng ta có thể xem xét một cánh tay có 2 bậc tự do (DOF).

*

Cánh tay với 2 DOF

Chúng ta có thể xây dựng lưới chiếm dụng 2 chiều đại diện cho các trạng thái có thể đạt được bằng đầu, trong đó kích thước đầu tiên là θ1 và kích thước thứ hai là θ2, cả hai đều được tùy ý theo từng bước 1 độ. Nhìn vào cánh tay, chúng ta có thể thấy rằng θ2 180 °, do đó θ2 ≥ 180 ° đối với tất cả các giá trị của θ1 không thể đạt được và được biểu diễn dưới dạng vùng bóng mờ, hoặc chướng ngại vật, trên lưới. Khi end effector di chuyển từ trạng thái này sang trạng thái khác, chúng ta có thể mô tả nó như một vấn đề mà mẹo cần tìm ra con đường tối ưu từ trạng thái hiện tại đến mục tiêu. Bằng cách sử dụng lưới chiếm dụng, chúng tôi có thể chỉ định góc bắt đầu và góc mục tiêu của mỗi khớp và tìm đường đi tối ưu giữa hai điểm, sau đó mô tả đường đi tối ưu mà bộ tạo hiệu ứng cuối nên đi.

XEM THÊM:  Tổng Hợp Các Kí Hiệu Rubik 3X3 Và Các Ký Hiệu, Tổng Hợp Các Kí Hiệu Cần Nhớ Khi Chơi Rubik

Điều này có thể được mô hình hóa như một bài toán trong Lý thuyết Nhóm, trong đó G0 có thể được định nghĩa là tất cả các trạng thái có thể giải được bằng và chúng ta có thể giảm điều này hai lần thành các nhóm con thích hợp G1 = và nhóm rỗng G2. Chúng ta cũng có thể sử dụng Lý thuyết Đồ thị để mô hình hóa vấn đề này, vì lưới có thể được xem như một đồ thị với các ô liền kề được nối bằng các cạnh. Sử dụng thông tin chi tiết được áp dụng trong thuật toán cải tiến, chúng tôi có thể giải quyết vấn đề này bằng cách sử dụng thuật toán tìm kiếm theo chiều sâu như IDA * Tìm kiếm để giảm lặp đi lặp lại nhóm của trạng thái hiện tại thành nhóm con thích hợp tiếp theo thay vì thực hiện tìm kiếm hoàn chỉnh, điều này làm giảm độ phức tạp của heuristic trong khi vẫn tìm ra một giải pháp gần với giải pháp tối ưu.

Điều này có thể được ngoại suy cho các bài toán về chiều cao hơn, vì hầu hết các cánh tay robot có 6 DOF. Ở các thứ nguyên cao hơn, chúng ta chỉ cần xem xét sự gia tăng số lượng giảm nhóm liên quan đến giải pháp, vì thuật toán tìm kiếm theo chiều sâu ở mỗi bước chỉ giảm số thứ nguyên ở xa giải pháp đi 1. Điều này dẫn đến tính toán kinh nghiệm xa ít phức tạp hơn so với một thuật toán được xây dựng cho thuật toán tìm kiếm theo 6 chiều, giúp dễ dàng triển khai hơn trong các ứng dụng công nghiệp quy mô lớn.

Xem thêm: Gà Thịt Gà Tiếng Anh Là Gì Trong Tiếng Anh? Từ Vựng Tiếng Anh Về Các Loại Thịt Cơ Bản

Nếu bạn quan tâm đến các dự án khác mà tôi đã thực hiện hoặc muốn liên hệ với tôi để làm bất cứ điều gì, đây là tài khoản Github và LinkedIn của tôi .

Công khai: VUIHECUNGCHOCOPIE là trang web Tổng hợp hình ảnh - thủ thuật hay, trước kia thuộc Chocopie Vietnam. Mời thính giả đón xem.

Chúng tôi trân trọng cảm ơn quý độc giả luôn ủng hộ và tin tưởng chúng tôi!

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *