User:Realazthat/Notes/Scrap: Difference between revisions
< User:Realazthat | Notes
Content added Content deleted
No edit summary |
No edit summary |
||
Line 57: | Line 57: | ||
\end{array} |
\end{array} |
||
</math> |
</math> |
||
===Naive algorithm=== |
|||
<math> |
|||
m\left(C,F,E\right) \in O\left(\left|n\right|^2\right) |
|||
</math> |
|||
<pre> |
|||
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): |
|||
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 |
|||
</pre> |
Revision as of 17:48, 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): 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