Análisis de Complejidad

Facultado de MAtemticasUADY
Contenido
El Problema del Aserradero....................................2
Descripcin del problema.....................................2
Propuesta de Resolucin por medio de
Ramificacin y Poda..............................................2
Anlisis de complejidad temporal.......................4
Anlisis de Complejidad espacial........................5
El Problema del Aserradero

Descripcin del problema
En el aserradero El palillo se llevan troncos para cortarlos
en pedazos ms pequeos. El aserradero cobra 10 pesos por
cada metro que mida el tronco a cortar. La sierra solamente
realiza un corte a la vez. Los troncos que se llevan a corte son
de diferentes largos y se requieren cortar en varias secciones.
Es fcil notar que diferentes rdenes de corte resultan en
diferentes costos. Por ejemplo, un tronco de 10 metros que
requiere cortarse a las distancias de 2, 4 y 7 metros a partir
de un extremo tendr un costo de 100+80+60=240 pesos si
se corta primero en el punto de 2 metros, luego en el punto
de 4 metros y luego en el punto de 7 metros. Pero si primero
se corta en el punto de 4 metros, luego en el de 2 y luego en
el de 7, entonces el costo ser de 100+40+60=200 pesos.
Disea un algoritmo para determinar el orden de corte de un
tronco que resulte en el costo mnimo.
Propuesta de Resolucin por medio de

Ramificacin y Poda
Luego de inspeccionar con las tcnicas vistas en la asignatura
Complejidad Computacional, el equipo propuso utilizar el
algoritmo de Ramificacin y Poda, para la resolucin del
problema anterior.
Aunque pareciera ser muy similar a la implementacin por
Backtracking, consideramos importante optimizar el proceso,
buscando primero en profundidad para identificar los nodos
que no nos sirven y detener el anlisis.
Para esto, tomamos un trozo de madera cualquiera con
sus respectivas marcas de corte, como la cima de
nuestro rbol.
A este nodo se extienden las diferentes posibilidades de

inicio del cortado, que a su vez, extendern cada uno de
los posibles caminos a seguir en el corte del tronco.
El algoritmo encuentra su valor agregado, cuando cada
noto tiene cierta cantitad de coste econmico.
Nuestro algoritmo se encargar de comparar costes y si
algn nodo supera el mnimo en turno, no ser analizado,
lo cual ahorra espacio y tiempo de ejecucin a nuestra
solucin.
Podremos expandir un rbol de manera parcial, en el cual se
encontrar la solucin ptima para la resolucin de nuestro
problema.
Es importante analizar la complejidad Espacial y Temporal de
nuestro algoritmo, por lo cual, hemos dedicado una seccin a
su estudio.
Anlisis de complejidad temporal

En el peor caso siempre se encontrara una solucin mejor que
la anterior por lo que se tendrn que crear todos los nodos,
preguntara cuando llegue a una solucin si es el ptimo y
cambiar el ultimo valor por el nuevo.
Para el caso de la accin de comparar la realizara siempre que
llegue a una solucion.
Dado que hay n! soluciones, la funcin de complejidad para
comparar costos seria:
F1(n) = (P1)n! , donde P1 es el peso de la comparacin
Para el caso de creacin de nodos se crean n nodos en el
primer nivel, n(n-1) en el segundo,
n(n-1)(n-2) en el
tercero, y as sucesivamente, por lo tanto la funcin de
complejidad de esta parte es:
F2(n) = P2[n! + n!/1! +n!/2! + + n!/(n-2)! + n!/(n-1)!]
Finalmente, para la comparacin de costo del total de los
cortes hasta el momento, se realiza en todos los niveles
menos en el ultimo, por lo que la funcin de complejidad es:
F3(n) = P3[n!/1! + n!/2! + + n!/(n-2)! + n!/(n-1)!]]
El total es:
F(n) = (P1+2P2+P3)n! + (P2+P1)[n!/3! +n!/3! + + n!/(n-2)!
+ n!/(n-1)!]
El orden de complejidad temporal es entonces:
O(n) = n!
Anlisis de Complejidad espacial

