|
|
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\{ 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})=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} |
Du
Naive algorithm
newedgdes(C,p,q,r,s):
return { (C[p-1],C[q+1]), (C[q],C[s]), (C[p], C[r]) }
countbps(E,NE):
newbps = 0
for ( ne in NE )
if ( ne !in E )
++newbps
return newbps
countmainbps(F,E,NE):
newmainbps = 0
for ( ne in NE )
if ( ne !in E && ne in F )
++newmainbps
return newmainbps
m(C,F,E,p):
min = infinity
n = |C|
for ( q in range(p,p-2) )
for ( s in range( q + 2, p ) )
r = s - 1
for ( i in range(2) )
NE = newedges(C,p,q,r,s)
if ( |NE| != 0 )
newbps = countbps(F,E,NE)
newmainbps = countmainbps(F,E,NE)
if ( newbps == 0 || newmainbps > 0 )
min = newbps < min ? newbps : min
swap(r,s)
return min
Better algorithm
As we iterate over the different possible values for , there are incrementally more possibilities for . Each selection of implies a possible breakpoint for .
For each q, for all the valid (r,s) for that q, will track those that result in no breakpoint for (p,r).
will track those s that result in a breakpoint that is a former main breakpoint.