¿Todos los problemas de programación son NP-Hard?

Question

Sé que hay algunos problemas de programación que son NP-hard/NP-complete ... sin embargo, ninguno de ellos se indica de tal manera que muestre que esta situación también es NP.

Si usted tiene un conjunto de tareas limitadas a un startAfter, startBy y duración todos tratando de utilizar un solo recurso ... se puede resolver un horario o identificar que no se puede resolver sin una búsqueda exhaustiva?

Si la respuesta es "amigo lo siento, pero esto es NP-completo" lo que sería la mejor heurística (s?) De usar y hay maneras de disminuir el tiempo que se tarda en a) resolver un horario y b) identificar un cronograma no resuelto.

Implementé (en prolog) un objetivo básico de resolución de conflictos a través de la recursión que implementa una heurística de "ventana más pequeña primero". En realidad, esto encuentra soluciones con bastante rapidez, pero es excepcionalmente lento para encontrar horarios no válidos. ¿Hay una manera de superar esto?

¡Yay para preguntas combinadas!

Answer 1

La parte más difícil de la mayoría de los problemas de programación en en la vida real está adquiriendo una fiabilidad y un conjunto completo de restricciones. Si tomamos el ejemplo de la creación de un calendario universitario:

• Profesor A no se levanta por la mañana, él está en una gran cantidad de comités, pero nadie le dirá la oficina calendario de este tipo de restricción
• Departamento 1 necesita el calendario por el comienzo del plazo, sin embargo, Departamento 2 que utiliza las mismas habitaciones no está dispuesto a decidir sobre los cursos que se ejecutarán hasta que todos los estudiantes han llegado
• Etc

Entonces necesita un sistema de programación que pueda hacer frente a los cambios, por lo que cuando se modifica una restricción en el último minuto, no es necesario cambiar el horario completo.

Todo lo anterior normalmente se ignora en trabajos de investigación sobre sistemas de programación. En cuanto a la integridad de NP de un problema de programación dado, en en la vida real no le importa, ya que incluso si no es NP completa, es poco probable que pueda definir cuál es la "mejor solución", por lo tanto es buena. suficiente.

Consulte http://www.asap.cs.nott.ac.uk/watt/resources/university.html para obtener una lista de documentos que pueden ayudarlo a comenzar; todavía hay muchos PHD en el software de programación.

Answer 2

Puede usar la programación dinámica para resolver algunas de estas cuestiones. Los algoritmos codiciosos también vienen a la mente. La teoría de la programación es a la vez profunda y hermosa, pero los dos que encuentro resolverán la mayoría de los problemas que he enfrentado. Tal vez he tenido suerte.

Answer 3

¿Qué quieres decir con startBy?

Con startAfter y si solo hay un recurso, entonces una solución rápida podría ser usar topological sorting. El algoritmo de ejemplo se ejecuta en tiempo lineal, pero no incluye el caso de error si el gráfico contiene ciclos.

Answer 4

Aquí hay uno que no lo es.

Programe un conjunto de trabajos i = 1,2 ... n en una sola máquina, cada uno de los cuales toma tiempo t (i) para que el tiempo de espera promedio se reduzca al mínimo.

Solución: Ordenar en orden creciente de t (i). O (n log n)

una buena lista here

Answer 5

A menudo hay una buena approximation algorithms de problemas de optimización NP-hard/completa como la programación. Puede leer las notas del curso por Ahmed Abu Safia en Approximation Algorithms for scheduling o en varios papers.

En cierto sentido, toda la criptografía de clave pública se realiza con problemas "menos duros" como el factoring en parte porque los problemas de NP-difícil ofrecen demasiados casos fáciles. Es la misma completitud NP lo que los hace "moralmente difíciles", lo que también les da demasiados problemas fáciles, que a menudo caen dentro de un límite de error óptimo.

Hay una teoría más profunda de hardness of approximation que discute las limitaciones de los algoritmos de aproximación.

Answer 6

considerar el problema de programación que está en la clase P:

Entrada: lista de actividades que incluyen la hora de inicio y de final.

Ordenar por hora de finalización.

Seleccione los primeros N elementos de esta lista ordenada para encontrar la cantidad máxima de actividades que puede programar en un momento dado.

Puede agregar advertencias como: todas las actividades deben finalizar a las 5 p.m., bueno, en este caso mientras trabaja en la lista, deténgase una vez que llegue a una actividad que finaliza después de esta fecha.