Algoritmo aproximado para encontrar p-medianas

El método heurístico para encontrar la p-mediana es el siguiente: los vértices se seleccionan aleatoriamente , forman el conjunto inicial , aproximándose al conjunto p-mediana . Luego se averigua si algún vértice puede reemplazar al vértice (como vértice mediano), para lo cual se construye un nuevo conjunto y se comparan las relaciones de transmisión . Si , entonces reemplace con , que se aproxima mejor al conjunto p-mediana . Luego, el conjunto se analiza de manera similar, y así sucesivamente, hasta que se construye el conjunto ', que no se puede cambiar de acuerdo con el principio anterior. $pags$ $S$ $X_{p}^{*}$ $x_{j}\in X\setminus S$ ${\ Displaystyle x_ {i} \ en S}$ $S^{*}=(S\cup {x_{j)))\setminus {x_{i}}$ ${\ estilo de visualización \ sigma (S ^ {*})}$ ${\ estilo de visualización \ sigma (S)}$ ${\ estilo de visualización \ sigma (S^{*}) <\ sigma (S)}$ $S$ ${\ estilo de visualización S^{*}}$ $X_{p}^{*}$ ${\ estilo de visualización S^{*}}$ $S$

Algoritmo

Paso 1. Elija algún conjunto de p vértices como una aproximación inicial a la p-mediana. Y llamemos a todos los vértices "no probados". $S$ $x_{i}\notin S$

Paso 2. Tome un vértice arbitrario "no probado" y para cada vértice calcule el "incremento" Δij correspondiente al reemplazo del vértice por el vértice , es decir, calcule . ${\ Displaystyle x_ {i} \ en S}$ $x_i$ ${\ Displaystyle x_ {j}}$ $\Delta _{ij}=\sigma (S)-\sigma ((S\cup {x_{j)))\setminus {x_{i)))$

Paso 3. Encuentra por todos . $\Delta _{i^{1}j}=máx[\Delta _{ij}]$ ${\ Displaystyle x_ {i} \ en S}$

a) Si , llame al vértice "probado" y vaya al paso 2. ${\ estilo de visualización \ Delta _ {i ^ {1} j} \ leq 0}$ ${\ Displaystyle x_ {j}}$

b) Si , entonces , llame al vértice "probado" y vaya al paso 2. ${\ estilo de visualización \ Delta _ {i ^ {i} j} \ geq 0}$ $S\obtiene (S\cup {x_{j}})\setminus {x_{i}}$ $x_{j}$

Paso 4. Repita los pasos 2 y 3 hasta que se prueben todos los vértices . Este procedimiento está diseñado como un ciclo. Si, durante el último ciclo, no hay reemplazos de vértices en el paso 3(a), vaya al paso 5. De lo contrario, es decir, si se ha hecho algún reemplazo, llame a todos los vértices "no probados" y regrese al paso 2. $X\setminus S$

Paso 5. Detente. El conjunto actual es una aproximación adecuada del conjunto p-mediana . $S$ $X_{p}^{*}$

Ejemplo

Es fácil ver que el algoritmo anterior no da la respuesta óptima en todos los casos. Consideremos un ejemplo (los números cerca de los bordes son iguales a los costos de borde correspondientes, todos los vértices tienen el mismo peso unitario):

Si buscamos la mediana de 2 y tomamos {x3, x6} como el conjunto inicial S con la relación de transmisión , entonces ningún reemplazo de un solo vértice conduce a un conjunto con una relación de transmisión más pequeña. Sin embargo, el conjunto {x3, x6} no es la mediana de 2 de este gráfico, porque hay dos conjuntos de mediana de 2 con razón 7: {x1, x4} y {x2, x5}. ${\ estilo de visualización \ sigma (S) = 8}$

Literatura

Christofides N. Teoría de grafos. Enfoque algorítmico. — M .: Mir, 1978.
E. Mainik. Algoritmos de optimización para redes y grafos. — M .: Mir, 1981. — 324 p.

Algoritmo aproximado para encontrar p-medianas

Algoritmo

Ejemplo

Literatura

Enlaces