Find all group of neighbors with a constraint weight
-
04-11-2019 - |
题
Forgive if this seems like a repeated question. However, I couldn't find a specific algorithm to my needs.
I have nodes that have weights with each other. I want to find all unique groups of nodes, with the constraint that every node in the group has a weight with every other node a value that is less than a certain pre-specified constant.
Let's take an example. The following is a table of weights where the row number and column number can be considered as node numbers.
6 15 25 4 6 1 4 15 28 19 20 15 28 6 25 19 4 26 2 10 2 4 20 26 15 1 15 29 6 15 2 1 13 20 15 1 28 10 15 12 5 16 4 6 2 29 15 16 7
Considering a weight limit of 15 the result I generated using my brute force solution looks like the following:
1 5 4 1 6 4 1 7 5 2 1 7 6 2 7 5 3 3 7 5 3 7 6 4 5 4 6 5 7 6 7
Now consider the first result 1 5 4
the weight between 1 and 5, w(1,5)=6; w(1,4) = 4; w(5,4) = 1. we can't add node 6 to this group because w(5,6) = 20.
The solution I have now takes forever when the dataset is larger. Is there an optimized algorithm that I am missing? Thanks for the help.
没有正确的解决方案