¿Alguna vez ha tenido un requisito comercial que resultó ser un problema NP-Complete?

Question

La integridad de NP me parece una de esas cosas que es principalmente teórica y no realmente algo con lo que te encontrarás en un entorno de trabajo normal.

¿Tengo curiosidad por saber si alguien ha tenido algún problema en su trabajo que resultó ser NP-completo, y que el diseño necesitaba ser cambiado para acomodarlo?

Answer 1

Como han dicho los demás, la mochila (para empacar carga) y el problema de los vendedores ambulantes son probablemente los más comunes del mundo real. Problemas NP-completos.

Tiendo a encontrar problemas en el trabajo que no pueden probarse que son NP completos o incompletos porque no están muy bien definidos.

Answer 2

Cualquier tipo de herramienta de mapeo en la que necesite encontrar puntos de viaje óptimos entre más de dos ubicaciones puede, sin ningún cambio, convertirse en Problema NP-Complete

Answer 3

El problema de optimizar la recogida de olas desde un almacén es equivalente al Problema del vendedor ambulante .

Es decir, tiene N pedidos esperando ser recogidos, y desea encontrar los n mejores pedidos para minimizar la distancia recorrida y los diferentes lugares de selección visitados por un recolector.

Recientemente me encontré con este problema. Pusimos a prueba y usamos una aproximación que funcionará bien para el caso promedio, pero que a veces puede proporcionar resultados subóptimos.

Answer 4

Además, el problema de la mochila (que es NP-hard) aparece con bastante frecuencia. Es una trampa seductora para intentar optimizar las cosas.

Answer 5

Vale la pena señalar que existen técnicas de aproximación heurísticas para obtener "lo suficientemente bueno". respuestas para problemas de NP completo, como el recocido simulado y el recocido comprimido. Si puede reducir su problema de NP completo al problema del vendedor ambulante, puede utilizar estos enfoques. (Cualquier problema de NP completo puede reducirse a cualquier otro problema de NP completo, pero en realidad hacerlo a veces es un fastidio).

De todos modos, hay implementaciones de recocido simulado y recocido comprimido por ahí; uno de ellos es Djinni , que está escrito en C ++ y tiene enlaces de Python.

Answer 6

Estuve de acuerdo en escribir software para el padre de un amigo cuando era estudiante de primer año de universidad. Fue para programar recursos. No me di cuenta en ese momento, pero resultó ser un problema NP completo.

Afortunadamente, solo encontrar una solución era aceptable, no necesitaba encontrar la solución óptima. Fue divertido escribir heurísticas, en realidad un conjunto de ellas, que se podían cambiar mientras el programa se estaba ejecutando y tratando de resolver el problema.

Tuve una solución en verano, pero luego trabajé en nuevas versiones cada año sucesivo. Mis grandes planes para venderlo fracasaron. Yo era mejor desarrollador que comercializador.

Fue muy divertido y desde el principio me enseñó mucho sobre el mundo real del desarrollo (usuarios finales, recopilación de requisitos, pruebas, etc.), muchas de las cosas que NO obtienes en la universidad de CS.

Para responder a su pregunta, fue para un maestro que tuvo que programar a los estudiantes para recibir instrucción especial. Era un terapeuta del habla y audiólogo, pero podría aplicarse a cualquier campo similar. Tenía actividades existentes para maestros, aulas y estudiantes para trabajar y tenía que reunirse un número específico de veces por semana con los estudiantes. Es el problema de la mochila o cualquier otro problema de programación similar / equivalente.

Nuevamente, resultó que obtener una solución estaba bien, no teníamos que maximizar ni minimizar nada, solo teníamos que acomodar a todos los estudiantes.

Solo puedo recordar que no pude resolver los casos de prueba que solía ejecutar en escenarios, todos los problemas que proporcionó durante los años que resolvimos.

Nunca pude comercializarlo, principalmente porque no tenía idea de lo que estaba haciendo y no estaba seguro de cómo llegar a mi mercado / compradores.

Answer 7

El problema del vendedor ambulante es un ejemplo perfecto. El mismo tipo de problemas logísticos se aplican a las aerolíneas, las oficinas de correos y todo tipo de industrias.

Answer 8

Otro ejemplo es que las empresas con centros de distribución regionales, especialmente aquellas que entregan directamente al cliente (por ejemplo, Netflix), deben preocuparse por la familia de problemas NP-Complete conocidos como ubicación de la instalación .

De hecho, la idea de que los problemas de NP-Complete son relevantes en el mundo real se evidencia por el hecho de que los algoritmos de aproximación para ellos aparecen con tanta frecuencia en revistas de investigación operativa.

Answer 9

Hace unos años estaba trabajando en un programa de mapeo, como un Google Maps nativo. Puse pequeños marcadores en el mapa para ubicaciones, pero muchos marcadores estaban agrupados de cerca en ciertas ubicaciones. Mi jefe dijo "déjame hacerlo para que pueda arrastrar un poco los marcadores". (y tendría una línea o discurso-burbuja-puntero-cosa que va del marcador a la ubicación real).

Pensé que era una tontería hacer que el usuario hiciera esto, especialmente porque pasaría 5 minutos haciéndolo perfecto, y luego cambiaría el nivel de zoom, y entonces todo estaría mal.

Decidí intentar escribir una función para encontrar una manera de diseñar etiquetas de manera que se minimizara la distancia total de la pantalla desde cada etiqueta hasta su ubicación. Creo que en ese momento me convencí de que esto era NP completo, pero que el número de puntos podría ser lo suficientemente pequeño como para que todavía sea factible, al menos en muchos casos. (Recuerdo haber pensado que pasamos demasiado tiempo en clase en pruebas de integridad de NP, y no lo suficiente en soluciones alternativas: si su jefe quiere que se haga algo, no puede simplemente decir "NP duro, no lo hará" - todavía tienes que encontrar algo .)

Luego apareció Google Maps y simplemente salpicó todas las etiquetas una encima de la otra, lo que apesta totalmente (y lo maldigo todos los días), pero no puedo competir con sus otras características, así que me di por vencido. :-(