algorithm - sirve - Minimizando la suma ponderada

para que sirve la media ponderada

Question

Me encontré con este problema bastante recientemente. Supongamos que hay n puntos en el eje x, x [0], x [1] .. x [n-1]. Deje que el peso asociado con cada uno de estos puntos sea w [0], w [1] .. w [n-1]. Comenzando desde cualquier punto entre 0 y n-1, el objetivo es cubrir todos los puntos de manera que la suma de w [i] * d [i] se minimice donde d [i] es la distancia recorrida para llegar al punto ith desde el punto de partida.

Ejemplo:
Supongamos que los puntos son: 1 5 10 20 40
Supongamos que los pesos son: 1 2 10 50 13
Si elijo comenzar en el punto 10 y elijo moverme al punto 20, luego a 5, luego a 40 y finalmente a 1, la suma ponderada se convertirá en 10 * 0 + 50 * (10) + 2 * (10 + 15) + 13 * (10 + 15 + 35) + 1 * (10 + 15 + 35 + 39).

Intenté resolverlo utilizando un enfoque codicioso comenzando desde el punto que tiene el peso máximo asociado y avanzo al segundo punto de peso máximo, y así sucesivamente. Pero el algoritmo no funciona. ¿Puede alguien darme consejos sobre el enfoque que debe tomarse para resolver este problema?

Answer 1

Hay un hecho muy importante que conduce a un algoritmo de tiempo polinomial:

Como los puntos están ubicados en algún eje, generan un gráfico de ruta, lo que significa que por cada 3 vértices v1,v2,v3 , si v2 está entre v1 y v3 , la distancia entre v1 y v3 es igual a la distancia entre v1 y v2 más la distancia entre v2 y v3 . por lo tanto si, por ejemplo, comenzamos en v1 , el obj. el valor de función de una ruta que va primero a v2 y luego a v3 siempre será menor que el valor de la ruta que primero va a v3 y luego a v2 porque:

value of the first path = w[2]*D(v1,v2)+W[3]*(D(v1,v2)+D(v2,v3))

value of the second path = w[3]*D(v1,v3)+W[2]*((v1,v3)+D(v3,v2)) = w[3]*D(v1,v2)+w[3]*D(v2,v3)+w[2]*(D(v1,v2)+2*D(v3,v2))

Si restamos el primer valor de ruta del segundo, nos queda w[2]*2*D(v3,v2) que es igual o mayor que 0 a menos que tenga en cuenta los pesos negativos.

Todo esto significa que si nos encontramos en un cierto punto, siempre hay solo 2 opciones que debemos considerar: ir al punto no visitado más cercano a la izquierda o al punto no visitado más cercano a la derecha.

Esto es muy significativo ya que nos deja con 2^n caminos posibles en lugar de n! posibles caminos (como en el Problema de Vendedor Viajero).

La resolución de la ruta TSP / hamiltoniana de peso mínimo en los gráficos de ruta se puede hacer en tiempo polinomial utilizando la programación dinámica, debe aplicar exactamente el mismo método pero modificar la forma en que calculó la función objetivo.

Como no conoce el vértice de inicio, deberá ejecutar este algoritmo en tiempo, cada vez que comience desde un vértice diferente, lo que significa que el tiempo de ejecución se multiplicará por n .

Answer 2

Tal vez deberías explicar lo que quieres decir con que el algoritmo "no funciona" . La idea básica del enfoque codicioso que describes me parece factible. ¿Quiere decir que el enfoque codicioso no necesariamente encontrará la solución óptima? Como se señaló en los comentarios, este podría ser un problema NP completo, aunque, sin duda, habría que analizarlo más a fondo: cierta programación dinámica, y tal vez algunas sumas de prefijos para los cálculos de distancia podrían conducir a un polinomio solución de tiempo también.

Rápidamente implementé la solución codiciosa en Java (espero haber entendido todo correctamente ...)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MinWeightSum
{
    public static void main(String[] args)
    {
        double x[] = { 1, 5, 10, 20, 40 };
        double w[] = { 1, 2, 10, 50, 13 };

        List<Integer> givenIndices = Arrays.asList(2, 3, 1, 4, 0);
        Path path = createPath(x, w, givenIndices);
        System.out.println("Initial result "+path.sum);

        List<Integer> sortedWeightIndices =
            computeSortedWeightIndices(w);
        Path greedyPath = createPath(x, w, sortedWeightIndices);
        System.out.println("Greedy result  "+greedyPath.sum);

        System.out.println("For "+sortedWeightIndices+" sum "+greedyPath.sum);
   }

    private static Path createPath(
        double x[], double w[], List<Integer> indices)
    {
        Path path = new Path(x, w);
        for (Integer i : indices)
        {
            path.append(i);
        }
        return path;
    }


    private static List<Integer> computeSortedWeightIndices(final double w[])
    {
        List<Integer> indices = new ArrayList<Integer>();
        for (int i=0; i<w.length; i++)
        {
            indices.add(i);
        }
        Collections.sort(indices, new Comparator<Integer>()
        {
            @Override
            public int compare(Integer i0, Integer i1)
            {
                return Double.compare(w[i1], w[i0]);
            }
        });
        return indices;
    }

    static class Path
    {
        double x[];
        double w[];

        int prevIndex = -1;
        double distance;
        double sum;

        Path(double x[], double w[])
        {
            this.x = x;
            this.w = w;
        }

        void append(int index)
        {
            if (prevIndex != -1)
            {
                distance += Math.abs(x[prevIndex]-x[index]);
            }
            sum += w[index] * distance;
            prevIndex = index;
        }
    }
}

