Có một thuật toán nổi tiếng nào được điền vào lưới cho một tập hợp các điểm không?

Question

Tôi thấy trò chơi này ở đây Flow, có vẻ khá thú vị.

Kết nối màu phù hợp với đường ống để tạo luồng. Ghép nối tất cả các màu, và che toàn bộ bảng để giải quyết từng câu đố. Nhưng hãy chú ý, các đường ống sẽ bị vỡ nếu chúng bị gạch chéo hoặc chồng lên nhau.

Cho một tập hợp các cặp (x, y), có giải thuật để giải câu đố, tức là điền vào toàn bộ lưới (giả sử có giải pháp) mà tôi không biết?

Answer 1

Đây là trường hợp rất cụ thể của vấn đề định tuyến toàn cầu. Định tuyến toàn cầu là một vấn đề được nghiên cứu kỹ lưỡng trong VLSI CAD (nơi mà người ta cần phải định tuyến hàng triệu mạng trong một mạch tích hợp). Vấn đề là NP-complete và có thể được giải quyết theo nhiều cách tùy thuộc vào sự cân bằng bạn cần giữa thời gian chạy và chất lượng. Sau wiki là một điểm khởi đầu tốt:

http://en.wikipedia.org/wiki/Routing_(electronic_design_automation)

Giấy đây đưa ra một cuộc khảo sát của các kỹ thuật khác nhau:

http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf

Gấu nhớ rằng các con trỏ tôi đã cho thường cố gắng để giải quyết một phiên bản phức tạp hơn nhiều của vấn đề bạn đã nói. Không bao giờ-ít, các khái niệm toán học vẫn giữ nguyên.