User:Realazthat/Notes/Scrap: Difference between revisions
< User:Realazthat | Notes
Content added Content deleted
No edit summary |
|||
Line 19: | Line 19: | ||
\in \left\{0,1\right\} |
\in \left\{0,1\right\} |
||
& = & |
& = & |
||
\begin{cases} |
|||
0 & \text{if }\left(u,v\right)\ |
0 & \text{if }\left(u,v\right) \notin E\\ |
||
1 & \text{if }\left(u,v\right)\ |
1 & \text{if }\left(u,v\right) \notin E\end{cases}\\ |
||
f\left( |
f\left(F,u,v\right) |
||
\in \left\{0,1\right\} |
\in \left\{0,1\right\} |
||
& = & |
& = & |
||
\begin{cases} |
\begin{cases} |
||
0 & \text{if } |
0 & \text{if }\left(u,v\right) \in F\\ |
||
1 & \text{if } |
1 & \text{if }\left(u,v\right) \notin F\end{cases}\\ |
||
c\left(C,E,p,q,r,s\right)\in\left\{ 0,1,2,3\right\} & = & b\left(E,C_{p-1},C_{q+1}\right)+b\left(E,C_{q},C_{s}\right)+b\left(E,C_{p},C_{r}\right) \\ |
c\left(C,E,p,q,r,s\right)\in\left\{ 0,1,2,3\right\} & = & b\left(E,C_{p-1},C_{q+1}\right)+b\left(E,C_{q},C_{s}\right)+b\left(E,C_{p},C_{r}\right) \\ |
||
d\left(C,E,F,p,q,r,s\right)\in\left\{ 0,1,2,3\right\} & = & f\left(E,F,C_{p-1},C_{q+1}\right)+f\left(E,F,C_{q},C_{s}\right)+f\left(E,F,C_{p},C_{r}\right)\\ |
d\left(C,E,F,p,q,r,s\right)\in\left\{ 0,1,2,3\right\} & = & -f\left(E,F,C_{p-1},C_{q+1}\right)+f\left(E,F,C_{q},C_{s}\right)+f\left(E,F,C_{p},C_{r}\right)\\ |
||
b,c,d,f \in O\left(1\right)\\ |
b,c,d,f \in O\left(1\right)\\ |
||
Line 107: | Line 107: | ||
</pre> |
</pre> |
||
== Better algorithm == |
|||
<math> |
|||
\begin{array}{lcl} |
|||
T_{q} |
|||
& = & |
|||
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
|||
\left[ |
|||
b(E,C_{p},C_{r})=0 |
|||
\right] |
|||
\right\}\\ |
|||
U_{q} |
|||
& = & |
|||
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
|||
\left[ |
|||
b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=1 |
|||
\right] |
|||
\right\}\\ |
|||
V_{q} |
|||
& = & |
|||
\left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} |
|||
\left[ |
|||
b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=0 |
|||
\right] |
|||
\right\}\\ |
|||
D_{q} |
|||
& = & |
|||
\left\{ v : (C_{q},v) \in E |
|||
\right\}\\ |
|||
H_{q} |
|||
& = & |
|||
\left\{ v \in D_{q} : f(E,F,v,C_{q})=0 |
|||
\right\}\\ |
|||
W(q) |
|||
& = & |
|||
\begin{cases} |
|||
W_{0}(q) & \text{if } b(E,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 |
|||
\end{cases}\\ |
|||
\end{array} |
|||
</math> |
Revision as of 21:54, 4 January 2011
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