Tìm con đường ngắn nhất đến thăm tất cả các hình vuông không bị chặn trên một mạng lưới

Question

Hãy nói rằng bạn có một mạng lưới như thế này (làm một cách ngẫu nhiên):

Bây giờ giả sử bạn có một chiếc xe bắt đầu một cách ngẫu nhiên từ một của các ô trong khi nào, đường dẫn ngắn nhất ngắn nhất là gì để đi qua từng hộp màu trắng? Bạn có thể ghé thăm từng ô màu trắng bao nhiêu lần tùy thích và không thể nhảy qua các ô đen. Các hộp đen giống như bức tường. Nói một cách đơn giản, bạn chỉ có thể chuyển từ hộp trắng sang hộp trắng.

Bạn có thể di chuyển theo bất kỳ hướng nào, thậm chí theo đường chéo.

Hai subquestions:

1. Giả sử bạn biết vị trí của tất cả các hộp đen trước khi chuyển.
2. Giả sử bạn chỉ biết vị trí của một hộp đen khi bạn đang ở trong một hộp màu trắng bên cạnh nó.

Answer 1

Cố gắng xây dựng nó như một đồ thị (trong đó mỗi nút có ít nhất 8 nút khác) và đối xử với nó như http://en.wikipedia.org/wiki/Travelling_salesman_problem

Answer 2

này tương tự như vấn đề Knights Tour, nơi một giải pháp điển hình đánh giá tất cả các tuyến đường có thể có nguồn gốc từ hình vuông bắt đầu. Khi một tour du lịch không thể hoàn thành, sau đó backtracking được sử dụng để trở về để sao lưu trên các quyết định trước đó. Vấn đề của bạn thoải mái hơn vì bạn có thể ghé thăm các ô vuông nhiều lần. Các tour du lịch Knights và Du lịch Saleman vấn đề thường yêu cầu truy cập vào mỗi hình vuông chính xác một lần.

Xem http://en.wikipedia.org/wiki/Knight's_tour

Answer 3

Bạn nên mô hình các vấn đề như một đồ thị hoàn chỉnh, nơi khoảng cách giữa hai nút (hộp trắng) là chiều dài của con đường ngắn nhất giữa các nút. Độ dài đường dẫn có thể được tính toán bằng thuật toán Floyd-Warshall. Sau đó, bạn có thể coi nó là "Traveling salesman", như bộ phát sáng đã viết.

CHỈNH SỬA: để làm rõ hơn: bạn có thể mô tả từng con đường "thú vị" thông qua mê cung theo một chuỗi khác nhau hộp màu trắng. Bởi vì nếu bạn có một con đường tùy ý truy cập vào mỗi hộp màu trắng, bạn có thể chia nó thành các đường dẫn con, mỗi con đường kết thúc tại một ô trắng mới không được truy cập từ trước đến nay. Mỗi đường dẫn con từ hộp màu trắng từ A đến B có thể được thay thế bằng một đường con ngắn nhất từ ​​A đến B, đó là lý do tại sao bạn cần ma trận đường đi ngắn nhất giữa tất cả các cặp-của-nút.

Answer 4

Điều này có vẻ là sự cố NP-Complete.

Đường dẫn Hamilton trong đồ thị lưới là NP-Complete đã được hiển thị ở đây: Hamilton Paths in Grid Graphs.

Lưu ý đồ thị lưới = biểu đồ con của lưới hoàn chỉnh.

Tất nhiên, tôi chưa đọc bài báo đó, vì vậy hãy xác nhận nó trước, đặc biệt là chuyển động chéo cho phép một phần.

Answer 5

Tài liệu đã nhận được. Tôi sẽ thêm rằng các hộp đen chỉ thay đổi khoảng cách giữa tất cả các cặp hộp màu trắng. Xây dựng thêm - nếu có một hộp đen trên đường chéo giữa bất kỳ hai hộp màu trắng nào (dễ kiểm tra), bạn cần tính toán đường đi ngắn nhất để lấy khoảng cách. Khi bạn có ma trận khoảng cách, hãy giải quyết TSP hoặc Đường dẫn Hamilton bằng cách giải quyết TSP sau khi tạo nút giả có độ dài bằng 0 cho tất cả các nút khác.

Điều quan trọng là để xây dựng và giải quyết TSP (hoặc bất kỳ công thức vấn đề nào cho vấn đề đó), bạn PHẢI có ma trận khoảng cách để bắt đầu. Ma trận khoảng cách không được chỉ định ở đầu nên nó phải được phát triển từ đầu.

Answer 6

trong khi phương pháp phỏng đoán dựa trên TSP là một cách tiếp cận hợp lý, không rõ nó đưa ra câu trả lời tối ưu. Vấn đề (như Moron chỉ ra) là vấn đề đường mòn kéo dài, và trong liên kết được cung cấp trong nhận xét, có nhiều trường hợp đặc biệt mà có các giải pháp tối ưu thời gian tuyến tính. Một điều khiến cho vấn đề của OP khác với công thức đồ thị lưới được sử dụng trong bài báo là khả năng đi qua đường chéo, thay đổi trò chơi khá một chút.