So i am learning about search algorithms at the minute, and would appreciate it if someone could provide an explanation of how this implementation of depth first search works, i do understand how depth first search works as a algorithm, but i am struggling to grasp how it has been implemented here.
Thanks for your patience and understanding, Below is the code:
map = {(0, 0): [(1, 0), (0, 1)],
(0, 1): [(1, 1), (0, 2)],
(0, 2): [(1, 2), (0, 3)],
(0, 3): [(1, 3), (0, 4)],
(0, 4): [(1, 4), (0, 5)],
(0, 5): [(1, 5)],
(1, 0): [(2, 0), (1, 1)],
(1, 1): [(2, 1), (1, 2)],
(1, 2): [(2, 2), (1, 3)],
(1, 3): [(2, 3), (1, 4)],
(1, 4): [(2, 4), (1, 5)],
(1, 5): [(2, 5)],
(2, 0): [(3, 0), (2, 1)],
(2, 1): [(3, 1), (2, 2)],
(2, 2): [(3, 2), (2, 3)],
(2, 3): [(3, 3), (2, 4)],
(2, 4): [(3, 4), (2, 5)],
(2, 5): [(3, 5)],
(3, 0): [(4, 0), (3, 1)],
(3, 1): [(4, 1), (3, 2)],
(3, 2): [(4, 2), (3, 3)],
(3, 3): [(4, 3), (3, 4)],
(3, 4): [(4, 4), (3, 5)],
(3, 5): [(4, 5)],
(4, 0): [(5, 0), (4, 1)],
(4, 1): [(5, 1), (4, 2)],
(4, 2): [(5, 2), (4, 3)],
(4, 3): [(5, 3), (4, 4)],
(4, 4): [(5, 4), (4, 5)],
(4, 5): [(5, 5)],
(5, 0): [(5, 1)],
(5, 1): [(5, 2)],
(5, 2): [(5, 3)],
(5, 3): [(5, 4)],
(5, 4): [(5, 5)],
(5, 5): []}
visited = []
path = []
routes = []
def goal_test(node):
if node == (5, 5):
return True
else:
return False
found = False
def dfs(visited, graph, node):
global routes
visited = visited + [node]
if goal_test(node):
routes = routes + [visited]
else:
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
dfs(visited, map, (0, 0))
print(len(routes))
for route in routes:
print(route)
This implementation employs several bad practices:
map is a native Python function, so it is a bad idea to create a variable with that name.
visited should not need to be initialised in the global scope: the caller has no interest in this as it only plays a role in the DFS algorithm itself
routes should not have to be initialised to an empty list either, and it is bad that dfs mutates this global variable. Instead dfs should return that information to the caller. This makes one dfs call self-contained, as it returns the possible routes from the current node to the target. It is up to the caller to extend the routes in this returned collection with an additional node.
The body of goal_test should be written as return node == (5, 5). The if ... else is just translating a boolean value to the same boolean value.
The function goal_test seems overkill when you can just pass an argument to the dfs function that represents the target node. This makes it also more generic, as you don't need to hard-code the target location inside a function.
path and found are initialised but never used.
dfs would run into a stack overflow if the graph would have cycles. It does not happen with the given graph, because that graph is acyclic, but it would be better if you could also rely on this function when giving it cyclic graphs.
dfs will visit the same cell multiple times, as it can be found via different paths (like for instance (2,2)), and so from there it will perform the same DFS search it already did before. This could be made slightly more efficient by storing the result it got from a previous visit to that cell, i.e. we could use memoization. The gain is small, as most time is spent on creating and copying paths. The gain (of using memoization) would be significant if the function would only count the number of paths, and not build them.
Here is an implementation that deals with the above mentioned points. It uses a wrapper function to hide the use of memoization to the caller, and to reduce the number of arguments that need to be passed to dfs:
def search(graph, source, target):
# Use memoization to avoid repetitive DFS from same node,
# Also used to mark a node as visited, to avoid runnning in cycles
memo = dict() # has routes that were already collected
def dfs(node):
if node not in memo: # not been here before
if node == target:
memo[node] = [[target]]
else:
# Mark with None that this node is on the current path
# ...avoiding infinite recursion on a cycle
memo[node] = None # temporary value while not yet back from recursion
memo[node] = [
[node] + route
for neighbour in graph[node]
for route in dfs(neighbour)
if route
]
return memo[node]
return dfs(source)
graph = {(0, 0): [(1, 0), (0, 1)],
# ...etc ...
}
routes = search(graph, (0, 0), (5, 5))
print(len(routes))
for route in routes:
print(route)