¿Cuál es la forma más insidiosa de plantear este problema?

Question

Mi mejor tiro hasta ahora:

  

Un vehículo de entrega debe realizar una serie de entregas (d ₁ , d ₂ , ... d _n ) y puede hágalo en cualquier orden; en otras palabras, todas las permutaciones posibles del conjunto D = {d ₁ , d ₂ , ... d _n } son soluciones válidas, pero la solución particular debe determinarse antes de abandonar la estación base en un extremo de la ruta (imagine que los paquetes deben cargarse en el LIFO del vehículo, por ejemplo).

     

Además, el costo de las diversas permutaciones no es el mismo. Se puede calcular como la suma de los cuadrados de la distancia recorrida entre d _{i -1} y d _i , donde d ₀ se considera la estación base, con la advertencia de que cualquier segmento que implique un cambio de dirección cuesta 3 veces más (imagínese que esto ocurre en un ferrocarril o un tubo neumático, y retroceder interrumpe otro tráfico).

     

Dado el conjunto de entregas D representadas como su distancia desde la estación base (entonces abs(d_i -d _j ) es la distancia entre dos entregas) y un iterador permutaciones (D) que producirá cada permutación en sucesión, encuentre un permutación que tiene un costo menor o igual al de cualquier otra permutación.

Ahora, una implementación directa de esta descripción podría conducir a un código como este:

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

Que es O (n * n! ^ 2), p. bastante horrible, especialmente en comparación con el O (n log (n)) que alguien con perspicacia encontraría, simplemente ordenando D.

Mi pregunta: ¿puede llegar a una descripción plausible del problema que naturalmente llevaría a los incautos a una implementación peor (o diferente) de un algoritmo de clasificación?

Answer 1

Supongo que está utilizando esta pregunta para una entrevista para ver si el solicitante puede notar una solución simple en una pregunta aparentemente compleja.

[Esta suposición es incorrecta - MarkusQ]

Usted da demasiada información.

La clave para resolver esto es darse cuenta de que los puntos están en una dimensión y que una clasificación es todo lo que se requiere. Para hacer esta pregunta más difícil, oculte este hecho tanto como sea posible.

La pista más grande es la fórmula de la distancia. Introduce una penalización por cambiar de dirección. Lo primero que me viene a la mente es minimizar esta penalización. Para eliminar la penalización, tengo que ordenarlos en una determinada dirección, este orden es el orden natural.

Quitaría la penalización por cambiar de dirección, es demasiado regalar.

Otra pista importante son los valores de entrada al algoritmo: una lista de enteros. Dales una lista de permutaciones, o incluso todas permutaciones. Eso los hace pensar que en realidad se podría esperar un algoritmo O (n!).

Lo expresaría como:

  

Dada una lista de todos los posibles   permutaciones de n ubicaciones de entrega,   donde cada permutación de entregas   (d ₁ , d ₂ , ...,   d _n ) tiene un costo definido por:

     

     

Devuelve la permutación P tal que el   el costo de P es menor o igual a cualquier   otra permutación.

Todo lo que realmente hay que hacer es leer en la primera permutación y ordenarlo.

Si construyen un solo ciclo para comparar los costos, pregúnteles cuál es el tiempo de ejecución grande de su algoritmo donde n es el número de ubicaciones de entrega (Otra trampa).

Answer 2

Esta no es una respuesta directa, pero creo que se necesita más aclaración.

¿Se permite que d _i sea negativo? Si es así, ordenar solo no es suficiente, por lo que puedo ver.

Por ejemplo:

d ₀ = 0

entregas = (-1,1,1,2)

Parece que la ruta óptima en este caso sería 1 > 2 > 1 > -1 .

Editar: esta podría no ser la ruta óptima, pero ilustra el punto.

Answer 3

PUEDES reformularlo, habiendo encontrado primero la solución óptima, como

" Dame una prueba de que la siguiente convicción es la más óptima para el siguiente conjunto de reglas, donde óptimo significa que el número más pequeño resulta de la suma de todos los costos de la etapa, teniendo en cuenta que todas las etapas (A ..Z) debe estar presente una sola vez.

Convención:

A->C->D->Y->P->...->N

Costos de la etapa:

A->B = 5,
B->A = 3,
A->C = 2,
C->A = 4,
...
...
...
Y->Z = 7,
Z->Y = 24."

Eso debería mantener a alguien ocupado por un tiempo.

Answer 4

Esto me recuerda el Problema de la mochila , más que el Vendedor viajero. Pero el Knapsack también es un problema NP-Hard, por lo que puede engañar a las personas para que piensen en una solución demasiado compleja usando programación dinámica si correlacionan su problema con el Knapsack. Donde el problema básico es:

  

se puede lograr un valor de al menos V   sin exceder el peso W?

Ahora el problema es que se puede encontrar una solución bastante buena cuando V es única, sus distancias, como tales:

  

El problema de la mochila con cada tipo de   elemento j que tiene un valor distinto por   unidad de peso (vj = pj / wj) es   considerado uno de los más fáciles   Problemas NP-completos. De hecho empírico   la complejidad es del orden de O ((log   n) 2) y pueden surgir problemas muy grandes   resuelto muy rápidamente, p. en 2003 el   tiempo promedio requerido para resolver   instancias con n = 10,000 estaba por debajo de 14   milisegundos utilizando productos personales   computadoras 1 .

Por lo tanto, es posible que desee indicar que varias paradas / paquetes pueden compartir el mismo vj, invitando a las personas a pensar en la solución realmente difícil para:

  

Sin embargo en el   caso degenerado de múltiples elementos   compartiendo el mismo valor vj se convierte   mucho más difícil con el extremo   caso donde vj = constante siendo el   problema de suma de subconjuntos con una complejidad   de O (2N / 2N).

Entonces, si reemplaza el peso por valor por distancia por valor, y declara que varias distancias podrían compartir los mismos valores, degenerar, algunas personas podrían caer en esta trampa.

Answer 5

¿No es solo el (NP-Hard) Problema de vendedor ambulante ? No parece probable que lo va a hacer mucho más difícil.

Tal vez redactando el problema para que el algoritmo real no esté claro, p. ej. describiendo los caminos como líneas de ferrocarril de un solo carril para que la persona tenga que inferir del conocimiento del dominio que el retroceso es más costoso.

¿Qué hay de describir la pregunta de tal manera que alguien tenga la tentación de hacer comparaciones recursivas? "¿Puede acelerar el algoritmo utilizando el subconjunto máximo óptimo de sus mejores (hasta ahora) resultados"?

Por cierto, ¿cuál es el propósito de esto? Parece que la intención es torturar a los entrevistados.

Answer 6

Debe ser más claro sobre si el camión de reparto tiene que regresar a la base (por lo que es un viaje de ida y vuelta) o no. Si el camión regresa , entonces una clasificación simple no produce la ruta más corta, porque el cuadrado del retorno desde el punto más alejado hasta la base cuesta mucho. Perder algunos saltos en el camino 'fuera' y usarlos en el camino de regreso resulta ser más barato.

Si engañas a alguien para que responda mal (por ejemplo, al no darle toda la información), ¿es su tontería o tu engaño lo que lo ha causado?

¿Cuán grande es la sabiduría de los sabios, si no hacen caso de las mentiras de su ego?