Haizz, Lâu rồi mình không viết tâm sự chia sẻ những tâm tư và dự định của mình nhỉ ? Hôm nay sực nhớ ra nên ngồi rảnh viết. (Đúng là rảnh thật nhỉ 12h30p rồi mà vẫn chưa ngủ) Chắc là tại khi chiều ngủ nhiều quá. Từ khi chiều đến giờ chẳng học được một thứ gì cho ra hồn cả. Khi nào cũng bảo là bản thân phải cố gắng lên. Cố gắng học để sau này có cuộc sống ổn định và lo cho gia đình.... Một đống dự định ở trong đầu. Nhưng có khi nào làm được đâu. Từ khi vào học đến giờ có buổi nào là mình học tử tế cả. Cứ một tí là bắt đầu lướt facebook, rồi lại lên youtube ngồi xem dăm ba cái thứ vớ vẩn làm mất hết cả thời gian. Mới chiều tối hôm qua, tức chủ nhật, ngồi trên xe buýt ngắm nhìn qua ô cửa sổ cảm thấy đời của mình thật vô cảm, tuy có nhiều thứ để phấn đấu nhưng chỉ là nói mà thôi. Chẳng có khi nào tôi có thể thực hiện được. Cảm giác thất vọng bản thân mình rất nhiều. Mới thấm thoát đó thôi nhưng giờ bản thân tôi đã sắp gần thi HSG tỉnh rồi mà trong khi bản thân chưa học được một thứ gì cả. Năm nay tôi thi cả toán và tin. 1 môn ôn chưa kịp mà bản thân đã "đú" theo hai môn. Bản thân học chuyên toán nhưng tôi lại có một tình yêu mãnh liệt đối với môn tin hơn. Không biết tại vì sao nhưng tôi rất yêu nó ! Yêu nó đến nỗi nếu như được bỏ môn toán thì tôi sẵn sàng chạy đến với môn tin luôn vậy. Tôi ước mơ rằng mình sẽ được thi IOI luôn. :D Cảm giác hãnh diện trước bao người. Sướng vcl..... Ước mơ của tôi thật xa vời khi những cái bài code đáng lẽ tôi có thể làm được từ lâu nhưng tôi đã phung phí thời gian rất nhiều. Nếu đến lúc chọn đội dự tuyển thì không biết có kịp ko? Bởi vì tôi cảm nhận thấy vào đội tuyển tin HSG Quốc gia có phần hơi dễ nhưng khi vào được đội tuyển chưa chắc mình đã đậu bởi vì trường ngoài giỏi hơn rất nhiều và tôi cảm thấy thành tích môn chuyên trường mình còn rất hạn chế, tỉ lệ đậu cũng thấp không phải 100% như môn toán vậy!
Và một phần tôi cảm thấy cô dạy tin tôi không giỏi như tôi tưởng tượng ban đầu. Có lẽ đó có thể là ý kiến cá nhân của tôi chăng! Nhưng cô đã bỏ dỡ một đống thời gian đến gần nửa tiết để kể những câu chuyện không đâu. Tôi cảm thấy ghét điều đó. Ở trong trường có thầy dạy tin mà tôi rất thích. Tôi cũng muốn được như thầy. Mỗi khi được thầy dạy tôi cảm thấy rất vui và cảm giác càng thích môn tin. Tuy nhiên mỗi lần học với thầy tôi cảm giác mình lo lắng đến ghê sợ. Cảm giác như kiểu học với cô tôi không lo lắng bởi mấy bài cô ra tuy dễ hay khó thì cô tôi đều "không giải được". Còn với thầy thầy luôn có những thuật toán rất hay và hấp dẫn. Cô tôi thường hay kể tôi đối với mấy thầy cô trong tổ tin khác nên cảm thấy bản thân mang trên mình một gánh nặng rất lớn. Cảm giác khi mình không thể thực hiện tốt một bài toán nào đó khi học với thầy tôi cảm thấy thất vọng về bản thân mình. Tôi muốn thân thiết với thầy hơn nhưng có lẽ khoảng cách là hơi xa. Có lẽ khi tôi vô đội dự tuyển thì khoảng cách đó có thể rút ngắn rất nhiều. Thôi có lẽ từng này là đủ. Một tháng tuy không phải là dài nhưng ngần ấy cũng đủ để tôi tạo nên một kì tích nào đó của bản thân cho tôi. Một tháng để tôi có thể thay đổi chính mình hay không? Hay là kì thi tỉnh sắp tới sẽ là một vấp ngã lớn trong cuộc đời tôi để tôi có thể vững bước hơn hay không thì có lẽ đến một tháng sau điều đó bản thân tôi mới biết. Tôi trông cậy vào kì thi tỉnh sắp tới. Tôi muốn mình giải full hết điểm tất nhiên là giành chức thủ khoa :v để tôi có thể chứng tỏ với thầy rằng mình có thể làm được đến đâu làm được đến mức nào. Để việc tôi ai trong tổ tin cũng biết không phải là những tin đồn nhảm nhí từ cô tôi. Tôi muốn chứng minh bản thân mình. Tôi muốn chinh phục một gian nan thử thách. Vì tuổi trẻ của chúng ta chỉ có một nên tôi không muốn bỏ qua cáu giai đoạn tuổi trẻ đầy mơ mộng này. Tôi muốn tuổi trẻ của tôi là những kỉ niệm đẹp và những phấn đấu của bản thân tôi. Thôi đây không phải là lúc mình vui chơi nữa mà hãy tập trung tối đa vào việc học. Tôi có thể làm việc đó. Tôi tin tưởng vào bản thân. Tin tưởng vào đôi tay và cơ thể , bộ não này có thể làm được một điều gì đó giúp ích cho đời. Để sự hiện diện của tôi không phải là một cơn gió nào đó thoảng qua mà nó có đậm lại một mùi hương nào đó khó phai. Đến đời sau vẫn còn ngậm ngùi mùi hương đó! CỐ LÊN TÔI ƠI!
12. 54' Ngày 19/2/2019
Chỉ còn 31 ngày còn lại.........
To be coded like a sharker!
Thứ Hai, 18 tháng 2, 2019
Chủ Nhật, 27 tháng 1, 2019
Giới thiệu thuật toán tìm đường đi ngắn nhất trong mê cung
Link bài viết gốc: http://arduino.vn/bai-viet/5553-gioi-thieu-thuat-toan-tim-duong-di-ngan-nhat-trong-me-cung
Hôm nay mình sẽ giới thiệu cho các bạn một cách để giúp chiếc xe dò đường trong mê cung của bạn trở nên "thông minh" hơn bằng cách tìm ra được đường đi ngắn nhất sau khi thoát khỏi mê cung ở lần chạy đầu tiên.
1. Mở đầu
Thông thường để giúp xe dò được đường trong mê cung, ta có nhiều thuật toán khác khau. Phổ biến và đơn giản nhất có lẽ là thuật toán tìm đường ngẫu nhiên và thuật toán bám tường. Với thuật toán tìm đường ngẫu nhiên, xe bạn sẽ mò mẫm trong mê cung theo kiểu "hên xui", may mắn thì sẽ tìm ra nhanh, còn không thì có thể đến "sáng mai" vẫn chưa ra nổi. Còn thuật toán bám tường có thể hiểu như sau:
Đặt tay phải hoặc trái lên tường và bắt đầu di chuyển sao cho tay luôn luôn chạm vào một bên tường. Với cách này, sau một lúc di chuyển, bạn cũng sẽ đến được đích. Một cách khác để diễn giải thuật toán này, đó là việc ưu tiên rẽ ở chỉ một phía. Ví dụ như ưu tiên phải, tại mỗi điểm rẽ, xe sẽ luôn luôn rẽ phải trước, nếu bên phải không có đường thì đi thẳng, nếu phía trước không có đường nữa thì mới rẽ trái. Như thế tay bạn sẽ luôn luôn chạm vào tường bên phải.
Các phương pháp kể trên có một nhược điểm, đó là quãng đường thu được sau khi đến đích thường rất dài do trước đó gặp phải khá nhiều ngõ cụt (mà thực ra đi kiểu gì cũng vậy thôi, vì chúng ta đâu có biết trước mê cung để một phát đến được đích ngay 
). Thế nên sau khi có được đường đi, ta cần phải tối ưu nó để ra được cách di chuyển ngắn nhất.
). Thế nên sau khi có được đường đi, ta cần phải tối ưu nó để ra được cách di chuyển ngắn nhất.
Và cách hôm nay mình giới thiệu là một phương pháp đơn giản giúp các bạn thực hiện được điều đó. 
2. Mô tả thuật toán
Trước tiên, để thực hiện được thuật toán, xe dò đường của bạn tất nhiên phải có chức năng ghi lại những hướng đã đi tại các điểm rẽ. Những hướng đó được lấy theo hê tọa độ cố định gắn với mê cung (ví dụ như lên, xuống, trái, phải). Ta lưu lại những hướng này vào một chuỗi để tiến hành rút gọn.
Nguyên tắc của thuật toán này là khử dần những đường đi ngược nhau, lặp lại liên tục, cho đến khi nào không thể rút gọn được nữa, thì đó sẽ là đường đi ngắn nhất. Trong chuỗi đã lưu sẽ có những cặp ký tự chỉ hướng ngược nhau và đứng liền nhau, ta sẽ nhận biết được đó là ngõ cụt. Để bỏ qua ngõ cụt đó, ta chỉ cần xóa chúng đi là xong.
Ví dụ 1: Cùng xem qua một ví dụ và ta sẽ rút gọn nó.
Quy ước viết tắt hướng đi:
| Lên | U |
| Xuống | D |
| Trái | L |
| Phải | R |
Như vậy bắt đầu từ 1 ta có:
- 1: U
- 2: L
- 3: R
- 4: D
=> ULRD
Ta nhận thấy những hướng ngược chiều nhau và đứng cạnh nhau là ngõ cụt (ở trên là L,R). Do đó ta có thể bỏ đi.
ULRD => UD
Chỉ còn lại UD. UD lại tiếp tục ngược nhau, ta lại rút gọn thêm một lần nữa...
...và chuỗi ULRD đã không còn, do đó xe sẽ bỏ qua đường này. 
Ví dụ 2: Ví dụ tiếp theo với một đường đi thẳng và đường rẽ ngang.
Ta có chuỗi: LULRDL. Bắt đầu rút gọn:
LULRDL => LUDL => LL
Như vậy, ban đầu xe đi về phía bên trái tại số 1. Đến ngã rẽ, xe sẽ bỏ qua để tiếp tục đi về phía trái. Như thế ta đã rút gọn bớt được một ngõ cụt.
Ví dụ 3: Đây sẽ là một mê cung hoàn chỉnh đơn giản. Nếu bạn hiểu rồi thì hãy thử tự giải và rút gọn trước khi xem đáp án.
Giả sử xe dò đường của chúng ta sử dụng thuật toán bám tường phải. Sau một hồi mò mẫm ta có đường đi như hình, tại mỗi điểm rẽ ta đều ghi lại hướng tiếp theo sẽ di chuyển. Chuỗi đường đi sẽ như sau: URDD URRL URDU LLUR DURD (mình viết cách ra cho dễ nhìn thôi nhé, thực tế chuỗi được ghi liền)
Tiến hành khử các cặp UD, DU, LR, RL cạnh nhau, cho đến khi không còn nữa thì thôi.
URDD URRL URDU LLUR DURD => URDRRLURLLURRD => URDRULURRD
Hãy thử dùng kết quả và dò trên hình, bạn sẽ thấy con đường tới đích đã ngắn hơn rất nhiều.
Vấn đề còn lại cho bạn tự giải quyết, đó là làm thế nào để ghi lại hướng đi tại từng điểm rẽ theo hệ tọa độ gắn với mê cung, làm thế nào để triển khai thuật toán trên dưới dạng code C++ nhằm rút gọn chuỗi đường đi, và cuối cùng để xe tự di chuyển theo lộ trình của chuỗi đã rút gọn.
Trên đây là toàn bộ mô tả về thuật toán tìm đường đi ngắn nhất trong mê cung của mình. Hy vọng với ý tưởng này, các bạn có thể triển khai thành công vào việc chế tạo xe dò đường. Nếu có thời gian, mình sẽ viết tiếp cách để có thể triển khai thuật toán này dưới dạng code C++, giúp thuận tiện hơn cho các bạn khi lập trình cho xe.
===================================
Bổ sung code của thành viênMinh Nghia Pham
- #include <iostream>
- #include <stdio.h>
- #include <conio.h>
- #include <cstring>
- using namespace std;
- int Search_street(char x[], int a[], int size1)
- {
- // quy chuoi ra man tran
- for (int i = 0; i < size1; i++) {
- if (x[i] == 'L')
- a[i] = 3;
- else if (x[i] == 'R')
- a[i] = 2;
- else if (x[i] == 'D')
- a[i] = 10;
- else if (x[i] == 'U')
- a[i] = 1;
- // cout << a[i] << endl;
- }
- int i = 0;
- while (i < size1) {
- int size_current = size1;
- if (a[i] * a[i + 1] == 10 || a[i] * a[i + 1] == 6) { // co su rut gon
- if (a[i + 2] == size1)
- a[i] = a[i + 2];
- else {
- for (int j = i; j < size1 - 2; j++) {
- a[j] = a[j + 2];
- }
- }
- // XOA PHAN TU CU THUA
- for (int j = size1 - 2; j < size1; j++) {
- a[j] = 0;
- }
- size1 = size1 - 2;
- }
- // neu k cos su rut gon thi tag i;
- if (size_current == size1)
- i++;
- }
- // doc nguoc tu mang a de ra mang x
- for (int j = 0; j < size1; j++) {
- if (a[j] == 1)
- x[j] = 'U';
- else if (a[j] == 10)
- x[j] = 'D';
- else if (a[j] == 3)
- x[j] = 'L';
- else if (a[j] == 2)
- x[j] = 'R';
- }
- x[size1] = '\0';
- cout << " duong di ngan nhat " << x << endl;
- return 0;
- }
- int main()
- {
- int H[30];
- char Street[30];
- cout << " U la len, D la xuong, L la re trai, R la re phai " << endl;
- cout << " hay nhap duong di thu thap dc " << endl;
- fflush(stdin);
- gets(Street);
- Search_street(Street, H, strlen(Street));
- return 0;
- }
- // CODE BLOCK, GUUGC , ĐÃ TEST OKIE
Đăng ký:
Bài đăng (Atom)