[pyar] Buscar máximo

[fisa]

Claro, es otra opción, es un hill_climbing que se hace presiso a
medida que avanza. Yo lo que puse es la idea más básica, pero hay
bastante para jugar en eso :)

El día 17 de enero de 2014, 20:39, Angel Java Lopez
<ajlopez2000 en gmail.com> escribió:
> Perdon, se escapo, yo pondria
>
> def hill_climbing():
>     n=1
>     actual = (a + b) / 2  # medio entre a y b
>     while n < precision requerida:
>         mejor_vecino = vecino con f más alto en vecinos(actual, n)
>         if f(actual) > f(mejor_vecino):
>             n = n + 1
>         else:
>             actual = mejor_vecino
>
> def vecinos(x, n):
>     return (x + 0.1 ^ n, x - 0.1 ^ n)
>
>
> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>
>>
>> Si, me confunde el 0.001 fijo. Yo pondria
>>
>> def hill_climbing():
>>     n = 1
>>
>>     actual = (a + b) / 2  # medio entre a y b
>>     while True:
>>         mejor_vecino = vecino con f más alto en vecinos(actual)
>>         if f(actual) > f(mejor_vecino):
>>
>>
>>
>>         else:
>>             actual = mejor_vecino
>>
>> def vecinos(x):
>>     return (x + 0.001, x - 0.001)
>>
>>
>> 2014/1/17 fisa <fisadev en gmail.com>
>>>
>>> Está bien ubicado en ese punto, porque el corte del bucle es "cuando
>>> los vecinos de mi x sean peores". O sea, cuando desde tu x mirando
>>> para izquierda y derecha, en las dos direcciones f baje.
>>>
>>> Lo que uno puede hacer para tener mejor o peor precisión es subir o
>>> bajar el 0.001 que uso.
>>> Con un número más grande, la precisión baja pero el tiempo de cálculo
>>> baja. Con un número más chico, la precisión sube pero el tiempo de
>>> cálculo sube.
>>>
>>>
>>> El día 17 de enero de 2014, 20:33, Angel Java Lopez
>>> <ajlopez2000 en gmail.com> escribió:
>>> > Ah!
>>> >
>>> > pero esta bien el return? parece que se corta demasiado rapido en
>>> > algunos
>>> > casos. Hmmm... yo podria un loop por cantidad de decimales.
>>> >
>>> > def hill_climbing():
>>> >     actual = (a + b) / 2  # medio entre a y b
>>> >     while True:
>>> >         mejor_vecino = vecino con f más alto en vecinos(actual)
>>> >         if f(actual) > f(mejor_vecino):
>>> >             return actual
>>> >         else:
>>> >             actual = mejor_vecino
>>> >
>>> > def vecinos(x):
>>> >     return (x + 0.001, x - 0.001)
>>> >
>>> >
>>> > 2014/1/17 fisa <fisadev en gmail.com>
>>> >>
>>> >> 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
>>>
>>>
>>>
>>> --
>>> 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



-- 
fisa  -  Juan Pedro Fisanotti