fanusaez / tda-g04 Goto Github PK
View Code? Open in Web Editor NEWRespositorio de los TPs de la materia Teoria de Algoritmos
Respositorio de los TPs de la materia Teoria de Algoritmos
Algoritmo por BackTracking
Una poda que se puede aplicar es evitar agregar un elemento y explorar su rama si ese elemento no permite Hittear ningún subset adicional a los ya hitteados por el resto de los elementos.
En ese sentido los tiempos resultantes de algoritmo de Backtracking podían mejorarse, especialmente si se tomaba otro enfoque al mismo, buscando subconjuntos que aún no hayan sido satisfechos y agregando jugadores de los mismos, por supuesto también por Backtracking
Sin embargo, en el caso concreto de ’10 todos’, la estrategia de poda se revela como ineficaz.
En este contexto particular, no podemos descartar ramas de la soluci´on durante la exploraci´on, ya
que la soluci´on ´optima requiere seleccionar una cantidad de jugadores equivalente a la cantidad
de subconjuntos. Es decir, no podremos descartar soluciones en donde la longitud de la asignaci´on
que estamos explorando sea mayor a la mejor asignaci´on encontrada hasta el momento
Es decir, empirícamente la cantidad de elementos en cada subconjunto es también relevante, además de la cantidad de elementos totales y la cantidad de subconjuntos
Un gráfico con las mediciones de tiempo tomadas nos pueden ayudar a entender de qué manera crecen los tiempos en función de las diferentes variables
Aproximaci´on
wi es siempre 1 ya que no hay penalidades de peso para cada elemento
apariciones_ordenado = dict ( sorted ( apariciones . items () , key = lambda item :
item [1] , reverse = True ))
No es necesario hacer ordenamiento por cada iteración. Cada iteración se requiere solamente el elemento más grande. Eso se puede hacer con la búsqueda del máximo
La funci´on es soluci´on verifica si la asignaci´on actual constituye una soluci´on v´alida revisando
cada subconjunto. La complejidad de esta funci´on es O(m ∗ n), donde m es la cantidad de subconjuntos y n es el tama˜no promedio de cada subconjunto. En el peor caso, se deben revisar todos los
subconjuntos para determinar si la asignaci´on actual es una soluci´on.
No se está teniendo en cuenta que se ordena varias veces
Si acotamos, podemos concluir que la complejidad temporal del algoritmo es
Las complejidades calculadas se constantan de forma empírica? Los niveles de crecimiento empírico coinciden con los calculados teóricamente?
El análisis de optimalidad del algoritmo es acertado.
Variabilidad de los valores
Buscabamos que se analice a su vez si estos valores afectan de alguna manera a la complejidad temporal, cosa que en este caso se podría verificar que no ocurre
Casos de prueba
Para los casos de prueba se podría especificar de qué manera se logró identificar el valor óptimo, como parte del diseño de la prueba.
En los casos de test de optimalidad con pocos elementos, el tiempo resultante es siempre el del último ayudante. Vale la pena agregar otras pruebas en el que este no sea el caso, más allá de pruebas aleatorias o que involucran archivos
Mediciones
Creo que recomendaría que para cada n se corra más veces el algoritmo, en promedio ayuda a que la curva sea más fiel a la teoría
No teman agregar al informe apartados sobre cómo fue la metodología de creación de los sets de datos, pueden incluso embeber código relevante si lo consideran necesario
Pero solo con esta variable resulta imposible poder determinar para un d´ıa i el ´optimo solo
teniendo en cuenta el ´optimo de d´ıas anteriores. Para poder plantear la ecuaci´on de recurrencia,
necesitamos una variable m´as, que por la forma en que se plantea la energ´ıa disponible, conviene
que sea ”d´ıas desde el ´ultimo descanso”.
sí a todo, pero, por qué? Se siente apresurada la conclusión sin un desarrollo o justificación
m´ax0≤d≤1 P(k − 2, d) + m´ın(sk, e1)
Un error en la ecuación de recurrencia, debería ser: m´ın(s1, ek), no m´ın(sk, e1)
Luego el d´ıa k se va a generar un beneficio de min(sk, e1).
Misma confusión
Caso d = 0:
Es el caso donde no hay descansos en k d´ıas
Es raro el caso d=0, pareciera ser el mismo caso de d mayor a 1 pero con un valor igual a la cantidad de días transcurridos. En ese sentido, siempre se puede asumir que antes de comenzar con los entrenamientos el equipo llega descansado, por lo tanto el primer día de entrenamiento siempre hay una energía disponible s1
Paso a dejarles otra metodología de resolución, más que nada para que sepan de su existencia y vean algo raro que tiene, que a veces podemos hacer crecer los subproblemas desde el final hacia el principio
Paso a mostrarles como podría quedar la ecuación de recurrencia considerando:
las dos variables días i y descanso hace días k
Sabiendo que en el último día n lo conveniente es siempre entrenar (aunque no sabemos cuántos días seguidos venimos entrenando), el proceso sería dar vuelta el problema y comenzar calculando desde el día n, bajando hasta 0.
De cualquier manera, esto sigue implicando hacer crecer el tamaño de los subproblemas, así:
para todo k posible, los subproblemas más pequeños involucran un solo día, el día n
luego
para todo k posible, crecemos e involucran dos días, el día n y el n-1
etc
∀i, k ∈ N;i, k < n; k ≤ i
OPT[i, k] = max(min(ei; sk) + OP T[i + 1, k + 1]; OP T[i + 1, 1])
De esta manera el óptimo siempre se refiere a un día i+1, que siempre fue calculado previamente.
El resultado final queda en el origen 0,0 de la matriz
1 def obtener_matriz_optima ( e_de , e_dis ):
No sé si nos beneficia cambiar la terminología respecto del resto de la explicación
LLeno la matriz para el caso donde nunca se toma un descanso .
Se trata de un caso particular o puede ser resuelto por el algoritmo general?
Ahora analizando todo en conjunto la complejidad total deber´ıa calcularse como:
En otras palabras, para n^2-n casilleros, cada casillero se calcula en tiempo constante, dando una complejidad de O(n^2)
Para n-2 casilleros, cada uno de ellos se calcula en O(n), aportando otro término O(n^2).
Dando O(n^2) en total
Esto significa que es necesario evaluar todas las posibles
combinaciones de subproblemas para determinar cu´al es la mejor soluci´on global.
Esta exploración en muchos casos es implícita, ya que podemos descartar casos que sabemos que no son óptimos.
De lo contrario, para hacer una exploración explícita se deberían explorar la cantidad exponencial de posibilidades que este problema plantea.
Siendo que hay que explorar todas las soluciones la complejidad temporal del algoritmo se
mantendr´ıa constante sin importar la variabilidad de los valores
Esta no es una buena justificación. En realidad se justifica dado que los valores numéricos no son parte de la complejidad temporal, solamente depende de la cantidad n
Medici´on 1
Se podría por ejemplo graficar para cada n el valor del (tiempo consumido/n), el gráfico resultante debería asemejarse a una recta.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.