Anonymous user
User:Realazthat/Notes/Scrap: Difference between revisions
→Better algorithm
No edit summary |
|||
| (12 intermediate revisions by the same user not shown) | |||
Line 177:
<math>
\min_{q \in C} W(C,F,E,q)
</math>
<math>
W(C,F,E,q) \in \left\{0,1,2,3,\infty\right\}
=
\begin{cases}
Line 187 ⟶ 192:
<math>
W_{0}\left(C,F,E,q\right) \in \left\{0,1,2,\infty\right\}
=
\begin{cases}
0 & \text{if } \left|T_{q}
1 & \text{else if }
\left(
\left|T_{q} \cap H_{q} \right| \not=0
\vee
\left| V_{q}
\right) \text{,}\\
2 & \text{else if }
Line 208 ⟶ 213:
<math>
W_{1}\left(C,F,E,q\right) \in \left\{1,2,3,\infty\right\}
=
\begin{cases}
Line 216 ⟶ 221:
\left| T_{q} \cap D_{q} \right| \not=0
\vee
\left| U_{q}
\vee
\left| V_{q}
\right) \text{,}\\
3 & \text{else if }
Line 230 ⟶ 235:
<math>
W_{2}\left(C,F,E,q\right) \in \left\{2,3,\infty\right\}
=
\begin{cases}
2 & \text{if } \left|T_{q} \cap H_{q}\right| \not= 0 \vee \left( |
3 & \text{else if }
\left(
\left| U_{q} \cap H_{q} \right| \not=0
\vee
\left| V_{q}
\right) \text{,}\\
\infty & \text{otherwise}
\end{cases}
</math>
== Perform an operation ==
New edges:
<math>
N_{e}(C,p,q,r,s) = \left\{ (C_{p},C_{r}), (C_{q},C_{s}), (C_{p-1},C_{q+1
</math>
Broken edges:
<math>
B_{e}(C,p,q,r,s) = \left\{ (C_{p-1}, C_{p}), (C_{q},C_{q+1}) (C_{r}, C_{s}) \right\}
</math>
Next cycle:
<math>
C^{2}\left(C,M,E_{e},p,q,r,s\right) =
\begin{cases}
C^{2_{pq}}(C,p,q,r,s) & \text{if } b(C_{p-1},C_{q+1}) = 1 \wedge f(C_{p-1},C_{q+1}) = 0 \text{,}\\
C^{2_{pr}}(C,p,q,r,s) & \text{else if } b(C_{p},C_{r}) = 1 \wedge f(C_{p},C_{r}) = 0 \text{,}\\
C^{2_{qs}}(C,p,q,r,s) & \text{else if } b(C_{q},C_{s}) = 1 \wedge f(C_{q},C_{s}) = 0 \text{,}\\
C^{2_e}(C,p,q,r,s,m \in M \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) )) & \text{else if } M \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) ) \not= \emptyset\\
C^{2_e}(C,p,q,r,s,e \in E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) )) & \text{else if } E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) ) \not= \emptyset\\
C & \text{otherwise}
\end{cases}
</math>
<math>
C^{2_{pq}}(C,p,q,r,s) =
\begin{cases}
< [C_{q+1}, C_{r}], [C_{p},C_{q}], [C_{s}, C_{p-1}] > & \text{if } (r < s) \text{,}\\
< [C_{q+1}, C_{s}], [C_{q},C_{p}], [C_{r}, C_{p-1}] > & \text{if } (r > s) \text{,}\\
\end{cases}
</math>
<math>
C^{2_{pr}}(C,p,q,r,s) =
\begin{cases}
< [C_{p},C_{q}], [C_{s}, C_{p-1}], [C_{q+1}, C_{r}] > & \text{if } (r < s) \text{,}\\
< [C_{r}, C_{p-1}], [C_{q+1}, C_{s}], [C_{q},C_{p}] > & \text{if } (r > s) \text{,}\\
\end{cases}
</math>
<math>
C^{2_{qs}}(C,p,q,r,s) =
\begin{cases}
< [C_{s}, C_{p-1}], [C_{q+1}, C_{r}], [C_{p},C_{q}] > & \text{if } (r < s) \text{,}\\
< [C_{q},C_{p}], [C_{r}, C_{p-1}], [C_{q+1}, C_{s}] > & \text{if } (r > s) \text{,}\\
\end{cases}
</math>
<math>
E_{e}^{2}(E_{e},C,p,q,r,s) =
E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s))
</math>
<math>
M^{2}(M,C,p,q,r,s) =
(M \backslash B_{e}(C,p,q,r,s)) \cap N_{e}(C,p,q,r,s)
</math>
<math>
F \cap M^{2}(M,C,p,q,r,s)
</math>
| |||