Liebe CB'ler,
aktuell lerne ich mit einem Online-Kurs Python. Die erste Projekt-Aufgabe: das 8-Puzzle Game mit verschiedenen Tree-Search Algorithmen lösen. Bisher habe ich mich an Breath-First-Search und Deep-First-Search gewagt. Ersteres funktioniert auch sehr gut. Lösungen werden immer gefunden, die Laufzeit ist nur leicht länger der Referenzwert des Profs, ...
Bei Deep-Search (dfs) sieht es leider anders aus. Mein Alogrithmus such bis zu einer halben Minute lang und bricht dann mit "Memory Error" ab.
Mein Ansatz: das 8-Puzzle wird in ein numpy-array geladen. Das zu verschiebende Kästchen ist die 0. Bei jeder neuer Puzzlezusammensetzung wird die 0 gesucht, dann geschaut in welche Richtungen das Kästchen verschoben werden kann. Alle daraus resultierenden Puzzle werden in die FiFo-Schlange (bfs) oder den LiFo-Stack (dfs) gespeichert, WENN diese nicht schon in der Schlange/Stack sind oder nicht schon untersucht wurden.
Meiner Meinung nach ist diese Überprüfung "Ist Puzzle schon bekannt" genau das Problem. Bei dfs reden wir über eine 5-6 stellige Zahl von Puzzlen. Wie kann ich überprüfen, wo die Komplexität in meinem Code liegt?
Hat jemand eine Idee, wo ich verschlanken und verbessern kann? Würdet mir sehr helfen.
aktuell lerne ich mit einem Online-Kurs Python. Die erste Projekt-Aufgabe: das 8-Puzzle Game mit verschiedenen Tree-Search Algorithmen lösen. Bisher habe ich mich an Breath-First-Search und Deep-First-Search gewagt. Ersteres funktioniert auch sehr gut. Lösungen werden immer gefunden, die Laufzeit ist nur leicht länger der Referenzwert des Profs, ...
Bei Deep-Search (dfs) sieht es leider anders aus. Mein Alogrithmus such bis zu einer halben Minute lang und bricht dann mit "Memory Error" ab.
Mein Ansatz: das 8-Puzzle wird in ein numpy-array geladen. Das zu verschiebende Kästchen ist die 0. Bei jeder neuer Puzzlezusammensetzung wird die 0 gesucht, dann geschaut in welche Richtungen das Kästchen verschoben werden kann. Alle daraus resultierenden Puzzle werden in die FiFo-Schlange (bfs) oder den LiFo-Stack (dfs) gespeichert, WENN diese nicht schon in der Schlange/Stack sind oder nicht schon untersucht wurden.
Meiner Meinung nach ist diese Überprüfung "Ist Puzzle schon bekannt" genau das Problem. Bei dfs reden wir über eine 5-6 stellige Zahl von Puzzlen. Wie kann ich überprüfen, wo die Komplexität in meinem Code liegt?
Hat jemand eine Idee, wo ich verschlanken und verbessern kann? Würdet mir sehr helfen.
Code:
import sys
import numpy as np
import math
import copy
import time
from collections import deque
def move_up(board, zero):
if zero[0, 0] != 0:
move_board = copy.deepcopy(board)
temp = move_board[zero[0, 0] - 1, zero[0, 1]]
move_board[zero[0, 0] - 1, zero[0, 1]] = 0
move_board[zero[0, 0], zero[0, 1]] = temp
return move_board
def move_down(board, zero):
if zero[0, 0] != math.sqrt(board_size) - 1:
move_board = copy.deepcopy(board)
temp = move_board[zero[0, 0] + 1, zero[0, 1]]
move_board[zero[0, 0] + 1, zero[0, 1]] = 0
move_board[zero[0, 0], zero[0, 1]] = temp
return move_board
def move_left(board, zero):
if zero[0, 1] != 0:
move_board = copy.deepcopy(board)
temp = move_board[zero[0, 0], zero[0, 1]-1]
move_board[zero[0, 0], zero[0, 1]-1] = 0
move_board[zero[0, 0], zero[0, 1]] = temp
return move_board
def move_right(board, zero):
if zero[0, 1] != math.sqrt(board_size) - 1:
move_board = copy.deepcopy(board)
temp = move_board[zero[0, 0], zero[0, 1]+1]
move_board[zero[0, 0], zero[0, 1]+1] = 0
move_board[zero[0, 0], zero[0, 1]] = temp
return move_board
def new_node(board, path, depth, cost):
return Node(board, path, depth, cost)
class Node:
def __init__(self, board, path, depth, cost):
self.board = board
self.path = path
self.depth = depth
self.cost = cost
def bfs(start_board):
# starting parameters
bfs_queue = deque()
explored_boards = set()
max_queue = 0
nodes_expanded = 0
# start timer for search
start_time = time.time()
# put initial board in queue and in explored_boards
explored_boards.add(tuple(map(tuple, initial_board)))
bfs_queue.append(new_node(start_board, [], 0, 0))
while len(bfs_queue) != 0:
# save max length of fringe
if max_queue < len(bfs_queue):
max_queue = len(bfs_queue)
# pull new board instance to test
explore = bfs_queue.popleft()
if np.array_equal(explore.board, goal_board):
return explore, bfs_queue, start_time, nodes_expanded, max_queue
else:
print('Depth: ' + str(explore.depth) + ' | Nodes: ' + str(nodes_expanded) +
' | Time: ' + str(time.time()-start_time))
# search for child nodes
nodes_expanded += 1
zero = np.argwhere(explore.board == 0)
up = move_up(explore.board, zero)
if (up is not None) and (tuple(map(tuple, up)) not in explored_boards):
explored_boards.add(tuple(map(tuple, up)))
bfs_queue.append(new_node(up, explore.path + ['Up'], explore.depth + 1, 0))
down = move_down(explore.board, zero)
if (down is not None) and (tuple(map(tuple, down)) not in explored_boards):
explored_boards.add(tuple(map(tuple, down)))
bfs_queue.append(new_node(down, explore.path + ['Down'], explore.depth + 1, 0))
left = move_left(explore.board, zero)
if (left is not None) and (tuple(map(tuple, left)) not in explored_boards):
explored_boards.add(tuple(map(tuple, left)))
bfs_queue.append(new_node(left, explore.path + ['Left'], explore.depth + 1, 0))
right = move_right(explore.board, zero)
# Hier spare ich 1x Tuple anlegen, hat jedoch keinen Einfluss auf mein Problem
tuple_right = tuple(map(tuple, right))
if (right is not None) and (tuple_right not in explored_boards):
explored_boards.add(tuple_right)
bfs_queue.append(new_node(right, explore.path + ['Right'], explore.depth + 1, 0))
def dfs(start_board):
# starting parameters
dfs_stack = []
explored_boards = set()
max_stack = 0
nodes_expanded = 0
# start timer for search
start_time = time.time()
# put initial board in queue and in explored_boards
explored_boards.add(tuple(map(tuple, initial_board)))
dfs_stack.append(new_node(start_board, [], 0, 0))
while len(dfs_stack) != 0:
# save max length of fringe
if max_stack < len(dfs_stack):
max_stack = len(dfs_stack)
# pull new board instance to test
explore = dfs_stack.pop()
explored_boards.add(tuple(map(tuple, explore.board)))
if np.array_equal(explore.board, goal_board):
return explore, dfs_stack, start_time, nodes_expanded, max_stack
else:
print('Depth: ' + str(explore.depth) + ' | Nodes: ' + str(nodes_expanded) +
' | Time: ' + str(time.time()-start_time))
# search for child nodes
nodes_expanded += 1
zero = np.argwhere(explore.board == 0)
right = move_right(explore.board, zero)
if (right is not None) and (tuple(map(tuple, right)) not in explored_boards):
explored_boards.add(tuple(map(tuple, right)))
board_right = new_node(right, explore.path + ['Right'], explore.depth + 1, 0)
dfs_stack.append(board_right)
left = move_left(explore.board, zero)
if (left is not None) and (tuple(map(tuple, left)) not in explored_boards):
explored_boards.add(tuple(map(tuple, left)))
board_left = new_node(left, explore.path + ['Left'], explore.depth + 1, 0)
dfs_stack.append(board_left)
down = move_down(explore.board, zero)
if (down is not None) and (tuple(map(tuple, down)) not in explored_boards):
explored_boards.add(tuple(map(tuple, down)))
board_down = new_node(down, explore.path + ['Down'], explore.depth + 1, 0)
dfs_stack.append(board_down)
up = move_up(explore.board, zero)
if (up is not None) and (tuple(map(tuple, up)) not in explored_boards):
explored_boards.add(tuple(map(tuple, up)))
board_up = new_node(up, explore.path + ['Up'], explore.depth + 1, 0)
dfs_stack.append(board_up)
# Catch input parameters
program_name = sys.argv[0]
sorting_alg = sys.argv[1]
board_input = sys.argv[2]
# create initial board matrix with integer values
board_list = board_input.split(',')
board_size = int(len(board_list))
initial_board = np.reshape(np.array(board_list), (-1, int(math.sqrt(board_size))))
initial_board = initial_board.astype(np.integer)
# create goal board based on input arguments for reference
goal_board = np.reshape(np.array(list(range(0, board_size))), (-1, int(math.sqrt(board_size))))
goal_board = goal_board.astype(np.integer)
# program executes based on wanted sorting algorithm
if sorting_alg == 'bfs':
result = bfs(initial_board)
print('path_to_goal: ' + str(result[0].path))
print('cost_of_path: ' + str(len(result[0].path)))
print('nodes_expanded: ' + str(result[3]))
print('fringe_size: ' + str(len(result[1])))
print('max_fringe_size: ' + str(result[4]))
print('search_depth: ' + str(result[0].depth))
print('max_search_depth: ')
print('running_time: ' + str(time.time() - result[2]))
print('max_ram_usage: ')
if sorting_alg == 'dfs':
result = dfs(initial_board)
print('path_to_goal: ' + str(result[0].path))
print('cost_of_path: ' + str(len(result[0].path)))
print('nodes_expanded: ' + str(result[3]))
print('fringe_size: ' + str(len(result[1])))
print('max_fringe_size: ' + str(result[4]))
print('search_depth: ' + str(result[0].depth))
print('max_search_depth: ')
print('running_time: ' + str(time.time() - result[2]))
print('max_ram_usage: ')
if sorting_alg == 'ast':
print('Function not implemented yet!')
if sorting_alg == 'ida':
print('Function not implemented yet!')
