NP-completeness me parece una de esas cosas que en su mayoría son solo teóricas y no son realmente algo con lo que te encuentres en un entorno de trabajo normal.¿Alguna vez ha tenido un requisito comercial que resultó ser un problema NP-Complete?
Así que estoy un poco curioso si alguien alguna vez se encuentra con un problema en su trabajo que resultó ser NP-completo, y que el diseño necesita ser cambiado para acomodarlo?
Como han dicho los otros, la mochila (para el embalaje de la carga) y el problema de los vendedores ambulantes son probablemente los problemas NP-completos más comunes del "mundo real".
Tiendo a tener problemas en el trabajo que no pueden ser NP completos o incompletos porque no están muy bien definidos.
El problema del vendedor ambulante es un ejemplo perfecto. El mismo tipo de problemas logísticos se aplican a las líneas aéreas, oficinas postales y todo tipo de industrias.
Cualquier tipo de herramienta de mapeo donde tiene que encontrar los puntos óptimos de desplazamiento entre más de dos ubicaciones pueda, sin ningún cambio convertirse en un NP-Complete problem
El problema de optimizar fase de picking de un almacén es equivalente a la Travelling Salesman problem.
Es decir, tiene N-pedidos esperando ser recogidos, y desea encontrar los n mejores pedidos para minimizar la distancia recorrida y las diferentes ubicaciones de picking visitadas por un selector.
Hace poco me encontré con este problema. Punteamos y utilizamos una aproximación que funcionará bien para el caso promedio, pero a veces puede proporcionar resultados subóptimos.
Además, el problema de la mochila (que es NP-hard) se muestra con bastante frecuencia. Es una trampa seductora para tratar de optimizar las cosas.
Acepté escribir software para el padre de un amigo cuando era un estudiante universitario de primer año. Fue para programar recursos. No me di cuenta en ese momento, pero resultó ser un problema completo de NP.
Afortunadamente, encontrar una solución era aceptable, no era necesario encontrar la solución óptima. Fue divertido escribir heurísticas, en realidad, una serie de ellas, que podrían cambiarse mientras el programa se estaba ejecutando e intentando 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. Fui un desarrollador mejor que un vendedor.
Fue muy divertido y me enseñó mucho sobre el mundo real del desarrollo (usuarios finales, recopilación de requisitos, pruebas, etc.) muchas de las cosas que NO se obtienen en la licenciatura CS)
Para responder a su pregunta, era para un maestro que tenía que programar a los alumnos para recibir instrucción especial. Era terapeuta del habla y audiólogo, pero podría aplicarse a cualquier campo similar. Tenía actividades existentes de docentes, aulas y estudiantes para trabajar y tenía que cumplir un número específico de veces por semana con los estudiantes. Es el problema de la mochila o cualquier cantidad de otros problemas de programación similares/equivalentes.
De nuevo, resultó que solo obtener una solución estaba bien, no teníamos que maximizar o minimizar nada, simplemente teníamos que dar cabida a todos los estudiantes.
Solo recuerdo que no pude resolver los casos de prueba que solía ejecutar en los escenarios, todos los problemas que proporcionó a lo largo de los años lo resolvimos.
Nunca pude comercializarlo, sobre todo porque no tenía idea de lo que estaba haciendo y no estaba seguro de cómo llegar a mi mercado/compradores.
Vale la pena señalar que existen técnicas de aproximación heurística para obtener respuestas "suficientemente buenas" para problemas NP-completos, como el recocido simulado y el recocido comprimido. Si puede reducir su problema NP-complete al problema del Viajero Vendedor, puede usar estos enfoques. (Cualquier problema NP-completo se puede reducir a cualquier otro problema NP-completo, pero en realidad hacerlo a veces es un fastidio.)
De todos modos, existen implementaciones de recocido simulado y recocido comprimido; uno de ellos es Djinni, que está escrito en C++ y tiene enlaces de Python.
Otro ejemplo es que las empresas con centros de distribución regionales, especialmente aquellos que entregan directamente al cliente (por ejemplo, Netflix), deben preocuparse por la familia de problemas NP-Complete conocida como facility location.
De hecho, la idea de que los problemas 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 las revistas de investigación operativa.
Estaba trabajando en un programa de mapeo hace unos años, como un Google Maps nativo. Puse marcadores pequeños en el mapa para las ubicaciones, pero muchos marcadores se agruparon de cerca en ciertos lugares. Mi jefe dijo "déjame hacerlo así puedo arrastrar los marcadores un poco" (y tendría una línea o un discurso burbuja-puntero-cosa desde el marcador hasta la ubicación real).
Pensé que era tonto 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 a su ubicación. Creo que en ese momento me convencí de que esto era NP completo, pero que la cantidad de puntos podría ser lo suficientemente pequeña como para que todavía sea factible, al menos en muchos casos. (Recuerdo que pensamos que pasábamos demasiado tiempo en clase con pruebas de plenitud NP, y no lo suficiente con soluciones alternativas: si su jefe quiere que se haga algo, no puede simplemente decir "NP difícil, no funcionará"; todavía tienen que llegar a algo .)
a continuación, Google Maps llegó y simplemente splatted todas las etiquetas en la parte superior de uno al otro, que aspira totalmente (y me maldicen todos los días), pero no puedo competir con sus otras características, así que me di por vencido. :-(
+1 por "no muy bien" definido "- en el mundo real, este parece ser un problema mucho más común. –