Dos peones en un grafo completo

Question

Disponemos de un completo gráfico de $G = \langle V,E\rangle$ con los no-valores negativos en los bordes. Deje $C = \{v_1,v_2,\ldots,v_n\}$ ser una colección ordenada de $G$'s de vértices. Al principio tenemos dos peones en $v_1$. Puede mover los peones siguiendo estas reglas:

• Cada vez que se mueve sólo un peón
• peón de pie en $v_i$ sólo se puede ir a $v_j$ fib $j \ge i$ - (por lo que sólo puede mover un vértice que es más de lo que en $C$)
• Cada vértice tiene que ser visitado por al menos un peón
• Después de la última mover los peones debe estar de pie en $v_n$

¿Cuál es el óptimo algoritmo de determinación de la suma más pequeña de los visitó los bordes?

Answer 1

Dado pesos $w(i,j)$ de las aristas $v_iv_j$. Para $1\le i\le j\le n$ deje $F(i,j)$ el valor de la mínima suma de un movimiento válido secuencia de los peones de $(v_1,v_1)$ $(v_i,v_j)$tal que $v_1,\ldots v_j$ han sido visitados. Entonces tenemos $$\tag1F(j,j)=\min\{F(i,j)+w(i,j)\mid 1\le i<j\}$$ y $$\tag2\begin{align}F(i,j)=\min\bigl\{&F(i,j-1)+w(j-1,j),\\&\min\{\,F(k,j)+w(k,i) \mid 1\le k<i\,\}\bigr\}\end{align}$$ si $i<j$. Podemos ver $(1)$ como caso especial de $(2)$ si estamos de acuerdo en que con $F(i,j-1)+w(j-1,j)=+\infty$ si $i=j$. Estamos buscando a $F(n,n)$. Computación todos los $F$ valores tarda $O(n^3)$.

(Ciertamente, no es posible ser más rápido que el $O(n^2)$ porque es necesario mirar casi cada borde de peso al menos una vez)

---

Una mejora sobre el anterior es para hacer una $A^*$ buscar: permite a $Q$ ser una prioridad de la cola para las entradas de $(i,j,s)$$i,j\in\{1,\ldots,n\}$$s\ge0$, ordenados por $s$, y deje $A$ una matriz.

1. Inicialmente, el conjunto de $A(i,j)\leftarrow0$$1\le i\le j\le n$. Inserte $(1,1,0)$ a $Q$.
2. Pop $(i,j,s)$ con un mínimo de $s$$Q$.
3. Si $i=j=n$, terminar con $s$ como resultado
4. Si $i>j$, swap $i\leftrightarrow j$.
5. Si $A(i,j)=1$ regresar al paso 2.
6. Set $A(i,j)\leftarrow 1$. Para $i+1\le k\le \min\{j+1,n\}$, inserte $(k,j,s+w(i,k))$ a $Q$
7. Si $j<n$, inserte $(i,j+1,s+w(j,j+1))$ a $Q$
8. Volver al paso 2

Con un adecuado priotrity cola de estructura (por ejemplo, de Fibonacci del montón), mejor teneduría de libros acerca de las entradas duplicadas en la cola, y el uso de la disminución de clave de operación, este algoritmo debe tener tiempo de ejecución $O(n^2\log n)$.