from $\{0, 2, 3,\cdots, r\}$ according to $P(I=i)=p(i)$, $i=0, 2,\cdots, r$;

                 **If** $I>0$; Set $\pi(n+1-r)=I$ and $D=D^{'}_{I1}$, goto Step 6;

                 **Else** $I=0$; Set $k=k+1$

                      **If** $k<t$; Set $D=C$, goto Step 6; Otherwise goto Step 7;\
**Step 7:** $\widetilde{\operatorname{ham}}(A_G)=l^{-1}st^{-1}Br(C)$.\
The procedure of sampling elements in Step 6 is the same as SHC procedure except selecting an element with certain probability or rejection when $I=0$ is selected. The output $\mathcal{H}_i$, $1\leq i \leq s$, is accepted by the algorithm.\
\
**Theorem 7.** *Let $\mathcal {H}_1,\cdots,\mathcal {H}_s$ and $\widetilde{\operatorname{ham}}(A_G)$ be the output of Sub Algorithm II. If we set $N=Br(C)/\operatorname{ham}(C)$ in the same algorithm, and let $H$ be a random variable recovered from a random $\pi$ of Sub Algorithms II and $S$ denote the set of all the possible accepted hamiltonian cycles, then $$P(H=\mathcal {H}_1|H\in S)=W(\mathcal {H}_1)/W_H(G_C)$$ and $$P((1-\varepsilon)\operatorname{ham}(A_G)\leq
\widetilde{\operatorname{ham}}(A_G)\leq
(1+\varepsilon)\operatorname{ham}(A_G))\geq 1-\delta.$$*\
**Proof.** First, we check $p(0)\geq 0$ at each level of Step 6, which guarantees the proceeding of the algorithm. By the definition of $D^{'}_{i1}$ and $D_{i1}$, obviously, $Br(D^{'}_{i1})=Br(D_{i1})$. Using Lemma 5, it is easy to see $$\begin{split}
\sum\limits_{i=2}^nD(i,1)Br(D^{'}_{i1})&=\sum\limits_{i=2}^nD(i,1)Br(D_{i1})\\
&\leq \sum\limits_{i=1}^nD(i,1)Br(D_{i1})\\
&\leq Br(D).
\end{split}$$ Hence $p(0)\geq 0$. Suppose $\mathcal{H}_1=HR(j)$, $j=(j_1,\cdots,j_n)$. Following the path in which $\mathcal {H}_1$ is selected, and using the 