Làm thế nào để giải quyết vấn đề Rope Bridge bằng một thuật toán?

Question

Tôi đã tự hỏi liệu vấn đề cầu dây này có thể được giải quyết bằng thuật toán tìm kiếm đồ thị hay không:

Cảm giác ruột của tôi nói DFS nhưng làm cách nào để xác định trạng thái? (Tức là nếu DFS là ngay cả những con đường để đi.)

Rope Bridge

Answer 1

Nhiệm vụ này là vụ phải được giải quyết mà không có một máy tính.

Tuy nhiên, nếu bạn khái quát hóa trường hợp, thì tôi giả sử bạn có thể làm điều đó với tìm kiếm đồ thị, nhưng bạn nên lấy kích thước của biểu đồ thành tài khoản. Nếu mỗi đỉnh là "trạng thái", thì số trạng thái này được ước tính là 2 ^N ⋅L, trong đó N là số người và L là độ dài của đèn nháy. Mỗi tiểu bang chứa thông tin, bên nào là mỗi người tại, và thời lượng đèn pin còn lại. Nếu có một con đường từ trạng thái ban đầu đến một trong những trạng thái mà mọi người ở bên phe, thì con đường này là giải pháp.

Đó là cách rõ ràng nhất để tạo trạng thái, nhưng có thể bạn có thể làm điều đó một cách hiệu quả hơn (số trạng thái hiện tại, do đó thời gian chạy, là theo cấp số nhân với kích thước đầu vào).

Tuy nhiên, đối với các kích thước nhỏ như trong mẫu bạn đã cung cấp, thời gian chạy theo hàm mũ (có biểu đồ) có thể chấp nhận được. Người phỏng vấn thậm chí có thể thích nó, nếu bạn đề xuất giải pháp lập trình thay vì thực hiện nó bằng tay.

Answer 2

Bạn có thể muốn xem EWD 1255.