En este algoritmo utiliza una clase en la que se
especifican algunas constantes como puntos de corte,
total de cortes, algunas variables que ocupan un
espacio de memoria constante como el costo, numero
de cortes hechos, pero otras no son de tamao fijo
como las zonas de corte realizadas y trozos de tronco
resultantes.
El espacio de memoria que ocupa cada nodo en el algoritmo
es ax+c, donde x es el nivel del rbol en el que se encuentra
el nodo con a y c constantes.
Ahora se muestran el uso de memoria durante el proceso de
solucin del peor caso del problema de corte con 2 y 3 cortes
(se muestra m de am+c (total de memoria, con a y c
constantes)):
Iteraci
n x
1
2
3Iteraci
4 n x
5
6
1
0
1
0
0
0
00
01
2
3
4
5
6
7
8
9
10
11
12
13
14
15 5
16
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Nivel
1
2
0
0
2
0
1 Nivel
1
1
0
01
1
2
00
0
0
3
2
2
2
2
2
1
1
1
1
1
0
0
0
0
0
0
2
1
1
0
0
2
1
1
0
0
2
1
1
0
0
Tota
lM
0
2
3
Tota
2
lM
2
3
0
0
0
0
3
0
4
1
7
0
4
1
5
0
2
0
5
1
6
0
3
1
4
0
1
0
4
1
5
0
2
1
3
0
0
Se puede ver que el

mximo uso de
memoria es:
1(n-1) + 2(n-2) + + (n-2)2 + (n-1)1 + n

n1
i (ni)+n
i=1
n1
n1
i=1
i=1
n i i 2+ n
n(n1) n n(n1)(2n1)
+n
2
6
n(n1)(n+ 1)
+n
6
Entonces, el orden de complejidad espacial es:

O(n) = n3
Anexo 1- Cdigo en C++

#include <iostream>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <string.h>
using namespace std;
/******************************* DATOS
//#define numCortes 10
****************************
*/
//#define puntos {2,7,8,14,17,20,21,24,28,29}

