Ejemplos de backtracking.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "LoadPackage(\"yags\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### El problema de las ocho damas\n",
    "\n",
    "Definimos una función auxiliar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "chk_damas := function(L,ex)\n",
    "    local x, y, n, i;\n",
    "    n:=Length(L);\n",
    "    x:=L[n];\n",
    "    for i in [1..n-1] do\n",
    "        y:=L[i];\n",
    "        if y=x then return false; \n",
    "        fi;\n",
    "        if y=x+i-n then return false;\n",
    "        fi;\n",
    "        if y=x-i+n then return false;\n",
    "        fi;\n",
    "    od;\n",
    "    return true;\n",
    "end;  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " En este caso, el cuarto argumento de la función `BactrackBag` no se usa:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "BacktrackBag([1..4],chk_damas,4,\"hi\");    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Triángulos en una gráfica"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "chk_completas := function(L,g)\n",
    "    local x,i,n;\n",
    "    n:=Length(L);\n",
    "    x:=L[n];\n",
    "    for i in [1..n-1] do\n",
    "        if L[i]>=x then return false; fi;\n",
    "        if not(IsEdge(g,x,L[i])) then return false; fi;\n",
    "    od;\n",
    "    return true;\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g:=OctahedralGraph(3);   \n",
    "L:=[];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En este caso, evaluaciones sucesivas de la siguiente celda arrojan los triángulos en la gráfica."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Backtrack(L,Vertices(g),chk_completas,3,g);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ciclos inducidos\n",
    "\n",
    "En este caso definimos funciones `chk` y `done`. El argumento `par` se refiere a una lista cuyos elementos son la\n",
    "gráfica y la longitud deseada."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "done_ciclos := function(L,par)\n",
    "    local x,n,g,l;\n",
    "    g:=par[1];\n",
    "    l:=par[2];\n",
    "    n:=Length(L);\n",
    "    x:=L[n];\n",
    "    return IsEdge(g,x,L[1]) and Length(L)=l;\n",
    "end;   \n",
    "\n",
    "chk_camino_inducido := function(L,par)\n",
    "    local x,n,i,g,l;\n",
    "    g:=par[1];\n",
    "    l:=par[2];\n",
    "    n:=Length(L);\n",
    "    if n<=1 then return true; fi;\n",
    "    x:=L[n];\n",
    "    if x in L{[1..n-1]} then return false; fi;\n",
    "    if not(IsEdge(g,x,L[n-1])) then return false; fi;\n",
    "    for i in [2..n-2] do\n",
    "        if IsEdge(g,x,L[i]) then return false; fi;\n",
    "    od;\n",
    "    if n>2 and n<l and IsEdge(g,x,L[1]) then return false; fi;\n",
    "    return true;\n",
    "end;  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g:=RandomGraph(20,0.5);   \n",
    "L:=[];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Backtrack(L,Vertices(g),chk_camino_inducido,done_ciclos,[g,5]);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4",
   "language": "gap",
   "name": "gap-4"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP 4",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}