SHARE
TWEET

Untitled

a guest Mar 20th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # ИИ для прохождения ИГРЫ 8 алгоритмом Поиска A* и функией Манхетена
  2.  
  3. import random
  4. import math
  5.  
  6. _goal_state = [[1,2,3],
  7.                [4,5,6],
  8.                [7,8,0]]
  9.  
  10. def index(item, seq):
  11.     if item in seq:
  12.         return seq.index(item)
  13.     else:
  14.         return -1
  15.  
  16. class EightPuzzle:
  17.  
  18.     def __init__(self):
  19.         # результат эврестической функции
  20.         self._hval = 0
  21.         # Глубина дерева
  22.         self._depth = 0
  23.         # Родительская нода
  24.         self._parent = None
  25.         self.adj_matrix = []
  26.         for i in range(3):
  27.             self.adj_matrix.append(_goal_state[i][:])
  28.  
  29.     def __eq__(self, other):
  30.         if self.__class__ != other.__class__:
  31.             return False
  32.         else:
  33.             return self.adj_matrix == other.adj_matrix
  34.  
  35.     def __str__(self):
  36.         res = ''
  37.         for row in range(3):
  38.             res += ' '.join(map(str, self.adj_matrix[row]))
  39.             res += '\r\n'
  40.         return res
  41.  
  42.     def _clone(self):
  43.         p = EightPuzzle()
  44.         for i in range(3):
  45.             p.adj_matrix[i] = self.adj_matrix[i][:]
  46.         return p
  47.  
  48.     def _get_legal_moves(self):
  49.         """Находит пути для движения"""
  50.         row, col = self.find(0)
  51.         free = []
  52.        
  53.         if row > 0:
  54.             free.append((row - 1, col))
  55.         if col > 0:
  56.             free.append((row, col - 1))
  57.         if row < 2:
  58.             free.append((row + 1, col))
  59.         if col < 2:
  60.             free.append((row, col + 1))
  61.  
  62.         return free
  63.  
  64.     def _generate_moves(self):
  65.         """Генерируем движение"""
  66.         free = self._get_legal_moves()
  67.         zero = self.find(0)
  68.  
  69.         def swap_and_clone(a, b):
  70.             p = self._clone()
  71.             p.swap(a,b)
  72.             p._depth = self._depth + 1
  73.             p._parent = self
  74.             return p
  75.  
  76.         return map(lambda pair: swap_and_clone(zero, pair), free)
  77.  
  78.     def _generate_solution_path(self, path):
  79.         if self._parent == None:
  80.             return path
  81.         else:
  82.             path.append(self)
  83.             return self._parent._generate_solution_path(path)
  84.  
  85.     def solve(self, h):
  86.         """Алгоритм поиска А*
  87.         h() эврестическая функция
  88.         """
  89.         def is_solved(puzzle):
  90.             return puzzle.adj_matrix == _goal_state
  91.  
  92.         openl = [self]
  93.         closedl = []
  94.         move_count = 0
  95.         while len(openl) > 0:
  96.             x = openl.pop(0)
  97.             move_count += 1
  98.             if (is_solved(x)):
  99.                 if len(closedl) > 0:
  100.                     return x._generate_solution_path([]), move_count
  101.                 else:
  102.                     return [x]
  103.  
  104.             succ = x._generate_moves()
  105.             idx_open = idx_closed = -1
  106.             for move in succ:
  107.                 idx_open = index(move, openl)
  108.                 idx_closed = index(move, closedl)
  109.                 hval = h(move)
  110.                 fval = hval + move._depth
  111.  
  112.                 if idx_closed == -1 and idx_open == -1:
  113.                     move._hval = hval
  114.                     openl.append(move)
  115.                 elif idx_open > -1:
  116.                     copy = openl[idx_open]
  117.                     if fval < copy._hval + copy._depth:
  118.                         copy._hval = hval
  119.                         copy._parent = move._parent
  120.                         copy._depth = move._depth
  121.                 elif idx_closed > -1:
  122.                     copy = closedl[idx_closed]
  123.                     if fval < copy._hval + copy._depth:
  124.                         move._hval = hval
  125.                         closedl.remove(copy)
  126.                         openl.append(move)
  127.  
  128.             closedl.append(x)
  129.             openl = sorted(openl, key=lambda p: p._hval + p._depth)
  130.  
  131.         # Если невозможно найти путь будет выведена ошибка
  132.         return [], 0
  133.  
  134.     def shuffle(self, step_count):
  135.         for i in range(step_count):
  136.             row, col = self.find(0)
  137.             free = self._get_legal_moves()
  138.             target = random.choice(free)
  139.             self.swap((row, col), target)            
  140.             row, col = target
  141.  
  142.     def find(self, value):
  143.         if value < 0 or value > 8:
  144.             raise Exception("value out of range")
  145.  
  146.         for row in range(3):
  147.             for col in range(3):
  148.                 if self.adj_matrix[row][col] == value:
  149.                     return row, col
  150.    
  151.     def peek(self, row, col):
  152.         """Возвращаем значение ячейки"""
  153.         return self.adj_matrix[row][col]
  154.  
  155.     def poke(self, row, col, value):
  156.         """Устанавливаем значение ячейки"""
  157.         self.adj_matrix[row][col] = value
  158.  
  159.     def swap(self, pos_a, pos_b):
  160.         """Заменяет ячейки при движении"""
  161.         temp = self.peek(*pos_a)
  162.         self.poke(pos_a[0], pos_a[1], self.peek(*pos_b))
  163.         self.poke(pos_b[0], pos_b[1], temp)
  164.  
  165.  
  166. def heur(puzzle, item_total_calc, total_calc):
  167.     """Эврестическая функция"""
  168.     t = 0
  169.     for row in range(3):
  170.         for col in range(3):
  171.             val = puzzle.peek(row, col) - 1
  172.             target_col = val % 3
  173.             target_row = val / 3
  174.  
  175.             if target_row < 0:
  176.                 target_row = 2
  177.  
  178.             t += item_total_calc(row, target_row, col, target_col)
  179.  
  180.     return total_calc(t)
  181.  
  182. # Лучшая эврестическая функция для этой задачи это Манхетеновское расстояние
  183. def h_manhattan(puzzle):
  184.     return heur(puzzle, lambda r, tr, c, tc: abs(tr - r) + abs(tc - c), lambda t : t)
  185.  
  186. def h_default(puzzle):
  187.     return 0
  188.  
  189. def main():
  190.     p = EightPuzzle()
  191.     p.shuffle(20)
  192.     print(p)
  193.  
  194.     path, count = p.solve(h_manhattan)
  195.     path.reverse()
  196.     for i in path:
  197.         print(i)
  198.  
  199.     print("Решено за", count, "состояний")
  200.  
  201. if __name__ == "__main__":
  202.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top