So I have a 12 x 6 2D numpy array for input which consists of 7 possible board objects (characters from 'abcdefg'). From a 2D numpy array I wish to generate all the possible unique 2D arrays, in whose parent array 2 adjacent elements in each row have been swapped. In the worst case this means 60 (5*12) swaps for each parent node. However 2 adjacent elements can be the same, so I omit the duplicate nodes where a swap doesn't generate a unique child array. For instance, given an array (simplified case):
np.array([['a', 'a', 'c'], ['d', 'e', 'f'], ['g', 'a', 'b']])
I would get the following visited tuples for depth 1 (not in order of swapping cause it's a set):
(('a', 'a', 'c'), ('d', 'e', 'f'), ('a', 'g', 'b')) (('a', 'a', 'c'), ('d', 'e', 'f'), ('g', 'b', 'a')) (('a', 'c', 'a'), ('d', 'e', 'f'), ('g', 'a', 'b')) (('a', 'a', 'c'), ('d', 'e', 'f'), ('g', 'a', 'b')) # parent node (('a', 'a', 'c'), ('e', 'd', 'f'), ('g', 'a', 'b')) (('a', 'a', 'c'), ('d', 'f', 'e'), ('g', 'a', 'b'))
The aforementioned function is ran through a breadth-first search function, where given a certain depth, it will find all the unique visited nodes (as a set of tuple of tuples). Since the complexity of BFS is O(b^n), the non unique positions generated would be at least 60^4 (for depth 4), and under a billion for depth 5. For my current implementation depth 4 takes 80-90 seconds, depth 3 is about 2-3 seconds. My goal would be to try and optimize it to 5 seconds max for depth 5, which would be a satisfactory result. Here is the code:
import numpy as np import time B = np.array([['a', 'a', 'c', 'a', 'a', 'b'], ['d', 'e', 'f', 'a', 'b', 'c'], ['a', 'b', 'd', 'd', 'e', 'b'], ['b', 'c', 'f', 'd', 'e', 'e'], ['a', 'b', 'd', 'b', 'd', 'd'], ['b', 'c', 'f', 'f', 'e', 'e'], ['d', 'e', 'f', 'g', 'b', 'c'], ['d', 'e', 'f', 'a', 'b', 'c'], ['a', 'b', 'd', 'b', 'd', 'd'], ['b', 'c', 'f', 'f', 'e', 'e'], ['d', 'e', 'f', 'a', 'b', 'c'], ['d', 'e', 'f', 'a', 'g', 'c']], dtype=object) def elementswap_getchildren(matrix): height, width = matrix.shape for i, j in [(i, j) for i in range(height) for j in range(width - 1) if (matrix[i, j] != matrix[i, j + 1])]: child = matrix.copy() child[i, j], child[i, j + 1] = child[i, j + 1], child[i, j] yield child def bfs(initial, depth): visited = set() queue = [initial] i, j, k, toggle = 0, 0, 0, 0 while queue: node = queue.pop(0) node_tuple = tuple(map(tuple, node)) if node_tuple not in visited: visited.add(node_tuple) if depth != 0: for child in elementswap_getchildren(node): queue.append(child) i += 1 if toggle == 0: k = i depth -= 1 toggle = 1 j += 1 if j == k: k = i if depth != 0: depth -= 1 return visited start = time.time() results = bfs(B, 3) end = time.time() print('Visited', len(results), 'positions') print('This took', end - start, 'seconds')
Needles to say, most of the bottleneck is likely from the following areas that I have not been able to find a more optimal solution to:
- Using for loops instead of a vectorized way to do
a, b = b, abut I haven't been able to figure out how to reduce that.
- Having to use
copy()on the argument 2D array for a temporary matrix every iteration of i*j. If I didn't use it inside the inner loop, each child wouldn't be swapping elements in the argument matrix (while keeping the argument matrix unchanged), but swapping elements in their earlier iterations, which is what I don't need.
queuelist in the BFS grows very big, about 50000 on depth 3. I'm not accessing it at all during operation, only pop()'ing it. It may be something I cannot implement differently due to it being essential to BFS.
Another thing to point out is, I intend to give each unique board state, that is found before the max depth, a score/value depending on certain combinations of characters present. This will increase overhead, as well as reduce number of branches, because they do not need to be investigated further. But I refrain from complicating this problem before the tree search can't be further optimized.
This is my first time actually coding something this performance/optimization orientated, so I am simply stuck due to inexperience and lack of knowledge in further optimization.
Any help or pointers are welcome, as well as suggesting a completely different approach.