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...
- if a value(s) in a both sets can be represented using an existing transformation entry (they need to correspond to the same entry in the table (7=value in set 1, 7=value in set 2) then the cost of those value(s) is free.
- entries in the transformation table that extend beyond the total individual numbers used in a group of sets can be used as wild cards (basically the transformation table can reference the same value multiple times as long as their remains enough entries to create at least one reference for all values).
- Each possible original value must be referenced in the transformation table at least once (obviously we need to be able to reference it to reproduce the original set).
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.