52
Tôi muốn tìm một thuật toán tốt hơn để giải quyết các vấn đề sau đây:không giao nhau đoạn thẳng trong khi giảm thiểu độ dài tích lũy
Có N điểm bắt đầu (màu tím) và N điểm mục tiêu (màu xanh) trong 2D. Tôi muốn một thuật toán kết nối các điểm bắt đầu với các điểm mục tiêu bằng một đoạn thẳng (màu nâu) mà không có bất kỳ phân đoạn nào giao nhau (màu đỏ) và trong khi giảm thiểu độ dài tích lũy của tất cả các đoạn.
Nỗ lực đầu tiên của tôi trong C++ đã làm mất đi tất cả các trạng thái có thể, tìm trạng thái không có giao lộ, và trong số các trạng thái có tổng chiều dài phân đoạn tối thiểu O (n!). Nhưng tôi nghĩ rằng phải có một cách tốt hơn.
Bất kỳ ý tưởng nào? Hoặc từ khóa tốt cho tìm kiếm?
Có thể một số loại kiểu tôpô? –
Tôi không biết câu trả lời, nhưng tôi sẽ tạo ra bất kỳ giải pháp nào (bỏ qua xung đột) và sau đó giải quyết xung đột riêng lẻ: khi hai đường xung đột, có vẻ như việc chuyển đổi một cặp điểm cuối sẽ giải quyết xung đột. Tôi không chắc chắn làm thế nào để đảm bảo tiến bộ, mặc dù. –
@ DietmarKühl: Việc chuyển đổi điểm cuối có thể gây ra xung đột khác để xuất hiện. –