recursion - polinomial - ¿Son todos los problemas de programación NP-Duro?
problemas np hard (6)
Sé que hay algunos problemas de programación por ahí que son NP-hard / NP-complete ... sin embargo, ninguno de ellos está establecido de tal manera que muestre que esta situación también es NP.
Si tiene un conjunto de tareas restringidas a un inicioAfte , un inicio y una duración, todas intentan usar un solo recurso ... ¿puede resolver un cronograma o identificar que no se puede resolver sin una búsqueda exhaustiva?
Si la respuesta es "perdón amigo, pero esto es NP-completo", ¿cuál sería la mejor heurística (s?) Para usar y hay formas de disminuir el tiempo que lleva a) resolver un cronograma yb) identificar un no resoluble programar.
He implementado (en prólogo) una meta básica 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 en encontrar horarios no válidos. ¿Hay una manera de superar esto?
¡Yay por preguntas compuestas!
¿Qué quieres decir con startBy?
Con startAfter y si solo hay un recurso, una solución rápida podría ser utilizar la clasificación topológica . El algoritmo de ejemplo se ejecuta en tiempo lineal, pero no incluye el caso de error si el gráfico contiene ciclos.
A menudo hay buenos algoritmos de aproximación para problemas de optimización NP-hard / complete como la programación. Puede hojear las notas del curso de Ahmed Abu Safia sobre Algoritmos de Aproximación para la programación o varios papers .
En cierto sentido, toda la criptografía de clave pública se realiza con problemas "menos difíciles", como la factorización parcial, porque los problemas de NP-hard ofrecen demasiados casos fáciles. Es el mismo NP-completo que los hace "moralmente difíciles" lo que también les da demasiados problemas fáciles, que a menudo caen dentro de algún límite de error óptimo.
Sin embargo, hay una teoría más profunda de la dureza de la aproximación que analiza las limitaciones de los algoritmos de aproximación.
Aquí hay uno que no lo es.
Programe un conjunto de trabajos i = 1,2 ... n en una sola máquina, cada una de las cuales toma el tiempo t (i) para minimizar el tiempo de espera promedio.
Solución: Ordenar en orden creciente de t (i). O (n log n)
Buena lista here
Considere el problema de programación que está en la clase P:
Entrada: lista de actividades que incluyen la hora de inicio y la hora de finalización.
Ordenar por tiempo 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., En este caso, a medida que avanza en la lista, deténgase una vez que llegue a una actividad que termina después de esta hora.
La parte más difícil de la mayoría de los problemas de programación en la vida real es conseguir una confiabilidad y un conjunto completo de restricciones. Si tomamos el ejemplo de crear un horario universitario:
- El profesor A no se levantará por la mañana, está en muchos comités, pero nadie le dirá a la oficina de horarios sobre este tipo de restricción
- El Departamento 1 necesita el horario para el inicio del trimestre, sin embargo, el Departamento 2 que utiliza las mismas salas no está dispuesto a decidir los cursos que se realizarán hasta después de que hayan llegado todos los estudiantes.
- Etc
Entonces necesita un sistema de horarios que pueda hacer frente a los cambios, por lo que cuando se cambia una restricción en el último minuto, no tiene que cambiar el calendario completo.
Todo lo anterior normalmente se ignora en los trabajos de investigación sobre sistemas de programación. En cuanto a la integridad de NP de un problema de programación dado, en la vida real no le importa , incluso si no está NP completo, es poco probable que sea capaz de definir cuál es la "mejor solución", por lo que lo suficientemente bueno es lo suficientemente bueno.
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 que se tendrán en el software de programación.
Puedes usar 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 profunda y hermosa, pero las dos que encuentro resolverán la mayoría de los problemas que enfrenté. Tal vez he tenido suerte.