Advertisement
IcaroPeretti

CNSemDist

Apr 5th, 2022 (edited)
664
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import math
  3. # coding: utf-8 #
  4.  
  5.  
  6. class State():
  7.     def __init__(self, leftMiss, rightMiss, leftCann, rightCann, boatSide):
  8.         self.node = None
  9.         self.childrens = []
  10.         self.leftMiss = leftMiss
  11.         self.rightMiss = rightMiss
  12.         self.leftCann = leftCann
  13.         self.rightCann = rightCann
  14.         self.boatSide = boatSide
  15.  
  16.     def __repr__(self):
  17.         from pprint import pformat
  18.         return pformat(vars(self), indent=4, width=1)
  19.  
  20.     def validState(self):
  21.         # Não permitir missionarios ou canibais negativos
  22.         if ((self.leftMiss < 0)
  23.             or (self.leftCann < 0)
  24.             or (self.rightMiss < 0)
  25.                 or (self.rightCann < 0)):
  26.             return False
  27.  
  28.         # Não permitir mais canibais que missionários
  29.         if((self.leftMiss == 0 or self.leftMiss >= self.leftCann) and
  30.            (self.rightMiss == 0 or self.rightMiss >= self.rightCann)):
  31.             return True
  32.  
  33.     def createChildren(self):
  34.         possible_moves = [
  35.             [1, 0], [1, 1], [0, 2], [2, 0], [0, 1]
  36.         ]
  37.  
  38.         # Gera os possíveis estados e armazena apenas os válidos no estado atual
  39.         for move in possible_moves:
  40.             if self.boatSide == 0:
  41.                # Barco na esquerda, ambos saem da esquerda pra direita
  42.  
  43.                 # movimentação dos missionarios da direita para a esquerda
  44.                 leftMiss = self.leftMiss - move[0]
  45.                 rightMiss = self.rightMiss + move[0]
  46.  
  47.                 # movimentação dos cannibais da direita para a esquerda
  48.                 leftCann = self.leftCann - move[1]
  49.                 rightCann = self.rightCann + move[1]
  50.  
  51.                 # Criação do estado do filho
  52.                 children = State(leftMiss, rightMiss,
  53.                                  leftCann, rightCann, 1)
  54.             else:
  55.                # Barco na direita, ambos saem da direita pra esquerda
  56.  
  57.                 # movimentação dos missionarios da esquerda para a direita
  58.                 rightMiss = self.rightMiss - move[0]
  59.                 leftMiss = self.leftMiss + move[0]
  60.  
  61.                 # movimentação dos cannibais da esquerda para a direita
  62.                 rightCann = self.rightCann - move[1]
  63.                 leftCann = self.leftCann + move[1]
  64.  
  65.                 # Criação do estado do filho
  66.                 children = State(leftMiss, rightMiss,
  67.                                  leftCann, rightCann, 0)
  68.  
  69.             # adiciona a lista
  70.             children.node = self
  71.  
  72.             # validação de estado
  73.             if children.validState():
  74.                 # adiciona como filhos do pai
  75.                 self.childrens.append(children)
  76.  
  77.     def finalState(self):
  78.         if ((self.rightMiss and self.rightCann) == 3 and
  79.            (self.leftMiss and self.leftCann) == 0):
  80.             return True
  81.         else:
  82.             return False
  83.  
  84.     def calculateEuclidianDistance(self):
  85.         left = (self.leftMiss, self.leftCann)
  86.         right = (self.rightMiss, self.rightCann)
  87.  
  88.         cost = math.dist(left, right)
  89.  
  90.         heuristic = self.leftMiss + self.rightMiss
  91.         result = cost + heuristic
  92.         return result
  93.  
  94.  
  95. class Tree():
  96.     def __init__(self):
  97.         self.state = [State(3, 0, 3, 0, 0)]
  98.         self.solution = None
  99.  
  100.     def resolveProblem(self):
  101.         for element in self.state:
  102.             if element.finalState():
  103.                 # Se o elemento for o final, armazena o caminho
  104.                 self.solution = [element]
  105.                 while element.node:
  106.                     self.solution.insert(0, element.node)
  107.                     element = element.node
  108.                 break
  109.  
  110.             # Se o elemento nao solucionar gera os filhos no state
  111.             element.createChildren()
  112.  
  113.             self.state.extend(element.childrens)
  114.  
  115.  
  116. problem = Tree()
  117. problem.resolveProblem()
  118.  
  119. i = 0
  120. for state in problem.solution:
  121.  
  122.     i += 1
  123.     print(
  124.         "Passo", i,
  125.         '\nLeft Miss', state.leftMiss, 'Right Miss', state.rightMiss, '\n'
  126.         'Left Cann:', state.leftCann,  'Right Cann', state.rightCann, '\nBoat side:', state.boatSide, '\n', 50*'--'
  127.     )
  128.  
Advertisement
RAW Paste Data Copied
Advertisement