Apologies if this question is not suited for this forum. The question extends beyond my knowledge of mathematics and programming, it is quite hard to get my head around it let alone put it in to words.
I am looking for a similar established problem from which I can construct an acceptable solution. The problem is as follows.
From a hands on perspective the problem appears similar to the traveling salesman problem, a set of interconnected nodes (network) with an associated quantifiable cost for moving from one to another. The major difference is the realization between any two paths potentially changes the cost of all subsequent steps, removes possible paths or in some cases removes nodes completely from the network.
I want to, in a reasonable amount of time, find a path or small collection of paths which is close to the best starting from any node, best being defined as the path which produces the lowest value from the equation [cost / total nodes travelled].
The obvious answer would be to permutate over all paths however this is not realistic possible given the potential number of nodes and the nature of the networks.
For those wondering about the real world problem it goes as follows.
I have sets with a cardinality of 8, each item in the set has a value of 0-15. These sets are grouped in groups of 8. They have been grouped so that between all 8 sets a minimal amount of possible values 0-15 is used (typically the group of 8 sets will use between 6-8 of the possible 0-15 numbers with a few outliers each way).
Each of these groups has a transformation table which allows me to replace the real value in a set with a reference to the value, these transformation tables are 16 entries long.
This creates the opportunity to represent multiple sets with the same pattern of variance with a single set and allow the transformation tables to realize their real respective values.
[ 7, 7, 9, 9] [ 4, 4, 5, 5]
Becomes
[ 1, 1, 2, 2] with respective transformations (1=7, 2=9) (1=4, 2=5).
Of course as sets in a group get transformed they eat up entries in the transformation table reducing the ability for further transformations to occur. In the network problem the cost is associated with the number of additional entries I need to realize a transformation and the removal is when a transformation is no longer possible.
Additional factors to consider...
I am aware computational complexity theory and the fact that I am seeking an approximation or heuristic solution. Ideally from my knowledge of the cost between nodes and knowledge of possible connections I would like to create a small subset of paths from which I can test and take the best.
I resolved this issue by changing focus. Instead of focusing on convergence of sets i focused on convergence of individual items in the set.
The process needed to be completed several million times to identify and process the best then ultimately remove from the structure so the next best could be found. As such I took a few shortcuts but it works.
I created a cache of possible convergences, 8 possible indexes, 16 possible values. For each combination a hashset of sets conforming to this convergence was stored. If no sets conformed to the convergence then no hashset was created.
I then processed all possible convergences via combinations. The algorithm stops the combination process if the intersection of current convergences can not achieve a better result then currently stored best for this overall convergence. Best results are cached.
Each iteration cached convergence results are only recalculated if the underlying second set is altered and it has the possibility of beating current best. The order in which the convergence possibilities are calculated is sorted by maximum weight, thus when it hits a convergence possibility that cannot possibly beat best it terminates this iteration, takes the current best and starts again.