//#define largo 30
struct trozo{
int limi,lims;
};
class tronco{
public:
int n;
int costo;
int hechos;
int *corteslistos;
//lista
int *cortes;
//lista
trozo *trozos;
tronco(){
costo = 0;
hechos = 0;
cortes = NULL;
trozos = NULL;
corteslistos = NULL;
}
~tronco(){
//total de cortes
//numero de cortes realizados
de cortes realizados en orden
de zonas de corte
}
void liberar(){
delete[] cortes;
delete[] trozos;
delete[] corteslistos;
}
bool cortar(int idx, tronco& _tronco){
if(hechos == n || idx+1 > n - hechos)return false;
int i,j,k;
j=0;k=0;
while(k+trozos[j].lims-trozos[j].limi-1 < idx+1){
k+=trozos[j].lims-trozos[j].limi-1;
j++;
}
k = trozos[j].limi+idx+1-k;
////////////////////////////////////////////////////7
_tronco.n = n;
_tronco.hechos = hechos+1;
_tronco.costo = costo+cortes[trozos[j].lims]-cortes[trozos[j].limi];
//cout<<"c: "<<hechos<<"costo: "<<_tronco.costo<<endl;
_tronco.cortes = new int[n+2];
for(i=0;i<n+2;i++) _tronco.cortes[i] = cortes[i];
_tronco.corteslistos = new int[hechos+1];
for(i=0;i<hechos;i++) _tronco.corteslistos[i] = corteslistos[i];
//falta 1
_tronco.corteslistos[hechos] = k;
_tronco.trozos = new trozo[hechos+2];
_tronco.trozos[j].limi = trozos[j].limi;
_tronco.trozos[j].lims
= k;
_tronco.trozos[j+1].limi = k;
_tronco.trozos[j+1].lims = trozos[j].lims;
for(i=0;i<j;i++) _tronco.trozos[i] = trozos[i];
for(i=j+2;i<hechos+2;i++) _tronco.trozos[i] = trozos[i-1];
return true;
}
};
int main(int argc, char *argv[]) {
int numCortes;
int largo;
int *cortes;
//
int cortes[numCortes] = puntos;

tronco base;
/**
ENTRADA
*/
cout<<"Escriba el tamao del tronco: "; cin>>largo;

cout<<"Escriba el numero de cortes: "; cin>>numCortes;
cortes = new int[numCortes];
for(int i=0;i<numCortes;i++){
cout<<"Escriba el punto de corte "<<i+1<<": "; cin>>cortes[i];
}
base.n = numCortes;
base.trozos = new trozo;
base.trozos->limi=0;
base.trozos->lims=numCortes+1;
base.cortes=new int[numCortes+2];
int coptimo = largo;
base.cortes[0]=0;
base.cortes[numCortes+1]=largo;
for(int i=0;i<numCortes;i++) {
base.cortes[i+1] = cortes[i];
coptimo += cortes[i];
}
delete[] cortes;
tronco boptimo;
boptimo.costo = coptimo;
int i=0;
tronco temp, nuevo;
/*****************************************************************************/
/** Metodo: ramificacion y poda */
stack<tronco> arbol;
/** Se utiliza una pila, el arbol sera recorrido
primero en profundidad */
arbol.push(base);
while(!arbol.empty()){
temp = arbol.top();
arbol.pop();
if(temp.hechos == numCortes){
recorrido llega a una hoja */
if (temp.costo < boptimo.costo){
para seleccionar el optimo */
boptimo.liberar();
boptimo = temp;
}
}
else {
if(temp.costo < boptimo.costo){
no se sigue recorriendo si el costo de */
/** si el
/** compara costos
/** una rama

/**
haber llegado al nodo actual supera el costo del optimo */

while(temp.cortar(i,nuevo)){
/** Nuevos nodos */
arbol.push(nuevo);
i++;
}
i=0;
}
temp.liberar();
}
}
/*****************************************************************************/
cout<<"Orden optimo de corte:\n";
for(i=0;i<numCortes;i++){
cout<<boptimo.cortes[boptimo.corteslistos[i]]<<endl;
}
cout<<"costo: "<<boptimo.costo;
boptimo.liberar();
//
return 0;
trozo t;
Anexo 2 Algunos Ejemplos

Ejemplo 1
En el primer ejemplo, consideraremos una barra de 100 cm de tamao,
a la cual le haremos cinco cortes, a los 3, 6, 10 y 50 cm.
10
El algoritmo, se encargar de expandir el rbol de manera parcial,

nicamente en los nodos prometedores. En un instante enviar la
respuesta.
Para cortar el tronco con el mnimo costo, el programa indica, por

Ramificacin y Poda, que debemos hacerlo en el orden, 50, 10 y 6, para
garantizar el costo mnimo de $160.
Ejemplo 2
Como segundo ejemplo, consideraremos una pedazo de madera de 500
cm de longitud, y realizaremos 10 cortes, a 15, 20, 35, 45, 70, 80, 100,
115, 150, 190 y 195.
11
Para este caso ms complejo, es de vital importancia la utilizacin de la

Ramificacin y Poda, pues se ahorra la completa expansin de varios
nodos que haran interminable el proceso.
El programa nos indica que para garantizar el costo mnimo de $1110,

debemos cortar el orden 195, 100, 150, 190, 45, 70, 80, 20, 35 y 15.
12

Análisis de Complejidad

Cargado por

Copyright:

Formatos disponibles

Análisis de Complejidad

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Análisis de Complejidad

Cargado por

Copyright:

Formatos disponibles

Facultado de MAtemticasUADY

El Problema del Aserradero

Propuesta de Resolucin por medio de

A este nodo se extienden las diferentes posibilidades de

Anlisis de complejidad temporal

Anlisis de Complejidad espacial

Se puede ver que el

1(n-1) + 2(n-2) + + (n-2)2 + (n-1)1 + n

Entonces, el orden de complejidad espacial es:

Anexo 1- Cdigo en C++

//#define puntos {2,7,8,14,17,20,21,24,28,29}

int cortes[numCortes] = puntos;

cout<<"Escriba el tamao del tronco: "; cin>>largo;

/** una rama

haber llegado al nodo actual supera el costo del optimo */

cout<<"Orden optimo de corte:\n";

Anexo 2 Algunos Ejemplos

El algoritmo, se encargar de expandir el rbol de manera parcial,

Para cortar el tronco con el mnimo costo, el programa indica, por

Para este caso ms complejo, es de vital importancia la utilizacin de la

El programa nos indica que para garantizar el costo mnimo de $1110,

También podría gustarte