Tuyên bố miễn trừ trách nhiệm: Trình độ của tôi còn hạn chế. Bài viết này là bản tóm tắt nghiên cứu của tác giả và chỉ mang tính chất tham khảo.

1. Giới thiệu tìm kiếm

Các thuật toán tìm kiếm bao gồm tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS), bắt đầu từ điểm bắt đầu và dần dần mở rộng phạm vi tìm kiếm cho đến khi tìm thấy câu trả lời cần thiết. Xét về độ phức tạp về thời gian, cách này không khác nhiều so với cách liệt kê brute Force thông thường. Trong trường hợp này, tại sao chúng ta nên sử dụng thuật toán tìm kiếm thay vì sử dụng trực tiếp phương pháp brute Force? Trước hết, thuật toán tìm kiếm là một cách viết brute Force tinh tế, tức là brute Force thanh lịch, có thể giảm bớt các vòng lặp for lồng nhau dài dòng trong mã của chúng ta. Thứ hai, việc tìm kiếm có thể bỏ qua một số trạng thái không hợp lệ và giảm kích thước của vấn đề thông qua thao tác cắt tỉa, do đó làm cho việc tìm kiếm hiệu quả hơn so với việc liệt kê trực tiếp tất cả các câu trả lời.

2. Sự khác biệt giữa DFS và BFS

3. Tặng một ít hạt dẻ

3.1 BFS--đi ngang qua ngựa

Mô tả câu hỏi

Có một bàn cờ $ n * m $ và có một quân mã tại một điểm nhất định $ (x, y) (x, y) $. Bạn phải tính số bước tối thiểu để quân mã đó đạt được bất kỳ điểm nào. điểm trên bàn cờ.

Đây là một câu hỏi BFS kinh điển, có thể nói là một câu hỏi mẫu. Trước khi giải quyết vấn đề tôi xin giới thiệu ý tưởng triển khai BFS như sau:

[1] Xây dựng cấu trúc và hàng đợi tương ứng [2] Khởi tạo dữ liệu và điểm ban đầu [3] Đi qua các điểm khác đáp ứng yêu cầu dựa trên điểm ban đầu và mối quan hệ truyền tải [4] Truy vấn câu trả lời.

Theo ý tưởng triển khai của BFS, mã cho câu hỏi này có thể dễ dàng lấy được như sau.

                        
                          #include  #define N_MAX 400 sử dụng không gian tên std; int mp[N_MAX][N_MAX]; // mp[i][j] đại diện cho số lần int tối thiểu cần thiết để hiệp sĩ đạt được (i , j) điểm n,m,x,y // Xác định dx dy để thực hiện các phép tính int dx[] = {-1,1,2,2,1,-1,-2,-2}; int dy[] = {-2,-2,-1,1,2,2,1,-1}; // [1] Xác định cấu trúc dữ liệu và duilie struct point{ int x,y // điểm Tọa độ int t; // Số lần ngựa đến điểm tối thiểu}; queue que; int main() { // [2] Khởi tạo dữ liệu memset(mp,-1,sizeof(mp)); > n >> m >> x >> y; mp[x][y] = 0; // Điểm ban đầu là 0 // [3] Tìm kiếm que.push((point){x,y,mp[x][y]}); // Đầu tiên đẩy điểm ban đầu vào hàng đợi while(!que.empty()) { // Duyệt từng điểm một từ hàng đợi p = que.front(); // Nhớ bật / / Tìm các điểm thỏa mãn điều kiện và đẩy chúng vào hàng đợi for(int i = 0;i < 8;i++) { int nx = px + dx[i]; int ny = py + dy[i]; đó là hợp pháp if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == -1) { mp[nx][ny] = pt + 1; que.push((point){nx,ny,mp[nx][ny]}); } } } // Kết quả đầu ra cho(int i = 1;i < = n;i++) { for(int j = 1;j <= m;j++) { cout << mp[i][j] << " "; } cout << endl } return 0; }

                        
                      

3.2 BFS - thang máy lạ

Mô tả câu hỏi

