User:Realazthat/Notes/Scrap: Difference between revisions
Content added Content deleted
(→Du) |
|||
| Line 109: | Line 109: | ||
== Better algorithm == |
== Better algorithm == |
||
As we iterate over the different possible values for <math>q</math>, there are incrementally more possibilities for <math>(r,s)</math>. Each selection of <math>(r,s)</math> implies a possible breakpoint for <math>(p,r)</math>. |
|||
| ⚫ | |||
For each q, for all the valid (r,s) for that q, <math>T_{q}</math> will track those that result in no breakpoint for (p,r). |
|||
| ⚫ | |||
| ⚫ | |||
T_{q} |
T_{q} |
||
= |
|||
\left\{ |
\left\{ C_{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
||
\left[ |
\left[ |
||
b(E,C_{p},C_{r})=0 |
b(E,C_{p},C_{r})=0 |
||
\right] |
\right] |
||
\right\} |
\right\} |
||
</math> |
|||
<math>U_{q}</math> will track those s that result in a breakpoint that is a former main breakpoint. |
|||
<math> |
|||
U_{q} |
U_{q} |
||
= |
|||
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
||
\left[ |
\left[ |
||
b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=1 |
b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=1 |
||
\right] |
\right] |
||
\right\} |
\right\} |
||
</math> |
|||
<math> |
|||
V_{q} |
V_{q} |
||
= |
|||
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
||
\left[ |
\left[ |
||
b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=0 |
b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=0 |
||
\right] |
\right] |
||
\right\} |
\right\} |
||
D_{q} |
D_{q} |
||
= |
|||
\left\{ v : (C_{q},v) \in E |
\left\{ v : (C_{q},v) \in E |
||
\right\} |
\right\} |
||
H_{q} |
H_{q} |
||
= |
|||
\left\{ v \in D_{q} : f(E,F,v,C_{q})=0 |
\left\{ v \in D_{q} : f(E,F,v,C_{q})=0 |
||
\right\} |
\right\} |
||
</math> |
|||
<math> |
|||
W(q) |
|||
| ⚫ | |||
W(q) \in \left\{0,1,2,3,\infty\right\} |
|||
& = & |
& = & |
||
\begin{cases} |
\begin{cases} |
||
| Line 149: | Line 160: | ||
W_{1}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(E,F,C_{p-1},C_{q+1}) = 0\text{,}\\ |
W_{1}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(E,F,C_{p-1},C_{q+1}) = 0\text{,}\\ |
||
W_{2}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(E,F,C_{p-1},C_{q+1}) = 1 |
W_{2}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(E,F,C_{p-1},C_{q+1}) = 1 |
||
\end{cases}\\ |
|||
W_{0} |
|||
& = & |
|||
\begin{cases} |
|||
0 & \text{if } \left|A_{q} / D_{q}\right| \not= 0 \text{,} |
|||
\end{cases}\\ |
\end{cases}\\ |
||
\end{array} |
\end{array} |
||