algoritmia_backtracking.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# <center>Backtracking</center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "La idea principal es construir soluciones candidatas un componente a la vez y evaluar tales candidatos construidos parcialmente de la siguiente forma:\n",
        "\n",
        "* Tomar la primer __opción legítima restante__ para el\n",
        "siguiente componente.\n",
        "* Si no hay opción válida para el siguiente componente, el algoritmo retrocede para __reemplazar el último componente__ de la solución parcialmente construída por la siguiente opción."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Resulta conveniente implementar este tipo de procesamiento construyendo un árbol de decisiones tomadas, llamado árbol de **estado-espacio**. La raíz representa un estado inicial antes de que comience la búsqueda por una solución."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Los nodos del primer nivel en el árbol representan las decisiones tomadas para el primer componente de una solución, los nodos del segundo nivel representan las elecciones para el segundo componente y así sucesivamente."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Un nodo en un árbol de estado-espacio se dice que es prometedor si coresponde a una solución parcialmente construída que todavía pueda llevar a una solución completa; en otro caso, se llama no prometedor. Las hojas representan ya sea finales no prometedores o soluciones completas encontradas por un algoritmo.\n"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "En la mayoría de los casos, un árbol de estado-espacio se construye según la __búsqueda primero en profundidad__. Si el nodo actual es prometedor, su hijo es generado al agregar la primer opción legítima restante para el siguiente componente de una solución y el procesamiento se mueve a ese hijo. Si el nodo actual resulta ser no prometedor, el algoritmo retrocede al padre del nodo para considerar la siguiente opción posible para su último componente."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Si no hay tal opción, retrocede un nivel más en el árbol y así sucesivamente. Finalmente, si el algoritmo llega a una solución completa al problema se detiene (si sólo se necesita una solución) o continúa buscando por otras posibles soluciones."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Ejemplos"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### El problema de las n Reinas\n",
        "\n",
        "El problema es colocar n reinas en un tablero de ajedrez de $n \\times n$ de forma tal que no se ataquen 2 reinas al estar en el mismo renglón o la misma columna o misma diagonal.\n",
        "\n",
        "Consideremos el problema de cuatro reinas. Como cada una de las cuatro reinas tiene que estar colocada en su propio renglón, todo lo que necesitamos es asignar una columna para cada reina en el\n",
        "tablero."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "<center><img src=\"media/tablero_reinas.png\" width=50% /></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "<center><img src=\"media/solucion_reinas.png\" width=75% /></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%html\n",
        "<center><iframe src=\"https://drive.google.com/file/d/1jynL5D9x-BQfowcuWq8WMnZV9dNjP_fg/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": [
        "### Suma de subconjuntos\n",
        "\n",
        "Encontrar un subconjunto de un conjunto dado    $A = \\{a_1, a_2, \\dots, a_n\\}$ cuya suma es igual a un valor $d$  previamente definido.\n",
        "\n",
        "Por ejemplo si $A = \\{1, 2, 5, 6, 8\\}$ y $d = 9$ existen dos soluciones $\\{1, 2, 6\\}$ y $\\{1, 8\\}$. Resulta conveniente ordenar los elementos de los conjuntos."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Ejemplo\n",
        "\n",
        "para $A = \\{3, 5, 6, 7\\}$ y $d = 15$\n",
        "\n",
        "<center><img src=\"media/suma_subconjuntos.png\"/></center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%html\n",
        "<center><iframe src=\"https://drive.google.com/file/d/1atZgmKgvhMgc3fIa4li8diFYxp-DvYtm/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": [
        "## Referencias\n",
        "\n",
        "Levitin, A. (2012) \"Introduction to the design and analysis of algorithms\". Ed. Pearson education, edición 3, Estados unidos de América."
      ],
      "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.28.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}