Cách sắp xếp/sắp xếp bảng phụ thuộc 2D

Question

Tôi tò mò nếu có một số lý thuyết/phương pháp/thuật toán mức cao hơn để giải quyết vấn đề này tôi có.

Tôi đang làm việc trên sự cố định tuyến mạng (mạng vô tuyến độc quyền). Ví dụ, tôi có một mạng lưới gồm 5 thiết bị. Đối với mỗi thiết bị, tôi có thể đo mức độ tuyệt vời của thiết bị này. Nút gốc thứ 0 chỉ thú vị như một nguồn. Vì vậy, ở dạng bảng, tôi có thể kết thúc bằng một cái gì đó như:

_0_ _1_ _2_ _3_ _4_ 
1 | 21 - 42 55 0 
2 | 0 63 - 18 20 
3 | 20 0 0 - 0 
4 | 0 0 13 0 - 

Mỗi hàng cho biết thiết bị có thể nghe được 5 nguồn khác như thế nào. Những gì tôi muốn làm là sắp xếp chúng để mỗi thiết bị nhận được các tín hiệu tổng hợp tốt nhất từ ​​các phần tử trước đó. Vì vậy, đối với trường hợp đơn giản này, thứ tự có thể là 1, 3, 2, 4. Nhưng nó cũng có thể là 3, 1, 2, 4. Trong thực tế, thứ hai này sẽ tốt hơn bởi vì 1 có thể nghe cả 0 và 3. 3, 2, 1, 4 cũng sẽ hoạt động.

Tôi đang cố gắng xác định loại thuật toán nào tôi có thể sử dụng để đặt hàng các thuật toán này. Có một số nhân viên bán hàng du lịch đến đó và tôi không cần loại "tốt nhất". Chỉ là một loại khá tốt. Tôi cần phải mở rộng tới 9 thiết bị với 10 nguồn.

Bất kỳ suy nghĩ, trợ giúp, nudges, mẹo, gợi ý được đánh giá cao.

Answer 1

Sự cố này có thể được mô hình hóa là minimum feedback arc set problem, đây là sự cố NP-hard. Biểu đồ ban đầu là biểu đồ được hướng hoàn chỉnh, với trọng số của mỗi cạnh (v0, v1) là cường độ tín hiệu từ v0 đến v1. Sau khi tính toán tập hồ quang phản hồi tối đa, thực hiện sắp xếp topo sẽ đưa ra thứ tự có tổng tín hiệu tối đa.