La secuencia de índices que describió en el ejemplo arroja la solución

For [2, 3, 1, 4, 0] sum 1429.0

El enfoque codicioso que describiste da

For [3, 4, 2, 1, 0] sum 929.0

La mejor solución es

For [3, 2, 4, 1, 0] sum 849.0 

que encontré comprobando todas las permutaciones de índices (Esto no es factible para n mayores, por supuesto)

Answer 3

Supongamos que está en medio de una solución y que ha recorrido la distancia D hasta el momento. Si vas a una distancia mayor xy ves un punto con un peso w, te cuesta (D + x) w. Si vas más lejos y ves un punto con peso v te cuesta (D + x + y) v .. Si sumas todo esto, hay un componente que depende de la ruta que tomes después de la distancia D: xw + xv + yv + ..., y hay un componente que depende de la distancia D y la suma de los pesos de los puntos que necesitas llevar: D (v + w + ...). Pero el componente que depende de la distancia D no depende de nada más que la suma de los pesos de los puntos que necesita visitar, por lo que es fijo, en el sentido de que es el mismo independientemente de la ruta que tome después de la distancia recorrida. RE.

Siempre tiene sentido visitar los puntos que pasamos cuando los visitamos, por lo que el mejor camino comenzará con un solo punto (posiblemente en el borde del conjunto de puntos que se visitarán y posiblemente en el centro) y luego se ampliará a un punto intervalo de puntos visitados, y luego expanda esto para visitar todos los puntos. Para precalcular los costos relativos de visitar todos los puntos fuera del intervalo, solo necesitamos conocer la posición actual y el tamaño del intervalo, no la distancia recorrida hasta el momento.

Entonces, un enfoque de programación dinámico, costoso pero polinomial, tiene como estado la posición actual (que debe ser uno de los puntos) la posición del primer punto no visitado, a la izquierda de la posición actual, y la posición, si la hay, del primer punto no visitado a la derecha del punto actual. Hay como mucho dos puntos que deberíamos considerar visitar a continuación: el punto a la derecha del punto actual y el punto a la izquierda del punto actual. Podemos calcular el costo de estas dos alternativas observando los costos pre calculados para los estados con menos puntos restantes, y almacenar el mejor resultado como el mejor costo posible a partir de este punto. Podríamos calcular estos costos bajo la ficción de que D = 0 en el momento en que alcanzamos el punto actual. Cuando buscamos los costos almacenados, también se almacenan bajo esta suposición (pero con D = 0 en su punto actual, no nuestro punto actual), pero sabemos la suma de los pesos de los puntos restantes en esa etapa, de modo que podemos agregar a el costo almacenado esa suma de pesos multiplicada por la distancia entre nuestro punto actual y el punto que estamos buscando cuesta para compensar esto.

Eso le da un costo O (n ^ 3), porque está construyendo una tabla con celdas O (n ^ 3), y cada celda es producto de un proceso relativamente simple. Sin embargo, dado que nunca tiene sentido pasar células sin visitarlas, el punto actual debe estar al lado de uno de los dos puntos en cada extremo del intervalo, por lo que debemos considerar solo O (n ^ 2) posibilidades, lo que reduce el costo hasta O (n ^ 2). Una ruta en zig-zag como (0, 1, -1, 2, -2, 3, -3, 4, -4 ...) podría ser la mejor solución para pesos adecuadamente extraños, pero sigue siendo así, incluso por ejemplo, al pasar de -2 a 3, ese -2 a es el punto más cercano aún no tomado entre los dos puntos 3 y -3.

He puesto una implementación de java intentada en http://www.mcdowella.demon.co.uk/Plumber.java . El arnés de prueba verifica esta versión de DP con una versión (lenta) casi exhaustiva para varios casos de prueba generados aleatoriamente de hasta 12. Incluso puede que no esté completamente libre de fallas, pero con suerte llenará los detalles.