Advertisement
IcaroPeretti

mc

Apr 3rd, 2022
1,006
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.03 KB | None
  1. import sys
  2. import math
  3. import numpy as np
  4.  
  5. # 0 - 3 Missionários lado esquerdo
  6. # 1 - 3 Canibais do lado esquerdo
  7. # 2 - 0 Missionários do lado direito
  8. # 3 - 0 Canibais lado direito
  9. # 4 - Lado da canoa 0 - Esq - 1 Dir
  10. initial_state = [3, 3, 0, 0, 0]
  11.  
  12.  
  13. # (1,0) - Atravessar 1 missionário
  14. # (2,0) - Atravessar 2 missionários
  15. # (1,1) - Atravessar 1 canibal e 1 missionário
  16. # (0,2) - Atravessar 2 canibais
  17. # (0,1) - Atravessar 1 canibal
  18. operators = [(1, 0), (1, 1), (2, 0), (0, 2)]
  19.  
  20. board = []
  21. visited_nodes = []
  22.  
  23.  
  24. def deslocateBoat(state, numMiss=0, numCan=0):
  25.     # Comporta apenas 2 no barco
  26.     if numMiss + numCan > 2:
  27.         return
  28.  
  29.     # Testa a última posição, se for 0 a canoa ta a esquerda
  30.     # Se for 1 esta a esquerda
  31.     print(numCan, numMiss)
  32.     if state[-1] == 0:
  33.         missionariesOrigin = 0
  34.         cannibalsOrigin = 1
  35.         missionariesDest = 2
  36.         cannibalsDest = 3
  37.     else:
  38.         missionariesOrigin = 2
  39.         cannibalsOrigin = 3
  40.         missionariesDest = 0
  41.         cannibalsDest = 1
  42.  
  43.     # Caso não haja oque transportar
  44.     if state[missionariesOrigin] == 0 and state[cannibalsOrigin] == 0:
  45.         return
  46.  
  47.     # Atualizar a posição da canoa
  48.  
  49.     # Se é 1 passa a ser 0 e se é 0 passa a ser 1
  50.     state[-1] = 1 - state[-1]
  51.  
  52.     # Deslocamento dos missionários
  53.     # Remove 1 missioário da origem e aumenta 1 no destino
  54.     # Verifica se a quantitade de missionários é menor que a quantidade de missionários no estado
  55.     for i in range(min(numMiss, state[missionariesOrigin])):
  56.         state[missionariesOrigin] -= 1
  57.         state[missionariesDest] += 1
  58.  
  59.     # Deslocamento Canibais
  60.     for i in range(min(numCan, state[cannibalsOrigin])):
  61.         state[cannibalsOrigin] -= 1
  62.         state[cannibalsDest] += 1
  63.  
  64.     print("Range", range(min(numMiss, state[missionariesOrigin])))
  65.     return state
  66.  
  67.  
  68. def successors(estadoAtual):
  69.     arraySucessors = []  # armazenar os sucessores
  70.  
  71.     # Par ordenado que informa a quantidade de canibais e missionários a serem transferidos
  72.     for (i, j) in operators:
  73.         # cópia do array, i  missionários e j canibais
  74.         # Retorna um estado possivel a partir do estado original
  75.  
  76.         sucessor = deslocateBoat(estadoAtual[:], i, j)
  77.         print("MOVE:", deslocateBoat(estadoAtual[:], i, j))
  78.         print("Successor", sucessor)
  79.         print(estadoAtual[:])
  80.         if sucessor == None:  # se estiver vazio
  81.             continue
  82.  
  83.         # Aplicando as regras do problema
  84.         # O número de missionários não pode ser menor que o de canibais
  85.         if(sucessor[0] < sucessor[1] and sucessor[0] > 0) or (sucessor[2] < sucessor[3] and sucessor[2] > 0):
  86.             continue
  87.  
  88.         # Verifica sucessor gerado já foi visitado
  89.         if sucessor in visited_nodes:
  90.             continue  # verificação de ESTADOS REPETIDOS
  91.  
  92.         # Adiciona o sucessor ao array de sucessores
  93.         arraySucessors.append(sucessor)
  94.  
  95.     print(arraySucessors)
  96.  
  97.     return arraySucessors
  98.  
  99.  
  100. successors(initial_state)
  101.  
  102.  
  103. def calculateCost(state):
  104.     left = (state[0], state[1])
  105.     right = (state[2], state[3])
  106.  
  107.     cost = math.dist(left, right)  # calculo euclidiano
  108.  
  109.     heuristic = state[0] + state[1]
  110.  
  111.     result = cost + heuristic
  112.     return result
  113.  
  114.  
  115. def getAdjacentNotVisited(stateToVerify):
  116.     saveCosts = []
  117.     adj = successors(stateToVerify)
  118.    
  119.     if len(adj) > 0:
  120.         for x in adj:
  121.             saveCosts.append(calculateCost(x))
  122.  
  123.             minValue = min(saveCosts)
  124.             return adj[saveCosts.index(minValue)]
  125.     else:
  126.         return -1
  127.  
  128.  
  129. # Verifica se os canibais e missionários foram transportados
  130. def finalTest(finalState):
  131.     if finalState[2] == 3 and finalState[3] == 3:
  132.         return True
  133.     else:
  134.         return False
  135.  
  136.  
  137. def search(initial_state):
  138.     board.append(initial_state)
  139.     while len(board) != 0:
  140.         stateToCheck = board[len(board)-1]
  141.  
  142.         # Se encontrar a solução, para o loop
  143.         if finalTest(stateToCheck):
  144.             print("Solucao encontrada")
  145.             break
  146.         adjReturn = getAdjacentNotVisited(stateToCheck)
  147.         if adjReturn == -1:  # se retorna -1, não existe então tira o elemento
  148.             board.pop()
  149.         else:  # se não retorna -1, adiciona aos visited_nodes e adiciona a board
  150.             visited_nodes.append(adjReturn)
  151.             board.append(adjReturn)
  152.     else:
  153.         print("Caminho não encontrado")
  154.     return board  # se estado atual for a board, será listado o caminho do estado inicial ate o estado final
  155.  
  156.  
  157. def showSolution():
  158.     solution = search(initial_state)
  159.     for i in range(1, len(solution)):
  160.         missionariesRight = abs(solution[i][0] - solution[i-1][0])
  161.         cannibalsRight = abs(solution[i][1] - solution[i-1][1])
  162.         boat = solution[i][4] - solution[i-1][4]
  163.  
  164.         if boat == 1:
  165.             s = "direita"
  166.         else:
  167.             s = "esquerda"
  168.         print(solution[i-1],
  169.               "({},{},{})".format(missionariesRight, cannibalsRight, s))
  170.  
  171.  
  172. showSolution()
  173.  
Advertisement
RAW Paste Data Copied
Advertisement