Tất cả thử thách
Trung bình 2 đã giải Tỷ lệ chấp nhận 100.0%

Tìm kiếm A* trên lưới có trọng số

Tìm đường đi rẻ nhất qua một lưới chi phí địa hình bằng A*, thuật toán tìm đường phía sau game và robot.

Bạn sẽ học được gì

  • Tìm đường rẻ nhất bằng hàng đợi ưu tiên
  • Dùng khoảng cách Manhattan làm heuristic
  • Hiểu vì sao heuristic chấp nhận được vẫn tối ưu

Đề bài

Xem bản gốc (English)

A* là thuật toán tìm đường kinh điển trong game và robot. Nó duyệt các ô theo thứ tự f = g + h, trong đó g là chi phí đã trả và h là ước lượng heuristic của chi phí còn lại.

Lưới chứa chi phí của từng ô: đi vào một ô tốn đúng giá trị của ô đó, và 0 là tường không thể đi vào. Bạn bắt đầu ở start (không trả chi phí ô này) và có thể đi lên, xuống, trái hoặc phải.

Dùng A* với heuristic là khoảng cách Manhattan |row - goal_row| + |col - goal_col|. Mọi ô đi được đều tốn ít nhất 1, nên heuristic này không bao giờ ước lượng quá và A* trả về kết quả tối ưu.

Hãy viết a_star_cost(grid, start, goal).

Đầu vào

grid: Ma trận chi phí của các ô (0 = tường).

start, goal: Vị trí dạng [row, col].

Đầu ra

Trả về tổng chi phí nhỏ nhất để đến goal, hoặc -1 nếu không thể đến (kể cả khi start hoặc goal là tường).

Ràng buộc

1 ≤ số hàng, số cột ≤ 100

0 ≤ mỗi chi phí ≤ 9

Ví dụ

Ví dụ 1
Đầu vào:
grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
start = [0, 0]
goal = [2, 2]

Kết quả mong đợi:
expected = 4
Đầu vào:
std::vector<std::vector<long long>> grid = {
    {1, 1, 1},
    {1, 0, 1},
    {1, 1, 1}
};
std::vector<long long> start = {0, 0};
std::vector<long long> goal = {2, 2};

Kết quả mong đợi:
long long expected = 4;
Đầu vào:
long[][] grid = new long[][] {
    new long[] {1, 1, 1},
    new long[] {1, 0, 1},
    new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
long[] goal = new long[] {2, 2};

Kết quả mong đợi:
long expected = 4;

Giải thích

Ô giữa là tường. Đi sang phải hai lần rồi xuống hai lần (hoặc xuống rồi sang phải) sẽ đi vào 4 ô chi phí 1, tổng là 4.

Ví dụ 2
Đầu vào:
grid = [
    [1, 9, 1],
    [1, 9, 1],
    [1, 1, 1]
]
start = [0, 0]
goal = [0, 2]

Kết quả mong đợi:
expected = 6
Đầu vào:
std::vector<std::vector<long long>> grid = {
    {1, 9, 1},
    {1, 9, 1},
    {1, 1, 1}
};
std::vector<long long> start = {0, 0};
std::vector<long long> goal = {0, 2};

Kết quả mong đợi:
long long expected = 6;
Đầu vào:
long[][] grid = new long[][] {
    new long[] {1, 9, 1},
    new long[] {1, 9, 1},
    new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
long[] goal = new long[] {0, 2};

Kết quả mong đợi:
long expected = 6;

Giải thích

Đi thẳng qua ô 9 tốn 9 + 1 = 10. Đi xuống, dọc theo hàng cuối rồi đi lên sẽ đi vào sáu ô chi phí 1, tổng là 6.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Dùng priority queue được sắp theo chi phí đã đi cộng với Manhattan distance tới đích.

Gợi ý 2

Theo dõi chi phí tốt nhất đã tìm cho mỗi ô, và chỉ mở rộng một ô khi đường đi hiện tại cải thiện nó.

Gợi ý 3

Xem tường và ô start hoặc goal bị chặn là không thể đi được, và nhớ rằng bước vào ô start là miễn phí.

Độ phức tạp mong đợi

thời gian O(rows * cols log(rows * cols)), bộ nhớ phụ O(rows * cols)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 849 ms - 5/5 Xem code
2 HTHolota Tudor Python 867 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 2 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.