Haha, một hôm tôi mơ thấy một chiếc thang máy rất lạ. Mỗi tầng của tòa nhà đều có thang máy và có số \(K_i\) ở tầng \(i\)th ( \(1 \le i \le N\) ) ( \(0 \le K_i \ le N\) ). Thang máy chỉ có bốn nút: bật, tắt, lên và xuống. Số tầng trên và dưới bằng số tầng hiện tại. Tất nhiên, nếu không đáp ứng được yêu cầu thì nút tương ứng sẽ bị lỗi. Ví dụ: \(3, 3, 1, 2, 5\) đại diện cho \(K_i\) ( \(K_1=3\) , \(K_2=3\) ,...), từ \(1\) bắt đầu sàn. Ở tầng \(1\), nhấn "lên" để lên tầng \(4\). Nhấn "xuống" không có tác dụng vì không có tầng \(-2\). Vậy bạn cần nhấn nút từ tòa nhà A đến tòa nhà B bao nhiêu lần?

Câu hỏi này cũng là một câu hỏi mẫu BFS, được sử dụng để củng cố Mã AC cụ thể như sau.

                        
                          #include  sử dụng không gian tên std; #define N_MAX 201 điểm cấu trúc{ int f; // 所在层数 int ki; // 拥有的数字 int t; // 需要按的次数 }; hàng đợi<điểm> que; int ans[N_MAX]; int n,a,b; int k[N_MAX]; int main() { memset(ans,-1,sizeof(ans)); cin >> n >> a >> b; for(int i = 1;i <= n;i++) { cin >> k[i]; } ans[a] = 0; // bfs que.push((point){a,k[a],ans[a]}); while(!que.empty()) { điểm p = que.front(); que.pop(); int nf = pf + p.ki; // Nếu(nf <= n && ans[nf] == -1) { ans[nf] = p.t+1; que.push( (điểm){nf,k[nf],ans[nf]}); } nf = pf - p.ki; // 下 nếu(nf >= 1 && ans[nf] == -1) { ans[nf ] = p.t+1; que.push((điểm){nf,k[nf],ans[nf]}); } } cout << ans[b] << endl; trả về 0; }

                        
                      

3.4 DFS--tổ hợp các số

Mô tả câu hỏi

Cho hai số nguyên n và k, trả về tất cả k tổ hợp số có thể có trong phạm vi [1, n]. Bạn có thể trả lời câu trả lời theo thứ tự bất kỳ.

Đây là một bài toán DFS điển hình. Nhóm DFS chủ yếu sử dụng thuật toán quay lui để giải quyết. Khó khăn cụ thể của việc quay lui là như sau.

[1] Viết lối ra đệ quy (thu thập trái cây) [2] Lặp qua tìm kiếm và thực hiện tối ưu hóa cắt tỉa [3] Xử lý nút [4] Đệ quy [5] Quay lui, tức là hủy hướng trái khi xử lý nút. Mã cho câu hỏi này như sau:

                        
                          class Solution { public: vector<>> ret; // Được sử dụng để lưu trữ đường dẫn vector kết quả cuối cùng; // Được sử dụng để lưu trữ kết quả trung gian void bnf(int st,int n,int k) { / / Thu thập trái cây (điều kiện hủy bỏ) if(path.size() == k) { ret.push_back(path); return } // Lặp lại và thực hiện tối ưu hóa việc cắt tỉa for(int i = st;i <= n - k + đường dẫn.size() + 1;++i) { // Nút xử lý path.push_back(i); // bnf(i+1,n,k); // Đường dẫn quay lại.pop_back() } } vector<>; > kết hợp(int n, int k) { bnf(1,n,k); return ret;

                        
                      

4.Tham khảo

Mã Ngẫu nhiên Bản ghi Luo Gu Thuật toán Tìm kiếm Câu hỏi Đề xuất Giải quyết vấn đề Luo Gu Traversal của Kuma Bài viết này kết thúc tại đây. Tôi hy vọng nó sẽ hữu ích cho bạn.

Cuối cùng, bài viết về tìm kiếm tóm tắt thuật toán này kết thúc tại đây. Nếu bạn muốn biết thêm về tìm kiếm tóm tắt thuật toán, vui lòng tìm kiếm bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .