Giới thiệu
Chào mừng bạn đến với bài viết về giải đố Advent của Code 2024 ngày 18! Trong bài viết này, chúng ta sẽ cùng nhau khám phá cách tìm đường đi ngắn nhất trong một lưới với các ô bị hỏng. Đặc biệt, chúng ta sẽ sử dụng các kỹ thuật như đệ quy và ghi nhớ để tối ưu hóa thuật toán tìm kiếm.
Tóm tắt bài toán
Bài toán yêu cầu chúng ta tìm đường đi ngắn nhất từ điểm bắt đầu đến điểm kết thúc trong một lưới có kích thước 70x70. Tuy nhiên, trong ví dụ của chúng ta, lưới chỉ có kích thước 6x6. Chúng ta sẽ nhập vào danh sách các tọa độ X,Y và xác định cách xử lý chúng để xây dựng lưới.
Cấu trúc bài viết
1. Tạo lưới
Để tạo lưới, chúng ta có thể sử dụng hàm sau:
javascript
function makeGrid(width, height) {
return new Array(height + 1)
.fill(0)
.map(el => new Array(width + 1).fill('.'));
}Khi gọi hàm này với kích thước 6:
javascript
let grid = makeGrid(6, 6);Kết quả sẽ là một lưới 6x6 như sau:
.......
.......
.......
.......
.......
.......2. Xử lý đầu vào
Để tạo danh sách tọa độ từ đầu vào, chúng ta có thể sử dụng đoạn mã sau:
javascript
let coords = input.split('\n').map(coord => coord.split(',').map(Number));Đoạn mã này sẽ giúp chúng ta:
- Tách chuỗi đầu vào theo từng dòng
- Tách mỗi chuỗi tọa độ tại dấu phẩy
- Chuyển đổi các chuỗi thành số
3. Cập nhật lưới
Để thay đổi một số ô thành trạng thái hỏng, chúng ta sử dụng hàm sau:
javascript
function updateGrid(amt) {
coords.slice(0, amt).forEach(coord => {
grid[coord[1]][coord[0]] = '#';
});
}Khi gọi hàm này với 12, chúng ta sẽ có được lưới như sau:
...#...
..#..#.
....#..
...#..#
..#..#.
.#..#..
#.#....4. Thêm biên cho lưới
Để làm cho điều kiện kiểm tra đơn giản hơn, chúng ta sẽ thêm biên cho lưới:
javascript
function addGridBorder() {
grid = grid.map(row => ['#', ...row, '#']);
grid = [
new Array(size + 2).fill('#'),
...grid,
new Array(size + 2).fill('#'),
];
}Kết quả sẽ là lưới có biên:
#########
#...#...#
#..#..#.#
#....#..#
#...#..##
#..#..#.#
#.#..#..#
##.#....#
#########5. Xây dựng thuật toán tìm đường
Chúng ta sẽ sử dụng đệ quy để khám phá tất cả các đường đi có thể trong lưới:
javascript
function walkGrid(current, visited) {
visited.add(current.join(','));
if (current.join(',') == end.join(',')) {
fewestSteps = Math.min(visited.size, fewestSteps);
return false;
} else {
let next = nearby.map(coord => grid[coord[0] + current[0]][coord[1] + current[1]] == '#' ? false : true);
if (next.every(el => el == false)) {
visited.delete(current.join(','));
return false;
} else {
next.forEach((el, index) => {
if (el) {
walkGrid([
current[0] + nearby[index][0],
current[1] + nearby[index][1]
], new Set(visited));
}
});
}
}
}6. Kiểm tra thuật toán
Chúng ta nên thêm các câu lệnh ghi log để kiểm tra kết quả:
javascript
if (current.join(',') == end.join(',')) {
console.log(current, visited.size);
fewestSteps = Math.min(visited.size, fewestSteps);
return false;
}7. Giải quyết các vấn đề thường gặp
- Lỗi tràn ngăn xếp: Điều này có thể xảy ra khi thuật toán đệ quy không thoát kịp thời. Hãy kiểm tra điều kiện dừng của bạn.
- Danh sách tọa độ đã thăm không tăng lên: Đảm bảo rằng bạn đang thêm tọa độ vào danh sách đúng cách và xóa chúng khi cần thiết.
8. Tối ưu hóa hiệu suất
Để giảm thiểu số bước, hãy kiểm tra xem số bước đã thực hiện có lớn hơn số bước tối thiểu chưa. Nếu có, hãy thoát khỏi hàm ngay lập tức.
javascript
if (visited.size - 1 > fewestSteps) {
return false;
}9. Thực hiện bài kiểm tra cuối cùng
Sau khi hoàn tất, hãy chạy chương trình với đầu vào thực tế của bạn và kiểm tra xem nó có hoàn thành đúng không và có thể tìm ra đường đi ngắn nhất không.
Kết luận
Trong bài viết này, chúng ta đã cùng nhau tìm hiểu cách giải quyết bài toán tìm đường ngắn nhất trong một lưới thông qua các kỹ thuật như đệ quy và ghi nhớ. Hy vọng rằng bài viết này sẽ giúp ích cho bạn trong việc giải quyết các bài toán tương tự trong tương lai. Nếu bạn có bất kỳ câu hỏi nào, hãy để lại trong phần bình luận bên dưới!
Câu hỏi thường gặp (FAQ)
1. Tôi có thể sử dụng ngôn ngữ nào để giải quyết bài toán này?
Bạn có thể sử dụng bất kỳ ngôn ngữ lập trình nào hỗ trợ đệ quy và quản lý bộ nhớ, như JavaScript, Python, Java, v.v.
2. Có cách nào khác để tìm đường đi ngắn nhất không?
Ngoài thuật toán đệ quy, bạn có thể sử dụng thuật toán Dijkstra hoặc A* để tìm đường đi ngắn nhất.
3. Làm thế nào để tối ưu hóa thuật toán của tôi?
Bạn có thể sử dụng ghi nhớ để lưu trữ các kết quả đã tính toán trước đó và tránh tính toán lại.
4. Tôi nên làm gì nếu thuật toán của tôi không trả về kết quả đúng?
Hãy kiểm tra lại logic của bạn, đảm bảo rằng bạn đã xử lý đúng các điều kiện dừng và không có lỗi cú pháp nào trong mã của bạn.
