[pyar] Buscar máximo

[Angel Java Lopez]

Ahi, ya iria con algoritmo genetico, una especie de hill climbing en
paralelo. Y pondria a 1000 instancias de Amazon a trabajar, cada una con su
poblacion, e intercambiado cromosomas ;-)  Es la idea de
https://github.com/ajlopez/SimpleGA/tree/master/samples/tspdistr

Lo que envie anoche, es el segundo metodo? el "viejo truco" de perturbar el
punto medio? ;-)

Con las condiciones del problema, puede una recta cortar en mas de tres
puntos a la curva en el intervalo [a,b] ? me parece que si

Si ponemos condicion que toda recta corta a la curva en el intervalo [a,b]
A LO SUMO en dos puntos, y hay un maximo, tenemos un problema que es
subproblema del inicial.

Si tuvieramos un algoritmo magico que nos diera, dados a, b, el x tal que
f'(x) = f(b)-f(a) (es decir el punto x donde la derivada de x se hace igual
a la diferencia de los extremos), entonces ese x nos acerca al maximo. Si
f(b)-f(a) es positivo, nos quedamos con el intervalo [x,b] y repetimos. Si
f(b)-f(a) es negativo, nos quedamos con el intervalo [a,x] y repetimos. El
punto x existe, por el teorema de Rolle. Es unico, por las condiciones del
problema. Cuando f(b)=f(a), x es el maximo.

Nos leemos!

Angel "Java" Lopez
@ajlopez


2014/1/18 Enrique Gabriel Baquela <egbaquela en gmail.com>

> Para evitar la meseta estaba bueno lo de correrlo con varios inicios
> aleatorios, pero el tiempo de calculo sube bastante.
> El 17/01/2014 20:30, "fisa" <fisadev en gmail.com> escribió:
>
> Y adelanto el principal problema de hill_climbing (aparte de máximos
>> locales, que en este caso no tenemos):
>> Si hay una meseta, se va a quedar estancado en ese punto.
>>
>> El día 17 de enero de 2014, 20:27, Angel Java Lopez
>> <ajlopez2000 en gmail.com> escribió:
>> > Ah! Ahora entendi, es O(n log(m)) no O(n log(n))
>> >
>> > Para mi daba lo mismo, porque
>> >
>> > O(n log(m)) en la segunda
>> > O(2 log(m)) en la primera == O(log(m))
>> >
>> > es asi?
>> >
>> > Bueno, gracias por el problema, muy bueno, paso a offline, time to
>> fight for
>> > my food ;-)
>> >
>> > Angel "Java" Lopez
>> > @ajlopez
>> >
>> >
>> > 2014/1/17 Alejandro Santos <listas en alejolp.com>
>> >>
>> >> La busqueda ternaria es O(log(M)), donde M representa la precisión del
>> >> resultado en decimales.
>> >>
>> >> La busqueda en N subintervalos con el pseudo codigo de recien es O(N
>> >> log(M)), donde N es la cantidad de subintervalos, y M la precisión del
>> >> resultado en decimales.
>> >>
>> >>
>> >>
>> >>
>> >> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
>> >> > Bien, mencionas "n de afuera", cual es el "n de adentro"?
>> >> >
>> >> > Si no hay "n de afuera" distinto de "n de adentro", veo que las dos
>> >> > tienen
>> >> > la misma O
>> >> >
>> >> >
>> >> > 2014/1/17 Alejandro Santos <listas en alejolp.com>
>> >> >>
>> >> >> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
>> >> >> > Hmmm...
>> >> >> >
>> >> >> > cual es el n en O(log(n))?
>> >> >> >
>> >> >> > Yo puse n en la segunda solucion, a ese n se refiere O(n log(n))?
>> >> >> >
>> >> >>
>> >> >> Ok, capaz hacer un analisis BigOh sin codigo es... confuso.
>> >> >>
>> >> >> El n de afuera se refiere a la cantidad de subintervalos en que
>> partís
>> >> >> [a, b], y en que luego partis el subintervalo no monótono.
>> >> >>
>> >> >> Con tu explicación me imaginé algo así:
>> >> >>
>> >> >> def busqueda_en_intervalos(f, a, b, N):
>> >> >>     EPS=1e-8
>> >> >>     while True:
>> >> >>         L = partir_en_intervalos(f, a, b, N)
>> >> >>         for E in L:
>> >> >>             if not es_monotono(E):
>> >> >>               a, b = E
>> >> >>               break
>> >> >>         if abs(a - b) <= EPS:
>> >> >>             return (a + b) / 2
>> >> >>
>> >> >> --
>> >> >> Alejandro Santos
>> >> >>
>> >> >> _______________________________________________
>> >> >> pyar mailing list pyar en python.org.ar
>> >> >> http://listas.python.org.ar/listinfo/pyar
>> >> >>
>> >> >> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>> >> >>
>> >> >> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre
>> de
>> >> >> Argentina - http://www.usla.org.ar
>> >> >
>> >> >
>> >> >
>> >> > _______________________________________________
>> >> > pyar mailing list pyar en python.org.ar
>> >> > http://listas.python.org.ar/listinfo/pyar
>> >> >
>> >> > PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>> >> >
>> >> > La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre
>> de
>> >> > Argentina - http://www.usla.org.ar
>> >>
>> >>
>> >>
>> >> --
>> >> Alejandro Santos
>> >> _______________________________________________
>> >> pyar mailing list pyar en python.org.ar
>> >> http://listas.python.org.ar/listinfo/pyar
>> >>
>> >> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>> >>
>> >> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>> >> Argentina - http://www.usla.org.ar
>> >
>> >
>> >
>> > _______________________________________________
>> > pyar mailing list pyar en python.org.ar
>> > http://listas.python.org.ar/listinfo/pyar
>> >
>> > PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>> >
>> > La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>> > Argentina - http://www.usla.org.ar
>>
>>
>>
>> --
>> fisa  -  Juan Pedro Fisanotti
>> _______________________________________________
>> pyar mailing list pyar en python.org.ar
>> http://listas.python.org.ar/listinfo/pyar
>>
>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>
>> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>> Argentina - http://www.usla.org.ar
>>
>
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
> Argentina - http://www.usla.org.ar
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140118/d04fb955/attachment.html>