Buenas tardes!

Publique ya un par de temas referidos a un par de problemas de tipo NP.

Había realizado un programa en C que resuelve el problema de la suma de subconjuntos usando programación lineal.

Necesito saber el O(n) y para eso necesito probarlo con casos representativos para calcularlo porque para un mismo tamaño de entrada tiene diferentes tiempos de ejecución, es decir, varían según los valores introducidos siendo del mismo tamaño de entrada.

Por ejemplo, para un N=1000 y valores entre 100000000 y 200000000 a veces tarda unos segundos en encontrar el valor deseado y otras pasan un par de horas y todavía no llega a resolverlo.

No saber si el caso anterior es representativo o cual podría serlo.

Saludos.

Hola, leí bastante sobre el tema en internet pero quiero saber bien cuales son los métodos de resolución del problema del viajante de comercio usando programación lineal y cual es el O(n) de esos métodos. Se que hay pocos métodos pero estoy interesado en tiempo de ejecución en el peor de los casos. Quiero juntar toda la información posible.

Muchas gracias compañeros! 

Supongamos que un programa basado en programación lineal no tiene un tiempo de ejecución definido, es decir no depende del parámetro de entrada siempre de la misma manera. Como se calcula su O(n)?
Leí en un articulo que por convención se decidió que para calcular su O(n) se debe probar casos representativos y de ahí calcularlo. No se si esto es cierto o no.

Gracias.

Un programa que resuelva con un resultado aproximado al optimo en este problema, cuanto seria un rango de "garantia" de aproximacion para que sea considerado util?

Por ejemplo un programa que  te asegure el 1% de margen es bueno?

Buenas, hace un tiempo hice un programa para resolver el problema mencionado en el titulo.

Quisiera saber que tan eficaz es para lo cual necesito compararlo con el metodo de solucion Branch and Bound, por lo cual necesito por si alguno tiene, sabe o conoce un enlace donde este el codigo del metodo recien mencionado aplicado para este problema. Si esta escrito en C mejor, ya que es con el cual hice mi programa.

Gracias.

Buenas tardes, estoy tratando de averiguar cual es la BIG O del algoritmo que resuelve mas rápidamente el problema del viajante de comercio de manera optima.
Es O(n!)?

Gracias.

Buenas, quisiera saber si serviria de algo resolver un logaritmo exacto considerando que el resultado del mismo es de tamaño exponenecial. Por ejemplo el logaritmo en base 2 de 32 es 5. Pero para numeros extradamente grandes serviria para algo? Gracias

Buenas, tengo una consulta: dado un algoritmo que para diferentes valores de un mismo tamaño de de entrada (n) el tiempo de ejecucion varía; como puedo cacular la complejidad del algoritmo si para entradas de un mismo tamaño varia el tiempo de ejecucion. Digamos que para un determinado n el tiempo puede variar en el rango de dos funciones

Buenas, considerando el problema de la mochila binaria, habría alguna manera de resolver el problema rapidamente teniendo en cuenta que la capacidad de la mochila puede ser increiblemente elevada? si fuera que haya una solución solamente para este problema serviría para algo practico? Muchas gracias.

Hola, queria saber cual es el problema en si. Es si tiene alguna solucion o no, o encontrar todas las soluciones?