Son todos los problemas de programación NP-duro?

Question

Sé que hay algunos problemas de programación por ahí que son NP-hard / NP-completo ... Sin embargo, ninguno de ellos se manifestó de tal manera de mostrar esta situación es también 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 puede resolverse sin una búsqueda exhaustiva?

Si la respuesta es "amigo lo siento, pero esto es NP-completo" ¿cuál 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) para identificar un programa de irresoluble.

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

Yay para preguntas compuestos!

Answer 1

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

• Un profesor 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

A continuación, se necesita un sistema de programación que puede hacer frente a los cambios, por lo que cuando una restricción se cambia en el último minuto que no tiene que cambiar el calendario completo.

Todo lo anterior es normalmente ignorado en trabajos de investigación sobre sistemas de programación. En cuanto a NP integridad de un problema de programación dado, en la vida real no se preocupan , ya que incluso si no es NP completa es poco probable que incluso ser capaz de definir lo que el “mejor solución” es, de modo suficientemente bueno es suficientemente bueno.

http: //www.asap.cs.nott .ac.uk / watt / recursos / university.html para obtener una lista de documentos que pueden ayudar a empezar; todavía hay muchas PHDs que se tenía en el software de programación.

Answer 2

A menudo hay una buena aproximación algoritmos de problemas de optimización NP-hard / completa como la programación. Es posible que las notas del curso descremada por Ahmed Abu Safia en aproximación Algoritmos para la programación o varios papeles .

En un sentido, todo criptografía de clave pública se realiza con problemas "menos duras" como la factorización en parte debido a problemas NP-duros ofrecen demasiados casos fáciles. Es lo mismo NP-completitud que los hace "moralmente dura", que también les da demasiados problemas fáciles, que a menudo caen dentro de alguna cota de error del óptimo.

Hay una teoría más profunda de dureza de aproximación que se explican las limitaciones de algoritmos de aproximación sin embargo.

Answer 3

Se puede utilizar la programación dinámica para resolver algunas de estas cosas. algoritmos codiciosos también vienen a la mente. la teoría de la programación es a la vez profundo y hermoso, pero los dos me parece va a resolver la mayoría de los problemas que he enfrentado. Tal vez he tenido suerte.

Answer 4

¿Qué quiere decir con startBy?

Con startAfter y si hay sólo un recurso, entonces una solución rápida podría ser el uso de topológica clasificación . Las pistas ejemplo de algoritmo en tiempo lineal, pero no incluye el caso de error si el gráfico contiene ciclos.

Answer 5

Aquí hay uno que no lo es.

Programar un conjunto de puestos de trabajo i = 1,2 ... n en una sola máquina que de manera que se reduce al mínimo de cada toma de tiempo t (i) el tiempo medio de espera.

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

aquí

Answer 6

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

Entrada:. Lista de actividades que incluyen la hora de inicio y hora de finalización

Ordenar por hora de finalización.

Seleccione los primeros N elementos de esta lista ordenada para encontrar la mayor cantidad de actividades que se pueden programar en un momento dado.

Se puede añadir advertencias como: todas las actividades deben poner fin a las 5 pm, así que en este caso a medida que trabaja a través de la lista, parada una vez que llegue una actividad que termina después de este tiempo

.