AtmaWeapon / FFXIVSynthSolver

BSD 2-Clause "Simplified" License
0 stars 1 forks source link

Investigate dynamic programming to unequivocally solve every state #3

Closed AtmaWeapon closed 10 years ago

AtmaWeapon commented 10 years ago

The advantages of this approach are that it is O(n*m) where n is the number of states and m is the number of abilities. The decision tree approach is more like O(n^m) because it involves heuristics, exponentially growing trees, etc.

The disadtanvage of this approach is that n is on the order of a few billion, at best. The number of states can be reduced by various observations and simplifications. For example, D must be a multiple of 10, Progress must be at least that which is comptued by the progress formula, similarly for Quality. This should drastically reduce the number of states to examine, but it's not clear if it will be enough to make it tractable.

It's worth pointing out that this approach is incompatible with abilities such as Tricks of the Trade, since it makes the order in which you must solve states unclear.

AtmaWeapon commented 10 years ago

Unnecessary after recent improvements to algorithm.