algoritmia_voraces.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# <center>Algoritmos Voraces</center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Los científicos de la computación consideran a los algoritmos voraces como una **técnica general de diseño** a pesar del hecho de que sólo es aplicable a problemas de optimización. \n",
        "\n",
        "El acercamiento voraz sugiere construir una solución a través de una serie de pasos, cada uno expandiendo una solución parcialmente construída hasta ese punto, ésto hasta que la solución completa se alcanza."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "En cada paso (y éste es el punto central de ésta técnica) la elección hecha debe ser:\n",
        "\n",
        "* __Viable__, es decir, debe satisfacer las __restricciones__ del problema.\n",
        "* __Óptima__ localmente, es decir, debe ser la __mejor elección__ local entre todas las opciones disponibles en ese paso.\n",
        "* __Irrevocable__, es decir, una vez hecha __no puede ser cambiada__ en pasos subsecuentes del algoritmo."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Éstos requerimientos explican el nombre de la técnica: En cada paso sugiere tomar de maner “voraz” la **mejor alternativa disponible** con la esperanza de que una secuencia de elecciones óptimas locales lleven a una solución óptima del problema entero. \n",
        "\n",
        "Como una regla, los algoritmos voraces son tanto intuitivos como atractivos y simples. Dado un problema de optimización, usualmente es simple encontrar la manera de proceder de forma voraz, posiblemente después de considerar unas cuantas instancias pequeñas del problema."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Ejemplos\n"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%html\n",
        "<center><iframe src=\"https://drive.google.com/file/d/1MPSZgES_NsWc813Rb9_CBn7f4nCJfCU8/preview\" width=\"640\" height=\"480\"></iframe></center>"
      ],
      "outputs": [],
      "execution_count": null,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-11-04T16:46:48.152Z",
          "iopub.execute_input": "2020-11-04T16:46:48.203Z",
          "iopub.status.idle": "2020-11-04T16:46:48.839Z",
          "shell.execute_reply": "2020-11-04T16:46:48.880Z"
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Knapsack\n",
        "\n",
        "La aproximación para resolver el problema de la mochila puede hacerse con un algoritmo voraz que se base en la relación de valor de los artículos. Se crea una lista ordenada de los artículos basada en la relación de su valor con respecto a su peso. Se representa cada artículo como un par \\[peso, valor\\].\n",
        "\n",
        "Si se tuviera la lista de artículos:\n",
        "\n",
        "$$([25, 50], [20, 80], [20, 50], [15, 45], [30, 105], [35, 35], [20, 10], [10, 45])$$\n",
        "\n",
        "tendrían relaciones de valor de: \n",
        "\n",
        "$$(2, 4, 2.5, 3, 3.5, 1, 0.5, 4.5)$$\n",
        "\n",
        "Ordenando por las relaciones de valor:\n",
        "\n",
        "$$([10, 45], [20, 80], [30, 105], [15, 45], [20, 50], [25, 50], [35, 35], [20, 10])$$"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Ahora se comienza a llenar la mochila usando los artículos en el orden de la lista. Si el siguiente artículo no cabe, se omite y se continúa en la lista hasta que la mochila está llena o se ha pasado por toda la lista. \n",
        "\n",
        "Por lo tanto si se tuviera una mochila de capacidad $80$, se podrían colocar los primeros cuatro artículos para un peso total de $75$ y un valor total de $275$. Sin embargo ésto no es óptimo, porque usando los primeros tres artículos y el quinto daría un peso total de $80$ y un valor total de $280$."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%html\n",
        "<center><iframe src=\"https://drive.google.com/file/d/1S4BDeUowD22hxBvc3v4DhnU3MJK-YEor/preview\" width=\"640\" height=\"480\"></iframe></center>"
      ],
      "outputs": [],
      "execution_count": null,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-11-04T16:47:51.490Z",
          "iopub.execute_input": "2020-11-04T16:47:51.531Z",
          "iopub.status.idle": "2020-11-04T16:47:51.823Z",
          "shell.execute_reply": "2020-11-04T16:47:51.865Z"
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Empaquetado\n",
        "\n",
        "Se tiene una cantidad de canastas cada una con una capacidad de $1$ y se tiene un conjunto de objetos todos con diferentes tamaños $s_1, s_2, \\dots, s_N$ entre $0$ y $1$. El problema de optimización pregunta por cuál es la menor cantidad de canastas que se necesitan para almacenar todos los objetos.\n",
        "\n",
        "Una estrategia para resolver el problema sería que para cada artículo se revisen las canastas en orden hasta que se encuentre una con suficiente espacio para almacenarlo. Si se tuviera un conjunto de artículos con tamaños $(0.5, 0.7, 0.3, 0.9, 0.6, 0.8, 0.1, 0.4, 0.2, 0.5)$ se tendría:\n",
        "\n",
        "canasta 1 $[0.5, 0.3, 0.1]$\n",
        "\n",
        "canasta 2 $[0.7, 0.2]$\n",
        "\n",
        "canasta 3 $[0.9]$\n",
        "\n",
        "canasta 4 $[0.6, 0.4]$\n",
        "\n",
        "canasta 5 $[0.8]$\n",
        "\n",
        "canasta 6 $[0.5]$\n",
        "\n",
        "Sin embargo la solución óptima sería:\n",
        "\n",
        "canasta 1 $[0.9, 0.1]$\n",
        "\n",
        "canasta 2 $[0.8, 0.2]$\n",
        "\n",
        "canasta 3 $[0.7, 0.3]$\n",
        "\n",
        "canasta 4 $[0.6, 0.4]$\n",
        "\n",
        "canasta 5 $[0.5, 0.5]$"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    }
  ],
  "metadata": {
    "kernel_info": {
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.3",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "kernelspec": {
      "argv": [
        "python",
        "-m",
        "ipykernel_launcher",
        "-f",
        "{connection_file}"
      ],
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "nteract": {
      "version": "0.26.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}