Algorithms For Dummies

 Challenging Difficult Problems

whereas maze-solving algorithms try to solve the problem in complete ignorance 

of where the exit is.

Consequently, the procedure for simulating a maze of obstacles that a robot has to 

navigate takes a different and simpler approach. Instead of creating a riddle of 

obstacles, you create a graph of vertexes arranged in a grid (resembling a map) 

and  randomly  remove  connections  to  simulate  the  presence  of  obstacles.  The 

graph is undirected (you can traverse each edge in both directions) and weighted 

because it takes time to move from one vertex to another. In particular, it takes 

longer to move diagonally than to move upward/downward or left/right.

The first step is to import the necessary Python packages. The code defines the 

Euclidean and the Manhattan distance functions next. (You can find this code in 

the 

A4D; 20; Heuristic Algorithms.ipynb

 file on the Dummies site as part of 

the downloadable code; see the Introduction for details.)

import numpy as np

import string

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

def euclidean_dist(a, b, coord):

    (x1, y1) = coord[a]

    (x2, y2) = coord[b]

    return np.sqrt((x1-x2)**2

+(y1-y2)**2)

def manhattan_dist(a, b, coord):

    (x1, y1) = coord[a]

    (x2, y2) = coord[b]

    return abs(x1 - x2) 

+ abs(y1 - y2)

def non_informative(a,b):

    return 0

The next step creates a function to generate random mazes. It’s based on an inte-

ger number seed of your choice that allows you to recreate the same maze every 

time  you  provide  the  same  number.  Otherwise,  maze  generation  is  completely 

random.

def create_maze(seed=2, drawing=True):

    np.random.seed(seed)

    letters = [l for l in string.ascii_uppercase[:25]]

    checkboard = np.array(letters[:25]).reshape((5,5))

---

CHAPTER 20