CercaExhaustiva.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "t0YAlIry50Lm"
   },
   "source": [
    "<div id=\"capcalera\">\n",
    "    \n",
    "<p>Aquest notebook forma part dels continguts teòrics dels problemes de l'assignatura d'<strong>Algorísmica</strong> del Grau d'Enginyeria Informàtica a la <a href=\"https://mat.ub.edu\">Facultat de Matemàtiques i Informàtica</a> de la <a href=\"https://www.ub.edu\">Universitat de Barcelona</a></p>\n",
    "\n",
    "<p>Els problemes s'ofereixen sota llicència <a href=\"https://creativecommons.org/licenses/by-nc-nd/3.0/us/legalcode\">CC-BY-NC-ND license</a>, i el codi sota <a href=\"https://opensource.org/licenses/MIT\">Llicència MIT</a>.</p>\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "B7NjZ5JB50Ln"
   },
   "source": [
    "# <span class=\"tema\">(Cerca)</span> Cerca exhaustiva i aleatòria"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bYrGFje0OOm-"
   },
   "source": [
    "## Cerca exhaustiva"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "0lGFKFwi50Lo"
   },
   "source": [
    "Aquest algorisme implementa la cerca exhaustiva"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ENxB23wdOOnB"
   },
   "outputs": [],
   "source": [
    "# Funció multimodal. Hem de buscar el valor de x que maximitza la funció\n",
    "\n",
    "def func1d(x): # funció multimodal de la que buscarem max\n",
    "    import math\n",
    "    y = x * math.sin(10*math.pi*(x))+1.0\n",
    "    return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "hY5c7TdvOOnD"
   },
   "outputs": [],
   "source": [
    "# Creem un range amb valors decimals, per conveniència\n",
    "\n",
    "def frange(start, stop, step): \n",
    "    current = start \n",
    "    while current < stop:\n",
    "        yield current   #yield proveeix un resultat i segueix\n",
    "        current += step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ciSNT-bCOOnH",
    "outputId": "76340862-204d-4eb8-92ba-524ea6e4276e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.1,0.30000000000000004,0.5,0.7,0.8999999999999999,"
     ]
    }
   ],
   "source": [
    "# Provem el frange\n",
    "\n",
    "for i in frange(0.1,1,0.2):\n",
    "    print(i, end=\",\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "FN6tAdMLOOnO"
   },
   "outputs": [],
   "source": [
    "def linsearchfunc1d():   # la funció de cerca \n",
    "    x = -1  #valor inicial d'x\n",
    "    maxim=func1d(x)  # valor inicial d'y \n",
    "    for i in frange(-1.0,2.0,0.01):\n",
    "        if func1d(i)>maxim: \n",
    "            maxim=func1d(i)\n",
    "            x=i\n",
    "    return x, maxim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "yYiIoLsSOOnR",
    "outputId": "f268e232-7b7b-45ee-9ecd-1afd3f8f45e8"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1.850000000000002, 2.8500000000000023)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linsearchfunc1d()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "hRXpfUayOOnT",
    "outputId": "c1c93fff-79e7-45e5-8c7b-7d97ba1c926d"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "161 µs ± 12.9 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit linsearchfunc1d()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "siRwDoSiOOnU"
   },
   "source": [
    "## Cerca aleatòria"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "wiMj4nfgOOnU"
   },
   "outputs": [],
   "source": [
    "def rsearchfunc1d():\n",
    "    import random\n",
    "    x = -1                                 # valor inicial d'x\n",
    "    maxim=func1d(x)                        # valor inicial d'y \n",
    "    for i in range(1000):                  # provem 1000 valors aleatòriament\n",
    "      xtemp = (random.random()*3.0)-1.0    # valors entre -1 i 2\n",
    "      if func1d(xtemp)>maxim:              # apliquem l'algorisme bàsic\n",
    "          maxim=func1d(xtemp)\n",
    "          x=xtemp\n",
    "    return x, maxim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "6O4P_SQoOOnV",
    "outputId": "7fbd5391-92e3-44f2-a822-3a66a91a9de1"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1.8502860462354258, 2.850211336332218)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rsearchfunc1d()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "BrsLdiesOOnV",
    "outputId": "a94fd420-9ad2-40dd-ba86-19cfde61403b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "503 µs ± 17.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit rsearchfunc1d()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "_Ub5RjD3OOnW"
   },
   "source": [
    "tarda molt més i el resultat és pitjor"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Exemple.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}