{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algoritmo Simulated Annealing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### KB=1.38*10^(-23)\n",
    "#### t : Temperatura, inicialmente alta, em Kelvin. Exemplo t==300\n",
    "##### probabilidade = exp((EnergiaCorrente-EnergiaNova)/(KB*t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resolver o problema do caixeiro viajante"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "n : quantidade de cidades\n",
    "\n",
    "KB=1.38*10^(-23)\n",
    "\n",
    "Distribuir(n)  // distribui aleatoriamente os n pontos correspondentes as n cidade e liga os pontos\n",
    "\n",
    "Plota(graficoOriginal,Esquerda) //grafico com as primeiras ligaçãoes, estático\n",
    "\n",
    "Ec= Energia()\n",
    "\n",
    "print(Ec)\n",
    "\n",
    "t = 300       // poderia ser mais ou menos\n",
    "\n",
    "escReducao = 0.1\n",
    "\n",
    "nSucessosSeguidos = 1\n",
    "\n",
    "nFracassoSeguidos = 0\n",
    "\n",
    "Sucesso = True\n",
    "\n",
    "for it in range (10):  // 10 iteracoes\n",
    "\n",
    "    Repita até         // ou coloca for de 1000\n",
    "    \n",
    "        Perturba()  //causa mudanças nas arestas\n",
    "        \n",
    "        Enew = Energia()\n",
    "        \n",
    "        deltaE = Ec - Enew\n",
    "        \n",
    "        probabilidade = 1   //supõe que a Enew é menor que Ec\n",
    "        \n",
    "        if deltaE < 0     //Enew > Ec, a principio recusa essa nova configuracao\n",
    "        \n",
    "            probabilidade = exp(deltaE/(KB*t)) //probabilidade de aceitar mesmo com nova energia mais alta\n",
    "            \n",
    "            r = random.random() //valor entre 0 e 1\n",
    "            \n",
    "        if r <= probabilidade:  //aceita a probabilidade\n",
    "        \n",
    "            if Sucesso:\n",
    "            \n",
    "                nSucessoSeguidos += 1\n",
    "                \n",
    "            else:\n",
    "            \n",
    "                Sucesso = True\n",
    "                \n",
    "                nSucessoSeguidos = 1\n",
    "                \n",
    "            Ec = Enew\n",
    "            \n",
    "            print(Ec)\n",
    "            \n",
    "        else:                  //rejeita a probabilidade\n",
    "        \n",
    "            if not (Sucesso):\n",
    "            \n",
    "                nFracasso += 1\n",
    "                \n",
    "            else:\n",
    "            \n",
    "                Sucesso = False\n",
    "                \n",
    "                nFracasso = 1\n",
    "                \n",
    "                \n",
    "        Plota(GraficoAtual,Direita)\n",
    "        \n",
    "    ou nSucessosSeguidos > 10*n ou nFracassosSeguidos > 100*n  // ou um ou outro\n",
    "    \n",
    "    \n",
    "    t = t - t*escalaReducao == t*(1 - escalaReducao)==(1-escalaReducao)*t    //diminui a temperatura\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}