Cópia_de_Grafo_Busca_A_Estrela_ORIGINAL.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Cópia de Grafo Busca A Estrela ORIGINAL.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_Grafo_Busca_A_Estrela_ORIGINAL.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r2ZZwVzmSD9w"
      },
      "source": [
        "# Grafo - Busca A Estrela (A*)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PgOWgXWsNWEr"
      },
      "source": [
        "## Grafo"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "37JdH3P_R-pL"
      },
      "source": [
        "class Vertice:\n",
        "\n",
        "  def __init__(self, rotulo, distancia_objetivo):\n",
        "    self.rotulo = rotulo\n",
        "    self.visitado = False\n",
        "    self.distancia_objetivo = distancia_objetivo\n",
        "    self.adjacentes = []\n",
        "\n",
        "  def adiciona_adjacente(self, adjacente):\n",
        "    self.adjacentes.append(adjacente)\n",
        "\n",
        "  def mostra_adjacentes(self):\n",
        "    for i in self.adjacentes:\n",
        "      print(i.vertice.rotulo, i.custo)"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Hj4-etBV6eYP"
      },
      "source": [
        "class Adjacente:\n",
        "  def __init__(self, vertice, custo):\n",
        "    self.vertice = vertice\n",
        "    self.custo = custo\n",
        "\n",
        "    # Novo atributo\n",
        "    self.distancia_aestrela = vertice.distancia_objetivo + self.custo"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "42axhC-b6r-L"
      },
      "source": [
        "class Grafo:\n",
        "  arad = Vertice('Arad', 366)\n",
        "  zerind = Vertice('Zerind', 374)\n",
        "  oradea = Vertice('Oradea', 380)\n",
        "  sibiu = Vertice('Sibiu', 253)\n",
        "  timisoara = Vertice('Timisoara', 329)\n",
        "  lugoj = Vertice('Lugoj', 244)\n",
        "  mehadia = Vertice('Mehadia', 241)\n",
        "  dobreta = Vertice('Dobreta', 242)\n",
        "  craiova = Vertice('Craiova', 160)\n",
        "  rimnicu = Vertice('Rimnicu', 193)\n",
        "  fagaras = Vertice('Fagaras', 178)\n",
        "  pitesti = Vertice('Pitesti', 98)\n",
        "  bucharest = Vertice('Bucharest', 0)\n",
        "  giurgiu = Vertice('Giurgiu', 77)\n",
        "\n",
        "  arad.adiciona_adjacente(Adjacente(zerind, 75))\n",
        "  arad.adiciona_adjacente(Adjacente(sibiu, 140))\n",
        "  arad.adiciona_adjacente(Adjacente(timisoara, 118))\n",
        "\n",
        "  zerind.adiciona_adjacente(Adjacente(arad, 75))\n",
        "  zerind.adiciona_adjacente(Adjacente(oradea, 71))\n",
        "\n",
        "  oradea.adiciona_adjacente(Adjacente(zerind, 71))\n",
        "  oradea.adiciona_adjacente(Adjacente(sibiu, 151))\n",
        "\n",
        "  sibiu.adiciona_adjacente(Adjacente(oradea, 151))\n",
        "  sibiu.adiciona_adjacente(Adjacente(arad, 140))\n",
        "  sibiu.adiciona_adjacente(Adjacente(fagaras, 99))\n",
        "  sibiu.adiciona_adjacente(Adjacente(rimnicu, 80))\n",
        "\n",
        "  timisoara.adiciona_adjacente(Adjacente(arad, 118))\n",
        "  timisoara.adiciona_adjacente(Adjacente(lugoj, 111))\n",
        "\n",
        "  lugoj.adiciona_adjacente(Adjacente(timisoara, 111))\n",
        "  lugoj.adiciona_adjacente(Adjacente(mehadia, 70))\n",
        "\n",
        "  mehadia.adiciona_adjacente(Adjacente(lugoj, 70))\n",
        "  mehadia.adiciona_adjacente(Adjacente(dobreta, 75))\n",
        "\n",
        "  dobreta.adiciona_adjacente(Adjacente(mehadia, 75))\n",
        "  dobreta.adiciona_adjacente(Adjacente(craiova, 120))\n",
        "\n",
        "  craiova.adiciona_adjacente(Adjacente(dobreta, 120))\n",
        "  craiova.adiciona_adjacente(Adjacente(pitesti, 138))\n",
        "  craiova.adiciona_adjacente(Adjacente(rimnicu, 146))\n",
        "\n",
        "  rimnicu.adiciona_adjacente(Adjacente(craiova, 146))\n",
        "  rimnicu.adiciona_adjacente(Adjacente(sibiu, 80))\n",
        "  rimnicu.adiciona_adjacente(Adjacente(pitesti, 97))\n",
        "\n",
        "  fagaras.adiciona_adjacente(Adjacente(sibiu, 99))\n",
        "  fagaras.adiciona_adjacente(Adjacente(bucharest, 211))\n",
        "\n",
        "  pitesti.adiciona_adjacente(Adjacente(rimnicu, 97))\n",
        "  pitesti.adiciona_adjacente(Adjacente(craiova, 138))\n",
        "  pitesti.adiciona_adjacente(Adjacente(bucharest, 101))\n",
        "\n",
        "  bucharest.adiciona_adjacente(Adjacente(fagaras, 211))\n",
        "  bucharest.adiciona_adjacente(Adjacente(pitesti, 101))\n",
        "  bucharest.adiciona_adjacente(Adjacente(giurgiu, 90))"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qBYjaInI-N4c"
      },
      "source": [
        "grafo = Grafo()"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aIjre2EzLXB0"
      },
      "source": [
        "## Vetor ordenado (adjacente)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bHnGlmCQLYoH"
      },
      "source": [
        "import numpy as np\n",
        "class VetorOrdenado:\n",
        "  \n",
        "  def __init__(self, capacidade):\n",
        "    self.capacidade = capacidade\n",
        "    self.ultima_posicao = -1\n",
        "    # Mudança no tipo de dados\n",
        "    self.valores = np.empty(self.capacidade, dtype=object)\n",
        "\n",
        "  # Referência para o vértice e comparação com a distância para o objetivo\n",
        "  def insere(self, adjacente):\n",
        "    if self.ultima_posicao == self.capacidade - 1:\n",
        "      print('Capacidade máxima atingida')\n",
        "      return\n",
        "    posicao = 0\n",
        "    for i in range(self.ultima_posicao + 1):\n",
        "      posicao = i\n",
        "      if self.valores[i].distancia_aestrela > adjacente.distancia_aestrela:\n",
        "        break\n",
        "      if i == self.ultima_posicao:\n",
        "        posicao = i + 1\n",
        "    x = self.ultima_posicao\n",
        "    while x >= posicao:\n",
        "      self.valores[x + 1] = self.valores[x]\n",
        "      x -= 1\n",
        "    self.valores[posicao] = adjacente\n",
        "    self.ultima_posicao += 1\n",
        "\n",
        "  def imprime(self):\n",
        "    if self.ultima_posicao == -1:\n",
        "      print('O vetor está vazio')\n",
        "    else:\n",
        "      for i in range(self.ultima_posicao + 1):\n",
        "        print(i, ' - ', self.valores[i].vertice.rotulo, ' - ', \n",
        "              self.valores[i].custo, ' - ', \n",
        "              self.valores[i].vertice.distancia_objetivo, ' - ',\n",
        "              self.valores[i].distancia_aestrela)  "
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bU6PRlO8L8cl",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8e247163-3bf1-464e-bf80-953dcbe3429c"
      },
      "source": [
        "grafo.arad.adjacentes"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[<__main__.Adjacente at 0x7f9163e1cd50>,\n",
              " <__main__.Adjacente at 0x7f916aca99d0>,\n",
              " <__main__.Adjacente at 0x7f9163e1cd90>]"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7K05OPLaMHar",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1e2140fa-4083-411d-a548-8dc77c272009"
      },
      "source": [
        "grafo.arad.adjacentes[0].vertice.rotulo, grafo.arad.adjacentes[0].vertice.distancia_objetivo"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('Zerind', 374)"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EaU6gA1qMUKJ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2880686e-b9f4-49f3-d24e-9e52c87664dc"
      },
      "source": [
        "grafo.arad.adjacentes[0].distancia_aestrela, grafo.arad.adjacentes[0].custo"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(449, 75)"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "P9p9N7quMX0y"
      },
      "source": [
        "vetor = VetorOrdenado(20)\n",
        "vetor.insere(grafo.arad.adjacentes[0])\n",
        "vetor.insere(grafo.arad.adjacentes[1])\n",
        "vetor.insere(grafo.arad.adjacentes[2])"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vKhUrylgMzJV",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6363f4a5-972e-4094-e334-025bdfb2b23f"
      },
      "source": [
        "vetor.imprime()"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  Sibiu  -  140  -  253  -  393\n",
            "1  -  Timisoara  -  118  -  329  -  447\n",
            "2  -  Zerind  -  75  -  374  -  449\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Lmvbw_KeNYvX"
      },
      "source": [
        "## Busca AEstrela"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vGziamQKNbRN"
      },
      "source": [
        "class AEstrela:\n",
        "  def __init__(self, objetivo):\n",
        "    self.objetivo = objetivo\n",
        "    self.encontrado = False\n",
        "\n",
        "  def buscar(self, atual):\n",
        "    print('------------------')\n",
        "    print('Atual: {}'.format(atual.rotulo))\n",
        "    atual.visitado = True\n",
        "\n",
        "    if atual == self.objetivo:\n",
        "      self.encontrado = True\n",
        "    else:\n",
        "      vetor_ordenado = VetorOrdenado(len(atual.adjacentes))\n",
        "      for adjacente in atual.adjacentes:\n",
        "        if adjacente.vertice.visitado == False:\n",
        "          adjacente.vertice.visitado = True\n",
        "          vetor_ordenado.insere(adjacente)\n",
        "      vetor_ordenado.imprime()\n",
        "\n",
        "      if vetor_ordenado.valores[0] != None:\n",
        "        self.buscar(vetor_ordenado.valores[0].vertice)"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PLEzojkn_WWY",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "845ee813-d16c-4b9d-d629-f8823dee6fdb"
      },
      "source": [
        "busca_aestrela = AEstrela(grafo.bucharest)\n",
        "busca_aestrela.buscar(grafo.arad)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "------------------\n",
            "Atual: Arad\n",
            "0  -  Sibiu  -  140  -  253  -  393\n",
            "1  -  Timisoara  -  118  -  329  -  447\n",
            "2  -  Zerind  -  75  -  374  -  449\n",
            "------------------\n",
            "Atual: Sibiu\n",
            "0  -  Rimnicu  -  80  -  193  -  273\n",
            "1  -  Fagaras  -  99  -  178  -  277\n",
            "2  -  Oradea  -  151  -  380  -  531\n",
            "------------------\n",
            "Atual: Rimnicu\n",
            "0  -  Pitesti  -  97  -  98  -  195\n",
            "1  -  Craiova  -  146  -  160  -  306\n",
            "------------------\n",
            "Atual: Pitesti\n",
            "0  -  Bucharest  -  101  -  0  -  101\n",
            "------------------\n",
            "Atual: Bucharest\n"
          ]
        }
      ]
    }
  ]
}