<jupyter_start><jupyter_text>Busca Não InformadaNeste notebook, exploraremos alguns algoritmos clássicos de busca cega (i.e., não informada, sem informação, etc.).Considere o grafo abaixo:![img1](https://github.com/ufrpe-ia/intro-ia/blob/master/assets/images/img_buscas_01.png?raw=true) Classe GraphUtilizaremos como base uma implementação de um grafo simples em python:<jupyter_code>from collections import defaultdict
from pprint import pprint 

class Graph():
  def __init__(self):
    self.neighbors = defaultdict(list)
    self.cost = defaultdict(list)

  def show_graph(self):
    print("Destinations:");
    pprint(dict(self.neighbors))
    
    print("Costs:");
    pprint(dict(self.cost))
    
  def add_edge(self, source, destination, price):
    self.neighbors[source].append(destination)
    self.cost[source].append(price)<jupyter_output><empty_output><jupyter_text>Algoritmo 1: Busca em largura (BFS)<jupyter_code>from collections import defaultdict
from pprint import pprint 

class GraphBFS(Graph):
  
  def bfs(self, start='S', end = 'G'):
    
    visited = []
    fringe = [(start,0,start)] # (node, cost-to-node, path-to-node)
    
    while len(fringe) > 0:
      
      node = fringe[0]

      fringe.remove(node)  
      visited.append(node[0])

      ################
      # inserir elementos na fronteira sem ordem
      for n,c in zip(self.neighbors[node[0]], self.cost[node[0]]):
        if n not in visited:
          fringe.append((n,c+node[1],node[2]+n))
      ################
      
      print('visited:' , node[0], '(', node[2], ') | fringe:', fringe)
      if node[0] == end:
        print('FIM: ', node[2], ' Cost:', node[1])
        break<jupyter_output><empty_output><jupyter_text>Adicionando os elementos ao grafo:<jupyter_code>g = GraphBFS()

g.add_edge('S', 'A', 2)
g.add_edge('S', 'B', 1)
g.add_edge('S', 'G', 9)
g.add_edge('A', 'C', 2)
g.add_edge('A', 'D', 3)
g.add_edge('B', 'D', 2)
g.add_edge('B', 'E', 4)
g.add_edge('C', 'G', 4)
g.add_edge('D', 'G', 4)

g.show_graph()
g.bfs(start='S', end = 'G')<jupyter_output><empty_output><jupyter_text>Algoritmo 2: Busca em Profundidade:<jupyter_code># Exercicio!<jupyter_output><empty_output><jupyter_text>Algoritmo 3: Busca de Custo Uniforme<jupyter_code>class GraphUC(GraphBFS):
  def uniformCost(self,  start='S', end = 'G'):

    visited = []
    fringe = [(start,0,start)] # (node, cost-to-node, path-to-node)
    
    while len(fringe) > 0:
      
      node = fringe[0]

      fringe.remove(node)  
      visited.append(node[0])

      for n,c in zip(self.neighbors[node[0]], self.cost[node[0]]):
        if n not in visited:
          fringe.append((n,c+node[1],node[2]+n))
          
      ################
      # sort fringe
      fringe = sorted(fringe, key=lambda x: x[1])
      ################
      
      print('visited:' , node[0], '(', node[2], ') | fringe:', fringe)
      if node[0] == end:
        print('FIM: ', node[2], ' Cost:', node[1])
        break
        
    
g = GraphUC()
g.add_edge('S', 'A', 2)
g.add_edge('S', 'B', 1)
g.add_edge('S', 'G', 9)
g.add_edge('A', 'C', 2)
g.add_edge('A', 'D', 3)
g.add_edge('B', 'D', 2)
g.add_edge('B', 'E', 4)
g.add_edge('C', 'G', 4)
g.add_edge('D', 'G', 4)

g.uniformCost(start='S', end = 'G')<jupyter_output><empty_output><jupyter_text>Exemplo 2: Malha aéreaConsidere o seguinte grafo representando uma malha aérea:<jupyter_code>f = GraphUC()
f.add_edge('Los Angeles', 'New Delhi', 200)
f.add_edge('Los Angeles', 'Japan', 87)
f.add_edge('Germany', 'New Delhi', 125)
f.add_edge('Italy', 'Los Angeles', 150)
f.add_edge('New Delhi', 'France', 100)
f.add_edge('Los Angeles', 'France', 200)
f.add_edge('Italy', 'New Delhi', 300)
f.add_edge('France', 'Norway', 175)
f.add_edge('Ireland', 'Chicago', 100)
f.add_edge('Chicago', 'Italy', 135)
f.add_edge('Los Angeles', 'Ireland', 100)
f.add_edge('Ireland', 'New Delhi', 200)
f.show_graph()<jupyter_output><empty_output><jupyter_text>Executando BFS, DFS e CustoUniforme:<jupyter_code>f.bfs(start='Los Angeles', end='Norway')
print()
f.uniformCost(start='Los Angeles', end='Norway')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.19502681618722575, 'fraction_numerical': 0.0212091662603608, 'mean_word_length': 4.2201017811704835, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 31, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '609172', 'license': 'MIT', 'n_tokens_mistral': 1715, 'n_tokens_neox': 1607, 'n_words': 318, 'path': '00-buscas/01_Buscas_BDS_DFS_CustoUniforme.ipynb', 'repo_name': 'ufrpe-ensino/ia-aulas', 'size': '4102'}