User:Zhan

From Speedclear Wiki
Jump to navigation Jump to search

DoA

Discrete formulation

What are the next starts i should choose to reduce gemstones type difference, the discrete optimization point of view.

Let us consider the gemstones as a vector y = (y1, y2, y3, y4) in N4, where the components respectively respresent the number of margonite gemstones, stygian gemstones, torment gemstones, titan gemstones.

Then, we consider successful runs by the following functions going from N4 to N4:

f1(x) = x + k(1, 2, 3, 4)

f2(x) = x + k(4, 1, 2, 3)

f3(x) = x + k(3, 4, 1, 2)

f4(x) = x + k(2, 3, 4, 1)

Where k = 2 in Hard Mode (HM), and where the functions respectively represent start city, start veil, start gloom, start foundry.


Now, let g be a finite number ni of composition of functions fi, (i in {1,...,4}). We consider g to be solution if it is the minimal number of composition which gives the minimum possible difference of gemstones. This gives the following minimization problem:

g* = argming (max(i, j) |gi(y) - gj(y)| + d||n||1), where d is small.

Let us set h(i,j)(y) = |gi(y) - gj(y)|. This is a polyhedral function with respect to n:

h(i,j)(n, y) = |yi - yj + k<D(i,j),n>|

where <., .> is the usual scalar product and D(i,j) is the difference of the lines i, j of the system matrix.

Continuous setting

Let us now consider z in R. The discrete problem is equivalent to this one:

minz z + <n, 1>

under:

z >= yi - yj + k<D(i,j),n>

z >= yj - yi + k<D(j,i),n>

for all couple (i,j) in {(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)}

We remark that each of these constraints are convex.

Computation of the solution

Due to the nature of the problem, it is possible to get the global solution numerically.

This was tested using Juniper.jl : https://github.com/lanl-ansi/Juniper.jl

Contact

In game character name Kunvie Zhan