Cópia_de_Algoritmos_de_otimização_calendário_de_voos.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Cópia de Algoritmos de otimização - calendário de voos.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/viannaandreBR/My-Data-Science-Journey/blob/main/C%C3%B3pia_de_Algoritmos_de_otimiza%C3%A7%C3%A3o_calend%C3%A1rio_de_voos.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lmY8JVlQxXjj"
      },
      "source": [
        "# Algoritmos de otimização - calendário de voos"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iA6XSNeifEB0"
      },
      "source": [
        "## Representação do problema"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tgkqEoRdxgfw"
      },
      "source": [
        "pessoas = [('Lisboa', 'LIS'),\n",
        "           ('Madrid', 'MAD'),\n",
        "           ('Paris', 'CDG'),\n",
        "           ('Dublin', 'DUB'),\n",
        "           ('Bruxelas', 'BRU'),\n",
        "           ('Londres', 'LHR')]"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6YkrP_6zx2--",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d271788e-e089-4507-c1f3-58974829504f"
      },
      "source": [
        "pessoas[5]"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('Londres', 'LHR')"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FezIjellyATt"
      },
      "source": [
        "destino = 'FCO'"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZxUhP_RCyloI"
      },
      "source": [
        "voos = {('BRU', 'FCO'): ['15:44', '18:55', 382]}"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JTDv4v96y2eT",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c51b9842-6da4-41b2-b3bc-3a9b8a8f1238"
      },
      "source": [
        "voos"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{('BRU', 'FCO'): ['15:44', '18:55', 382]}"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9dHRjcXGy6CR",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5026b42c-f5de-4088-f2c1-d5d98be012b1"
      },
      "source": [
        "voos[('BRU', 'FCO')]"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['15:44', '18:55', 382]"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0brRvL3CzAfU",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "27652ef6-6d1b-45a9-da5f-7e033285e518"
      },
      "source": [
        "voos[('BRU', 'FCO')][0], voos[('BRU', 'FCO')][1], voos[('BRU', 'FCO')][2]"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('15:44', '18:55', 382)"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i4pk1lYDyaaY"
      },
      "source": [
        "voos = {}\n",
        "for linha in open('/content/flights.txt'):\n",
        "  #print(linha)\n",
        "  #print(linha.split(','))\n",
        "  origem, destino, saida, chegada, preco = linha.split(',')\n",
        "  voos.setdefault((origem, destino), [])\n",
        "  voos[(origem, destino)].append((saida, chegada, int(preco)))"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nGEmfppez90U",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "11bac84d-3260-4fba-9440-842033f18c3b"
      },
      "source": [
        "voos"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{('BRU', 'FCO'): [('6:12', '10:22', 230),\n",
              "  ('7:53', '11:37', 433),\n",
              "  ('9:08', '12:12', 364),\n",
              "  ('10:30', '14:57', 290),\n",
              "  ('12:19', '15:25', 342),\n",
              "  ('13:54', '18:02', 294),\n",
              "  ('15:44', '18:55', 382),\n",
              "  ('16:52', '20:48', 448),\n",
              "  ('18:26', '21:29', 464),\n",
              "  ('20:07', '23:27', 473)],\n",
              " ('CDG', 'FCO'): [('6:25', '9:30', 335),\n",
              "  ('7:34', '9:40', 324),\n",
              "  ('9:15', '12:29', 225),\n",
              "  ('11:28', '14:40', 248),\n",
              "  ('12:05', '15:30', 330),\n",
              "  ('14:01', '17:24', 338),\n",
              "  ('15:34', '18:11', 326),\n",
              "  ('17:07', '20:04', 291),\n",
              "  ('18:23', '21:35', 134),\n",
              "  ('19:53', '22:21', 173)],\n",
              " ('DUB', 'FCO'): [('6:17', '8:26', 89),\n",
              "  ('8:04', '10:11', 95),\n",
              "  ('9:45', '11:50', 172),\n",
              "  ('11:16', '13:29', 83),\n",
              "  ('12:34', '15:02', 109),\n",
              "  ('13:40', '15:37', 138),\n",
              "  ('15:27', '17:18', 151),\n",
              "  ('17:11', '18:30', 108),\n",
              "  ('18:34', '19:36', 136),\n",
              "  ('20:17', '22:22', 102)],\n",
              " ('FCO', 'BRU'): [('6:09', '9:49', 414),\n",
              "  ('7:57', '11:15', 347),\n",
              "  ('9:49', '13:51', 229),\n",
              "  ('10:51', '14:16', 256),\n",
              "  ('12:20', '16:34', 500),\n",
              "  ('14:20', '17:32', 332),\n",
              "  ('15:49', '20:10', 497),\n",
              "  ('17:14', '20:59', 277),\n",
              "  ('18:44', '22:42', 351),\n",
              "  ('19:57', '23:15', 512)],\n",
              " ('FCO', 'CDG'): [('6:33', '9:14', 172),\n",
              "  ('8:23', '11:07', 143),\n",
              "  ('9:25', '12:46', 295),\n",
              "  ('11:08', '14:38', 262),\n",
              "  ('12:37', '15:05', 170),\n",
              "  ('14:08', '16:09', 232),\n",
              "  ('15:23', '18:49', 150),\n",
              "  ('16:50', '19:26', 304),\n",
              "  ('18:07', '21:30', 355),\n",
              "  ('20:27', '23:42', 169)],\n",
              " ('FCO', 'DUB'): [('6:39', '8:09', 86),\n",
              "  ('8:23', '10:28', 149),\n",
              "  ('9:58', '11:18', 130),\n",
              "  ('10:33', '12:03', 74),\n",
              "  ('12:08', '14:05', 142),\n",
              "  ('13:39', '15:30', 74),\n",
              "  ('15:25', '16:58', 62),\n",
              "  ('17:03', '18:03', 103),\n",
              "  ('18:24', '20:49', 124),\n",
              "  ('19:58', '21:23', 142)],\n",
              " ('FCO', 'LHR'): [('6:58', '9:01', 238),\n",
              "  ('8:19', '11:16', 122),\n",
              "  ('9:58', '12:56', 249),\n",
              "  ('10:32', '13:16', 139),\n",
              "  ('12:01', '13:41', 267),\n",
              "  ('13:37', '15:33', 142),\n",
              "  ('15:50', '18:45', 243),\n",
              "  ('16:33', '18:15', 253),\n",
              "  ('18:17', '21:04', 259),\n",
              "  ('19:46', '21:45', 214)],\n",
              " ('FCO', 'LIS'): [('6:19', '8:13', 239),\n",
              "  ('8:04', '10:59', 136),\n",
              "  ('9:31', '11:43', 210),\n",
              "  ('11:07', '13:24', 171),\n",
              "  ('12:31', '14:02', 234),\n",
              "  ('14:05', '15:47', 226),\n",
              "  ('15:07', '17:21', 129),\n",
              "  ('16:35', '18:56', 144),\n",
              "  ('18:25', '20:34', 205),\n",
              "  ('20:05', '21:44', 172)],\n",
              " ('FCO', 'MAD'): [('6:03', '8:43', 219),\n",
              "  ('7:50', '10:08', 164),\n",
              "  ('9:11', '10:42', 172),\n",
              "  ('10:33', '13:11', 132),\n",
              "  ('12:08', '14:47', 231),\n",
              "  ('14:19', '17:09', 190),\n",
              "  ('15:04', '17:23', 189),\n",
              "  ('17:06', '20:00', 95),\n",
              "  ('18:33', '20:22', 143),\n",
              "  ('19:32', '21:25', 160)],\n",
              " ('LHR', 'FCO'): [('6:08', '8:06', 224),\n",
              "  ('8:27', '10:45', 139),\n",
              "  ('9:15', '12:14', 247),\n",
              "  ('10:53', '13:36', 189),\n",
              "  ('12:08', '14:59', 149),\n",
              "  ('13:40', '15:38', 137),\n",
              "  ('15:23', '17:25', 232),\n",
              "  ('17:08', '19:08', 262),\n",
              "  ('18:35', '20:28', 204),\n",
              "  ('20:30', '23:11', 114)],\n",
              " ('LIS', 'FCO'): [('6:11', '8:31', 249),\n",
              "  ('7:39', '10:24', 219),\n",
              "  ('9:15', '12:03', 99),\n",
              "  ('11:08', '13:07', 175),\n",
              "  ('12:18', '14:56', 172),\n",
              "  ('13:37', '15:08', 250),\n",
              "  ('15:03', '16:42', 135),\n",
              "  ('16:51', '19:09', 147),\n",
              "  ('18:12', '20:17', 242),\n",
              "  ('20:05', '22:06', 261)],\n",
              " ('MAD', 'FCO'): [('6:05', '8:32', 174),\n",
              "  ('8:25', '10:34', 157),\n",
              "  ('9:42', '11:32', 169),\n",
              "  ('11:01', '12:39', 260),\n",
              "  ('12:44', '14:17', 134),\n",
              "  ('14:22', '16:32', 126),\n",
              "  ('15:58', '18:40', 173),\n",
              "  ('16:43', '19:00', 246),\n",
              "  ('18:48', '21:45', 246),\n",
              "  ('19:50', '22:24', 269)]}"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "a1V3DNay0IjW",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d6de0585-6723-4fed-a2d7-3579827c5ffa"
      },
      "source": [
        "voos[('LIS', 'FCO')]"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('6:11', '8:31', 249),\n",
              " ('7:39', '10:24', 219),\n",
              " ('9:15', '12:03', 99),\n",
              " ('11:08', '13:07', 175),\n",
              " ('12:18', '14:56', 172),\n",
              " ('13:37', '15:08', 250),\n",
              " ('15:03', '16:42', 135),\n",
              " ('16:51', '19:09', 147),\n",
              " ('18:12', '20:17', 242),\n",
              " ('20:05', '22:06', 261)]"
            ]
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "L3kABr7G0OPq",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7b3b6918-7b5a-4343-e59b-bdd43f241dd9"
      },
      "source": [
        "voos[('FCO', 'LIS')]"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('6:19', '8:13', 239),\n",
              " ('8:04', '10:59', 136),\n",
              " ('9:31', '11:43', 210),\n",
              " ('11:07', '13:24', 171),\n",
              " ('12:31', '14:02', 234),\n",
              " ('14:05', '15:47', 226),\n",
              " ('15:07', '17:21', 129),\n",
              " ('16:35', '18:56', 144),\n",
              " ('18:25', '20:34', 205),\n",
              " ('20:05', '21:44', 172)]"
            ]
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NzPvuuaW1Wb2",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "cd27020f-64f1-48ae-d34e-0dc7ffc2c327"
      },
      "source": [
        "agenda = [1,2, 3,2, 7,3, 6,3, 2,4, 5,3]\n",
        "len(agenda)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "12"
            ]
          },
          "metadata": {},
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "J6c97ssM2aga",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3aff8386-8092-4f8b-fd69-1fd48719a6e5"
      },
      "source": [
        "len(agenda) // 2"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6"
            ]
          },
          "metadata": {},
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8bh2eJJ92rkt",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "1f620520-eccf-4bd6-cf74-0803b0e8f7ab"
      },
      "source": [
        "pessoas[1][1]"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'MAD'"
            ]
          },
          "metadata": {},
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fZ3VCkNY2A5-"
      },
      "source": [
        "def imprimir_voos(agenda):\n",
        "  id_voo = -1\n",
        "  total_preco = 0\n",
        "  for i in range(len(agenda) // 2):\n",
        "    nome = pessoas[i][0]\n",
        "    origem = pessoas[i][1]\n",
        "    id_voo += 1\n",
        "    ida = voos[(origem, destino)][agenda[id_voo]]\n",
        "    total_preco += ida[2]\n",
        "    id_voo += 1\n",
        "    volta = voos[(destino, origem)][agenda[id_voo]]\n",
        "    total_preco += volta[2]\n",
        "    print('%10s%10s %5s-%5s %3s %5s-%5s %3s' % (nome, origem, ida[0], ida[1], ida[2],\n",
        "                                                volta[0], volta[1], volta[2]))\n",
        "  print('Preço total: ', total_preco)"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zVPPuyby4IXF",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9af68f9d-0753-4b07-be7b-011259a351b5"
      },
      "source": [
        "agenda = [1,0, 3,2, 7,1, 6,3, 2,4, 5,3]\n",
        "imprimir_voos(agenda)"
      ],
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "    Lisboa       LIS  7:39-10:24 219  6:19- 8:13 239\n",
            "    Madrid       MAD 11:01-12:39 260  9:11-10:42 172\n",
            "     Paris       CDG 17:07-20:04 291  8:23-11:07 143\n",
            "    Dublin       DUB 15:27-17:18 151 10:33-12:03  74\n",
            "  Bruxelas       BRU  9:08-12:12 364 12:20-16:34 500\n",
            "   Londres       LHR 13:40-15:38 137 10:32-13:16 139\n",
            "Preço total:  2689\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ecuxeMa_43Jn",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8ee39d21-9ee4-4fab-f726-f93ac9713b2e"
      },
      "source": [
        "10**12"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1000000000000"
            ]
          },
          "metadata": {},
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GqqEtILuYaj-"
      },
      "source": [
        "## Fitness function"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fH1uo4sm5dyK"
      },
      "source": [
        "def fitness_function(agenda):\n",
        "  id_voo = -1\n",
        "  total_preco = 0\n",
        "  for i in range(len(agenda) // 2):\n",
        "    origem = pessoas[i][1]\n",
        "    id_voo += 1\n",
        "    ida = voos[(origem, destino)][agenda[id_voo]]\n",
        "    total_preco += ida[2]\n",
        "    id_voo += 1\n",
        "    volta = voos[(destino, origem)][agenda[id_voo]]\n",
        "    total_preco += volta[2]\n",
        "  \n",
        "  return total_preco"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OSaGBRB25_Xk",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ab60d186-5d1a-4c71-9aed-35a5986a9841"
      },
      "source": [
        "agenda = [1,7, 3,1, 1,1, 6,3, 2,4, 5,3]\n",
        "fitness_function(agenda)"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2619"
            ]
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Bqmj2a3A8lSA",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "98200d7d-e817-45ec-dcac-8159e1c9ab76"
      },
      "source": [
        "!pip install mlrose"
      ],
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting mlrose\n",
            "  Downloading mlrose-1.3.0-py3-none-any.whl (27 kB)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.7/dist-packages (from mlrose) (1.19.5)\n",
            "Requirement already satisfied: sklearn in /usr/local/lib/python3.7/dist-packages (from mlrose) (0.0)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.7/dist-packages (from mlrose) (1.4.1)\n",
            "Requirement already satisfied: scikit-learn in /usr/local/lib/python3.7/dist-packages (from sklearn->mlrose) (0.22.2.post1)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.7/dist-packages (from scikit-learn->sklearn->mlrose) (1.0.1)\n",
            "Installing collected packages: mlrose\n",
            "Successfully installed mlrose-1.3.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hleIBozb8toR",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b20f1dc6-1d3f-46b5-83cd-680f72d380c5"
      },
      "source": [
        "import mlrose"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/sklearn/externals/six.py:31: FutureWarning: The module is deprecated in version 0.21 and will be removed in version 0.23 since we've dropped support for Python 2.7. Please rely on the official version of six (https://pypi.org/project/six/).\n",
            "  \"(https://pypi.org/project/six/).\", FutureWarning)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sgqWculR8yqo"
      },
      "source": [
        "fitness = mlrose.CustomFitness(fitness_function)"
      ],
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HWQKJU3w9DGr"
      },
      "source": [
        "problema = mlrose.DiscreteOpt(length=12, fitness_fn=fitness, \n",
        "                              maximize = False, max_val = 10)"
      ],
      "execution_count": 23,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pMo4HJcsnGVT"
      },
      "source": [
        "## Hill climb"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wrWp0PbxFY2a",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "261e2c6c-dc78-4517-9be5-e8ab96112ca2"
      },
      "source": [
        "melhor_solucao, melhor_custo = mlrose.hill_climb(problema, random_state = 1)\n",
        "melhor_solucao, melhor_custo"
      ],
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(array([2, 6, 5, 7, 8, 1, 3, 6, 0, 2, 9, 1]), 1566.0)"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cFm4OyLPGXgp",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fa5f9b58-8898-487a-9c2f-3c59f5595b6e"
      },
      "source": [
        "imprimir_voos(melhor_solucao)"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "    Lisboa       LIS  9:15-12:03  99 15:07-17:21 129\n",
            "    Madrid       MAD 14:22-16:32 126 17:06-20:00  95\n",
            "     Paris       CDG 18:23-21:35 134  8:23-11:07 143\n",
            "    Dublin       DUB 11:16-13:29  83 15:25-16:58  62\n",
            "  Bruxelas       BRU  6:12-10:22 230  9:49-13:51 229\n",
            "   Londres       LHR 20:30-23:11 114  8:19-11:16 122\n",
            "Preço total:  1566\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JbDgA_MuGgLU",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2ae0ecca-62af-4c15-b2b2-1e49d53982ff"
      },
      "source": [
        "voos[('BRU', 'FCO')]"
      ],
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('6:12', '10:22', 230),\n",
              " ('7:53', '11:37', 433),\n",
              " ('9:08', '12:12', 364),\n",
              " ('10:30', '14:57', 290),\n",
              " ('12:19', '15:25', 342),\n",
              " ('13:54', '18:02', 294),\n",
              " ('15:44', '18:55', 382),\n",
              " ('16:52', '20:48', 448),\n",
              " ('18:26', '21:29', 464),\n",
              " ('20:07', '23:27', 473)]"
            ]
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mgHnSkdacDEp"
      },
      "source": [
        "## Simulated annealing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TM9bez7II2V3",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9744aabd-9611-402b-f133-8b5723cf2a64"
      },
      "source": [
        "melhor_solucao, melhor_custo = mlrose.simulated_annealing(problema, \n",
        "                                                          schedule=mlrose.decay.GeomDecay(init_temp=10000),\n",
        "                                                          random_state=1)\n",
        "melhor_solucao, melhor_custo"
      ],
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(array([6, 7, 4, 9, 8, 4, 1, 0, 0, 3, 5, 3]), 1820.0)"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zfhQV3U_K0nH",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1fdd63da-bb83-401e-aaad-986c61032f4a"
      },
      "source": [
        "imprimir_voos(melhor_solucao)"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "    Lisboa       LIS 15:03-16:42 135 16:35-18:56 144\n",
            "    Madrid       MAD 12:44-14:17 134 19:32-21:25 160\n",
            "     Paris       CDG 18:23-21:35 134 12:37-15:05 170\n",
            "    Dublin       DUB  8:04-10:11  95  6:39- 8:09  86\n",
            "  Bruxelas       BRU  6:12-10:22 230 10:51-14:16 256\n",
            "   Londres       LHR 13:40-15:38 137 10:32-13:16 139\n",
            "Preço total:  1820\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Zt7GvTvc1dnQ"
      },
      "source": [
        "## Algoritmo genético"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tYlwF-n2XtMm",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6a18997a-1c69-4a1f-88fe-c03d5388865c"
      },
      "source": [
        "melhor_solucao, melhor_custo = mlrose.genetic_alg(problema, pop_size=500, mutation_prob=0.2,\n",
        "                                                  random_state=1)\n",
        "melhor_solucao, melhor_custo"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(array([7, 3, 1, 2, 9, 0, 3, 8, 0, 3, 4, 1]), 1956.0)"
            ]
          },
          "metadata": {},
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7Vfden9jYn1j",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d45b26a2-8892-4f96-d841-b668bb45487b"
      },
      "source": [
        "imprimir_voos(melhor_solucao)"
      ],
      "execution_count": 30,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "    Lisboa       LIS 16:51-19:09 147 11:07-13:24 171\n",
            "    Madrid       MAD  8:25-10:34 157  9:11-10:42 172\n",
            "     Paris       CDG 19:53-22:21 173  6:33- 9:14 172\n",
            "    Dublin       DUB 11:16-13:29  83 18:24-20:49 124\n",
            "  Bruxelas       BRU  6:12-10:22 230 10:51-14:16 256\n",
            "   Londres       LHR 12:08-14:59 149  8:19-11:16 122\n",
            "Preço total:  1956\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "daLCip2uiOLJ"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Z5ycfP3iQ3F"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}