Python 实用宝典

Question 1

What is the Python equivalent of Matlab’s tic and toc functions?

Question 2

Apart from timeit which ThiefMaster mentioned, a simple way to do it is just (after importing time):

t = time.time()
# do stuff
elapsed = time.time() - t

I have a helper class I like to use:

class Timer(object):
    def __init__(self, name=None):
        self.name = name

    def __enter__(self):
        self.tstart = time.time()

    def __exit__(self, type, value, traceback):
        if self.name:
            print('[%s]' % self.name,)
        print('Elapsed: %s' % (time.time() - self.tstart))

It can be used as a context manager:

with Timer('foo_stuff'):
   # do some foo
   # do some stuff

Sometimes I find this technique more convenient than timeit – it all depends on what you want to measure.

Question 3

I had the same question when I migrated to python from Matlab. With the help of this thread I was able to construct an exact analog of the Matlab tic() and toc() functions. Simply insert the following code at the top of your script.

import time

def TicTocGenerator():
    # Generator that returns time differences
    ti = 0           # initial time
    tf = time.time() # final time
    while True:
        ti = tf
        tf = time.time()
        yield tf-ti # returns the time difference

TicToc = TicTocGenerator() # create an instance of the TicTocGen generator

# This will be the main function through which we define both tic() and toc()
def toc(tempBool=True):
    # Prints the time difference yielded by generator instance TicToc
    tempTimeInterval = next(TicToc)
    if tempBool:
        print( "Elapsed time: %f seconds.\n" %tempTimeInterval )

def tic():
    # Records a time in TicToc, marks the beginning of a time interval
    toc(False)

That’s it! Now we are ready to fully use tic() and toc() just as in Matlab. For example

tic()

time.sleep(5)

toc() # returns "Elapsed time: 5.00 seconds."

Actually, this is more versatile than the built-in Matlab functions. Here, you could create another instance of the TicTocGenerator to keep track of multiple operations, or just to time things differently. For instance, while timing a script, we can now time each piece of the script seperately, as well as the entire script. (I will provide a concrete example)

TicToc2 = TicTocGenerator() # create another instance of the TicTocGen generator

def toc2(tempBool=True):
    # Prints the time difference yielded by generator instance TicToc2
    tempTimeInterval = next(TicToc2)
    if tempBool:
    print( "Elapsed time 2: %f seconds.\n" %tempTimeInterval )

def tic2():
    # Records a time in TicToc2, marks the beginning of a time interval
    toc2(False)

Now you should be able to time two separate things: In the following example, we time the total script and parts of a script separately.

tic()

time.sleep(5)

tic2()

time.sleep(3)

toc2() # returns "Elapsed time 2: 5.00 seconds."

toc() # returns "Elapsed time: 8.00 seconds."

Actually, you do not even need to use tic() each time. If you have a series of commands that you want to time, then you can write

tic()

time.sleep(1)

toc() # returns "Elapsed time: 1.00 seconds."

time.sleep(2)

toc() # returns "Elapsed time: 2.00 seconds."

time.sleep(3)

toc() # returns "Elapsed time: 3.00 seconds."

# and so on...

I hope that this is helpful.

Question 4

The absolute best analog of tic and toc would be to simply define them in python.

def tic():
    #Homemade version of matlab tic and toc functions
    import time
    global startTime_for_tictoc
    startTime_for_tictoc = time.time()

def toc():
    import time
    if 'startTime_for_tictoc' in globals():
        print "Elapsed time is " + str(time.time() - startTime_for_tictoc) + " seconds."
    else:
        print "Toc: start time not set"

Then you can use them as:

tic()
# do stuff
toc()

Question 5

Usually, IPython’s %time, %timeit, %prun and %lprun (if one has line_profiler installed) satisfy my profiling needs quite well. However, a use case for tic-toc-like functionality arose when I tried to profile calculations that were interactively driven, i.e., by the user’s mouse motion in a GUI. I felt like spamming tics and tocs in the sources while testing interactively would be the fastest way to reveal the bottlenecks. I went with Eli Bendersky’s Timer class, but wasn’t fully happy, since it required me to change the indentation of my code, which can be inconvenient in some editors and confuses the version control system. Moreover, there may be the need to measure the time between points in different functions, which wouldn’t work with the with statement. After trying lots of Python cleverness, here is the simple solution that I found worked best:

from time import time
_tstart_stack = []

def tic():
    _tstart_stack.append(time())

def toc(fmt="Elapsed: %s s"):
    print fmt % (time() - _tstart_stack.pop())

Since this works by pushing the starting times on a stack, it will work correctly for multiple levels of tics and tocs. It also allows one to change the format string of the toc statement to display additional information, which I liked about Eli’s Timer class.

For some reason I got concerned with the overhead of a pure Python implementation, so I tested a C extension module as well:

#include <Python.h>
#include <mach/mach_time.h>
#define MAXDEPTH 100

uint64_t start[MAXDEPTH];
int lvl=0;

static PyObject* tic(PyObject *self, PyObject *args) {
    start[lvl++] = mach_absolute_time();
    Py_RETURN_NONE;
}

static PyObject* toc(PyObject *self, PyObject *args) {
return PyFloat_FromDouble(
        (double)(mach_absolute_time() - start[--lvl]) / 1000000000L);
}

static PyObject* res(PyObject *self, PyObject *args) {
    return tic(NULL, NULL), toc(NULL, NULL);
}

static PyMethodDef methods[] = {
    {"tic", tic, METH_NOARGS, "Start timer"},
    {"toc", toc, METH_NOARGS, "Stop timer"},
    {"res", res, METH_NOARGS, "Test timer resolution"},
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
inittictoc(void) {
    Py_InitModule("tictoc", methods);
}

This is for MacOSX, and I have omitted code to check if lvl is out of bounds for brevity. While tictoc.res() yields a resolution of about 50 nanoseconds on my system, I found that the jitter of measuring any Python statement is easily in the microsecond range (and much more when used from IPython). At this point, the overhead of the Python implementation becomes negligible, so that it can be used with the same confidence as the C implementation.

I found that the usefulness of the tic-toc-approach is practically limited to code blocks that take more than 10 microseconds to execute. Below that, averaging strategies like in timeit are required to get a faithful measurement.

Question 6

You can use tic and toc from ttictoc. Install it with

pip install ttictoc

And just import them in your script as follow

from ttictoc import tic,toc
tic()
# Some code
print(toc())

Question 7

I have just created a module [tictoc.py] for achieving nested tic tocs, which is what Matlab does.

from time import time

tics = []

def tic():
    tics.append(time())

def toc():
    if len(tics)==0:
        return None
    else:
        return time()-tics.pop()

And it works this way:

from tictoc import tic, toc

# This keeps track of the whole process
tic()

# Timing a small portion of code (maybe a loop)
tic()

# -- Nested code here --

# End
toc()  # This returns the elapse time (in seconds) since the last invocation of tic()
toc()  # This does the same for the first tic()

I hope it helps.

Question 8

Have a look at the timeit module. It’s not really equivalent but if the code you want to time is inside a function you can easily use it.

Question 9

pip install easy-tictoc

In the code:

from tictoc import tic, toc

tic()

#Some code

toc()

^{Disclaimer: I’m the author of this library.}

Question 10

This can also be done using a wrapper. Very general way of keeping time.

The wrapper in this example code wraps any function and prints the amount of time needed to execute the function:

def timethis(f):
    import time

    def wrapped(*args, **kwargs):
        start = time.time()
        r = f(*args, **kwargs)
        print "Executing {0} took {1} seconds".format(f.func_name,  time.time()-start)
        return r
    return wrapped

@timethis
def thistakestime():
    for x in range(10000000):
        pass

thistakestime()

Question 11

I changed @Eli Bendersky’s answer a little bit to use the ctor __init__() and dtor __del__() to do the timing, so that it can be used more conveniently without indenting the original code:

class Timer(object):
    def __init__(self, name=None):
        self.name = name
        self.tstart = time.time()

    def __del__(self):
        if self.name:
            print '%s elapsed: %.2fs' % (self.name, time.time() - self.tstart)
        else:
            print 'Elapsed: %.2fs' % (time.time() - self.tstart)

To use, simple put Timer(“blahblah”) at the beginning of some local scope. Elapsed time will be printed at the end of the scope:

for i in xrange(5):
    timer = Timer("eigh()")
    x = numpy.random.random((4000,4000));
    x = (x+x.T)/2
    numpy.linalg.eigh(x)
    print i+1
timer = None

It prints out:

1
eigh() elapsed: 10.13s
2
eigh() elapsed: 9.74s
3
eigh() elapsed: 10.70s
4
eigh() elapsed: 10.25s
5
eigh() elapsed: 11.28s

Question 12

Updating Eli’s answer to Python 3:

class Timer(object):
    def __init__(self, name=None, filename=None):
        self.name = name
        self.filename = filename

    def __enter__(self):
        self.tstart = time.time()

    def __exit__(self, type, value, traceback):
        message = 'Elapsed: %.2f seconds' % (time.time() - self.tstart)
        if self.name:
            message = '[%s] ' % self.name + message
        print(message)
        if self.filename:
            with open(self.filename,'a') as file:
                print(str(datetime.datetime.now())+": ",message,file=file)

Just like Eli’s, it can be used as a context manager:

import time 
with Timer('Count'):
    for i in range(0,10_000_000):
        pass

Output:

[Count] Elapsed: 0.27 seconds

I have also updated it to print the units of time reported (seconds) and trim the number of digits as suggested by Can, and with the option of also appending to a log file. You must import datetime to use the logging feature:

import time
import datetime 
with Timer('Count', 'log.txt'):    
    for i in range(0,10_000_000):
        pass

Question 13

Building on Stefan and antonimmo’s answers, I ended up putting

def Tictoc():
    start_stack = []
    start_named = {}

    def tic(name=None):
        if name is None:
            start_stack.append(time())
        else:
            start_named[name] = time()

    def toc(name=None):
        if name is None:
            start = start_stack.pop()
        else:
            start = start_named.pop(name)
        elapsed = time() - start
        return elapsed
    return tic, toc

in a utils.py module, and I use it with a

from utils import Tictoc
tic, toc = Tictoc()

This way

you can simply use tic(), toc() and nest them like in Matlab
alternatively, you can name them: tic(1), toc(1) or tic('very-important-block'), toc('very-important-block') and timers with different names won’t interfere
importing them this way prevents interference between modules using it.

(here toc does not print the elapsed time, but returns it.)

Question 14

I would like to execute the equivalent of the following MATLAB code using NumPy: repmat([1; 1], [1 1 1]). How would I accomplish this?

Question 15

Here is a much better (official) NumPy for Matlab Users link – I’m afraid the mathesaurus one is quite out of date.

The numpy equivalent of repmat(a, m, n) is tile(a, (m, n)).

This works with multiple dimensions and gives a similar result to matlab. (Numpy gives a 3d output array as you would expect – matlab for some reason gives 2d output – but the content is the same).

Matlab:

>> repmat([1;1],[1,1,1])

ans =
     1
     1

Python:

In [46]: a = np.array([[1],[1]])
In [47]: np.tile(a, [1,1,1])
Out[47]: 
array([[[1],
        [1]]])

Question 16

Note that some of the reasons you’d need to use MATLAB’s repmat are taken care of by NumPy’s broadcasting mechanism, which allows you to do various types of math with arrays of similar shape. So if you had, say, a 1600x1400x3 array representing a 3-color image, you could (elementwise) multiply it by [1.0 0.25 0.25] to reduce the amount of green and blue at each pixel. See the above link for more information.

Question 17

See NumPy for Matlab users.

Matlab:

repmat(a, 2, 3)

Numpy:

numpy.kron(numpy.ones((2,3)), a)

Matlib in Numpy (numpy.matlib.repmat()):

numpy.matlib.repmat(a, 2, 3)

Question 18

This is how I understood it out of a bit of fiddling around. Happy to be corrected and hope this helps.

Say you have a matrix M of 2×3 elements. This has two dimensions, obviously.

I could see no difference between Matlab and Python while asking to manipulate the input matrix along the dimensions the matrix already has. Thus the two commands

repmat(M,m,n) % matlab

np.tile(M,(m,n)) # python

are really equivalent for a matrix of rank 2 (two dimensions).

The matters goes counter-intuitive when you ask for repetition/tiling over more dimensions than the input matrix has. Going back to the matrix M of rank two and shape 2×3, it is sufficient to look at what happens to the size/shape of the output matrix. Say the sequence for manipulation is now 1,1,2.

In Matlab

> size(repmat(M,1,1,2))
ans =

    2   3   2

it has copied the first two dimensions (rows and columns) of the input matrix and has repeated that once into a new third dimension (copied twice, that is). True to the naming repmat for repeat matrix.

In Python

>>> np.tile(M,(1,1,2)).shape
(1, 2, 6)

it has applied a different procedure since, I presume, the sequence (1,1,2) is read differently than in Matlab. The number of copies in the direction of columns, rows and out-of-plane dimension are being read from right to left. The resulting object has a different shape from Matlab. One can no longer assert that repmat and tile are equivalent instructions.

In order to get tile to behave like repmat, in Python one has to make sure that the input matrix has as many dimensions as the elements are in the sequence. This is done, for example, by a little preconditioning and creating a related object N

N = M[:,:,np.newaxis]

Then, at the input side one has N.shape = (2,3,1) rather than M.shape = (2,3) and at the output side

>>> np.tile(N,(1,1,2)).shape
(2, 3, 2)

which was the answer of size(repmat(M,1,1,2)). I presume this is because we have guided Python to add the third dimension to the right of (2,3) rather than to its left, so that Python works out the sequence (1,1,2) as it was intended in the Matlab way of reading it.

The element in [:,:,0] in the Python answer for N will contain the same values as the element (:,:,1) the Matlab answer for M.

Finally, I can’t seem to find an equivalent for repmat when one uses the Kronecker product out of

>>> np.kron(np.ones((1,1,2)),M).shape
(1, 2, 6)

unless I then precondition M into N as above. So I would argue that the most general way to move on is to use the ways of np.newaxis.

The game gets trickier when we consider a matrix L of rank 3 (three dimensions) and the simple case of no new dimensions being added in the output matrix. These two seemingly equivalent instructions will not produce the same results

repmat(L,p,q,r) % matlab

np.tile(L,(p,q,r)) # python

because the row, column, out-of-plane directions are (p,q,r) in Matlab and (q,r,p) in Python, which was not visible with rank-2 arrays. There, one has to be careful and obtaining the same results with the two languages would require more preconditioning.

I am aware that this reasoning may well not be general, but I could work it out only this far. Hopefully this invites other fellows to put it to a harder test.

Question 19

Know both tile and repeat.

x = numpy.arange(5)
print numpy.tile(x, 2)
print x.repeat(2)

Question 20

numpy.matlib has a repmat function with a similar interface as the matlab function

from numpy.matlib import repmat
repmat( np.array([[1],[1]]) , 1, 1)

Question 21

>>> import numpy as np

>>> np.repeat(['a','b'], [2,5])

array(['a', 'a', 'b', 'b', 'b', 'b', 'b'], dtype='<U1')

>>> np.repeat([1,2], [2,5])

array([1, 1, 2, 2, 2, 2, 2])

>>> np.repeat(np.array([1,2]), [3]).reshape(2,3)

array([[1, 1, 1],
       [2, 2, 2]])

>>> np.repeat(np.array([1,2]), [2,4]).reshape(3,2)

array([[1, 1],
       [2, 2],
       [2, 2]])

>>> np.repeat(np.matrix('1 2; 3 4'), [2]).reshape(4,2)

matrix([[1, 1],
        [2, 2],
        [3, 3],
        [4, 4]])

Question 22

I have a bunch of MATLAB code from my MS thesis which I now want to convert to Python (using numpy/scipy and matplotlib) and distribute as open-source. I know the similarity between MATLAB and Python scientific libraries, and converting them manually will be not more than a fortnight (provided that I work towards it every day for some time). I was wondering if there was already any tool available which can do the conversion.

Question 23

There are several tools for converting Matlab to Python code.

The only one that’s seen recent activity (last commit from June 2018) is Small Matlab to Python compiler (also developed here: SMOP@chiselapp).

Other options include:

LiberMate: translate from Matlab to Python and SciPy (Requires Python 2, last update 4 years ago).
OMPC: Matlab to Python (a bit outdated).

Also, for those interested in an interface between the two languages and not conversion:

pymatlab: communicate from Python by sending data to the MATLAB workspace, operating on them with scripts and pulling back the resulting data.
Python-Matlab wormholes: both directions of interaction supported.
Python-Matlab bridge: use Matlab from within Python, offers matlab_magic for iPython, to execute normal matlab code from within ipython.
PyMat: Control Matlab session from Python.
pymat2: continuation of the seemingly abandoned PyMat.
mlabwrap, mlabwrap-purepy: make Matlab look like Python library (based on PyMat).
oct2py: run GNU Octave commands from within Python.
pymex: Embeds the Python Interpreter in Matlab, also on File Exchange.
matpy: Access MATLAB in various ways: create variables, access .mat files, direct interface to MATLAB engine (requires MATLAB be installed).
MatPy: Python package for numerical linear algebra and plotting with a MatLab-like interface.

Btw might be helpful to look here for other migration tips:

http://bci2000.org/downloads/BCPy2000/Migration.html

On a different note, though I’m not a fortran fan at all, for people who might find it useful there is:

matlab2fortran

Question 24

There’s also oct2py which can call .m files within python

https://pypi.python.org/pypi/oct2py

It requires GNU Octave, which is highly compatible with MATLAB.

https://www.gnu.org/software/octave/

Question 25

What is the best way to represent and solve a maze given an image?

Given an JPEG image (as seen above), what’s the best way to read it in, parse it into some data structure and solve the maze? My first instinct is to read the image in pixel by pixel and store it in a list (array) of boolean values: True for a white pixel, and False for a non-white pixel (the colours can be discarded). The issue with this method, is that the image may not be “pixel perfect”. By that I simply mean that if there is a white pixel somewhere on a wall it may create an unintended path.

Another method (which came to me after a bit of thought) is to convert the image to an SVG file – which is a list of paths drawn on a canvas. This way, the paths could be read into the same sort of list (boolean values) where True indicates a path or wall, False indicating a travel-able space. An issue with this method arises if the conversion is not 100% accurate, and does not fully connect all of the walls, creating gaps.

Also an issue with converting to SVG is that the lines are not “perfectly” straight. This results in the paths being cubic bezier curves. With a list (array) of boolean values indexed by integers, the curves would not transfer easily, and all the points that line on the curve would have to be calculated, but won’t exactly match to list indices.

I assume that while one of these methods may work (though probably not) that they are woefully inefficient given such a large image, and that there exists a better way. How is this best (most efficiently and/or with the least complexity) done? Is there even a best way?

Then comes the solving of the maze. If I use either of the first two methods, I will essentially end up with a matrix. According to this answer, a good way to represent a maze is using a tree, and a good way to solve it is using the A* algorithm. How would one create a tree from the image? Any ideas?

TL;DR
Best way to parse? Into what data structure? How would said structure help/hinder solving?

UPDATE
I’ve tried my hand at implementing what @Mikhail has written in Python, using numpy, as @Thomas recommended. I feel that the algorithm is correct, but it’s not working as hoped. (Code below.) The PNG library is PyPNG.

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  """ Returns whether (x, y) is approx. a white pixel."""
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3 + i] > 240
  return a

def bfs(s, e, i, visited):
  """ Perform a breadth-first search. """
  frontier = Queue.Queue()
  while s != e:
    for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
      np = tuple(map(operator.add, s, d))
      if is_white(np, i) and np not in visited:
        frontier.put(np)
    visited.append(s)
    s = frontier.get()
  return visited

def main():
  r = png.Reader(filename = "thescope-134.png")
  rows, cols, pixels, meta = r.asDirect()
  assert meta['planes'] == 3 # ensure the file is RGB
  image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
  start, end = (402, 985), (398, 27)
  print bfs(start, end, image2d, [])

Question 26

Here is a solution.

Convert image to grayscale (not yet binary), adjusting weights for the colors so that final grayscale image is approximately uniform. You can do it simply by controlling sliders in Photoshop in Image -> Adjustments -> Black & White.
Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold.
Make sure threshold is selected right. Use the Magic Wand Tool with 0 tolerance, point sample, contiguous, no anti-aliasing. Check that edges at which selection breaks are not false edges introduced by wrong threshold. In fact, all interior points of this maze are accessible from the start.
Add artificial borders on the maze to make sure virtual traveler will not walk around it :)
Implement breadth-first search (BFS) in your favorite language and run it from the start. I prefer MATLAB for this task. As @Thomas already mentioned, there is no need to mess with regular representation of graphs. You can work with binarized image directly.

Here is the MATLAB code for BFS:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p + d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front + 1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back + 1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end + 1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

It is really very simple and standard, there should not be difficulties on implementing this in Python or whatever.

And here is the answer:

Question 27

This solution is written in Python. Thanks Mikhail for the pointers on the image preparation.

An animated Breadth-First Search:

The Completed Maze:

#!/usr/bin/env python

import sys

from Queue import Queue
from PIL import Image

start = (400,984)
end = (398,25)

def iswhite(value):
    if value == (255,255,255):
        return True

def getadjacent(n):
    x,y = n
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]

def BFS(start, end, pixels):

    queue = Queue()
    queue.put([start]) # Wrapping the start tuple in a list

    while not queue.empty():

        path = queue.get() 
        pixel = path[-1]

        if pixel == end:
            return path

        for adjacent in getadjacent(pixel):
            x,y = adjacent
            if iswhite(pixels[x,y]):
                pixels[x,y] = (127,127,127) # see note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "Queue has been exhausted. No answer was found."


if __name__ == '__main__':

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
    base_img = Image.open(sys.argv[1])
    base_pixels = base_img.load()

    path = BFS(start, end, base_pixels)

    path_img = Image.open(sys.argv[1])
    path_pixels = path_img.load()

    for position in path:
        x,y = position
        path_pixels[x,y] = (255,0,0) # red

    path_img.save(sys.argv[2])

Note: Marks a white visited pixel grey. This removes the need for a visited list, but this requires a second load of the image file from disk before drawing a path (if you don’t want a composite image of the final path and ALL paths taken).

A blank version of the maze I used.

Question 28

I tried myself implementing A-Star search for this problem. Followed closely the implementation by Joseph Kern for the framework and the algorithm pseudocode given here:

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))

    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}

    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []

As A-Star is a heuristic search algorithm you need to come up with a function that estimates the remaining cost (here: distance) until the goal is reached. Unless you’re comfortable with a suboptimal solution it should not overestimate the cost. A conservative choice would here be the manhattan (or taxicab) distance as this represents the straight-line distance between two points on the grid for the used Von Neumann neighborhood. (Which, in this case, wouldn’t ever overestimate the cost.)

This would however significantly underestimate the actual cost for the given maze at hand. Therefore I’ve added two other distance metrics squared euclidean distance and the manhattan distance multiplied by four for comparison. These however might overestimate the actual cost, and might therefore yield suboptimal results.

Here’s the code:

import sys
from PIL import Image

def is_blocked(p):
    x,y = p
    pixel = path_pixels[x,y]
    if any(c < 225 for c in pixel):
        return True
def von_neumann_neighbors(p):
    x, y = p
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
    return [p for p in neighbors if not is_blocked(p)]
def manhattan(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def squared_euclidean(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

start = (400, 984)
goal = (398, 25)

# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]

path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()

distance = manhattan
heuristic = manhattan

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)

for position in path:
    x,y = position
    path_pixels[x,y] = (255,0,0) # red

path_img.save(sys.argv[2])

Here are some images for a visualization of the results (inspired by the one posted by Joseph Kern). The animations show a new frame each after 10000 iterations of the main while-loop.

Breadth-First Search:

A-Star Manhattan Distance:

A-Star Squared Euclidean Distance:

A-Star Manhattan Distance multiplied by four:

The results show that the explored regions of the maze differ considerably for the heuristics being used. As such, squared euclidean distance even produces a different (suboptimal) path as the other metrics.

Concerning the performance of the A-Star algorithm in terms of the runtime until termination, note that a lot of evaluation of distance and cost functions add up compared to the Breadth-First Search (BFS) which only needs to evaluate the “goaliness” of each candidate position. Whether or not the cost for these additional function evaluations (A-Star) outweighs the cost for the larger number of nodes to check (BFS) and especially whether or not performance is an issue for your application at all, is a matter of individual perception and can of course not be generally answered.

A thing that can be said in general about whether or not an informed search algorithm (such as A-Star) could be the better choice compared to an exhaustive search (e.g., BFS) is the following. With the number of dimensions of the maze, i.e., the branching factor of the search tree, the disadvantage of an exhaustive search (to search exhaustively) grows exponentially. With growing complexity it becomes less and less feasible to do so and at some point you are pretty much happy with any result path, be it (approximately) optimal or not.

Question 29

Tree search is too much. The maze is inherently separable along the solution path(s).

(Thanks to rainman002 from Reddit for pointing this out to me.)

Because of this, you can quickly use connected components to identify the connected sections of maze wall. This iterates over the pixels twice.

If you want to turn that into a nice diagram of the solution path(s), you can then use binary operations with structuring elements to fill in the “dead end” pathways for each connected region.

Demo code for MATLAB follows. It could use tweaking to clean up the result better, make it more generalizable, and make it run faster. (Sometime when it’s not 2:30 AM.)

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
    k = zeros(1002,800);
    k(result==i) = 1; k = imclose(k,strel('square',8));
    closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
    for y = 1:800
        if closed(x,y) == 0
            out(x,y,:) = 0;
        end
    end
end
imshow(out);

Question 30

Uses a queue for a threshold continuous fill. Pushes the pixel left of the entrance onto the queue and then starts the loop. If a queued pixel is dark enough, it’s colored light gray (above threshold), and all the neighbors are pushed onto the queue.

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")

Solution is the corridor between gray wall and colored wall. Note this maze has multiple solutions. Also, this merely appears to work.

Question 31

Here you go: maze-solver-python (GitHub)

I had fun playing around with this and extended on Joseph Kern‘s answer. Not to detract from it; I just made some minor additions for anyone else who may be interested in playing around with this.

It’s a python-based solver which uses BFS to find the shortest path. My main additions, at the time, are:

The image is cleaned before the search (ie. convert to pure black & white)
Automatically generate a GIF.
Automatically generate an AVI.

As it stands, the start/end-points are hard-coded for this sample maze, but I plan on extending it such that you can pick the appropriate pixels.

Question 32

I’d go for the matrix-of-bools option. If you find that standard Python lists are too inefficient for this, you could use a numpy.bool array instead. Storage for a 1000×1000 pixel maze is then just 1 MB.

Don’t bother with creating any tree or graph data structures. That’s just a way of thinking about it, but not necessarily a good way to represent it in memory; a boolean matrix is both easier to code and more efficient.

Then use the A* algorithm to solve it. For the distance heuristic, use the Manhattan distance (distance_x + distance_y).

Represent nodes by a tuple of (row, column) coordinates. Whenever the algorithm (Wikipedia pseudocode) calls for “neighbours”, it’s a simple matter of looping over the four possible neighbours (mind the edges of the image!).

If you find that it’s still too slow, you could try downscaling the image before you load it. Be careful not to lose any narrow paths in the process.

Maybe it’s possible to do a 1:2 downscaling in Python as well, checking that you don’t actually lose any possible paths. An interesting option, but it needs a bit more thought.

Question 33

Here are some ideas.

(1. Image Processing:)

1.1 Load the image as RGB pixel map. In C# it is trivial using system.drawing.bitmap. In languages with no simple support for imaging, just convert the image to portable pixmap format (PPM) (a Unix text representation, produces large files) or some simple binary file format you can easily read, such as BMP or TGA. ImageMagick in Unix or IrfanView in Windows.

1.2 You may, as mentioned earlier, simplify the data by taking the (R+G+B)/3 for each pixel as an indicator of gray tone and then threshold the value to produce a black and white table. Something close to 200 assuming 0=black and 255=white will take out the JPEG artifacts.

(2. Solutions:)

2.1 Depth-First Search: Init an empty stack with starting location, collect available follow-up moves, pick one at random and push onto the stack, proceed until end is reached or a deadend. On deadend backtrack by popping the stack, you need to keep track of which positions were visited on the map so when you collect available moves you never take the same path twice. Very interesting to animate.

2.2 Breadth-First Search: Mentioned before, similar as above but only using queues. Also interesting to animate. This works like flood-fill in image editing software. I think you may be able to solve a maze in Photoshop using this trick.

2.3 Wall Follower: Geometrically speaking, a maze is a folded/convoluted tube. If you keep your hand on the wall you will eventually find the exit ;) This does not always work. There are certain assumption re: perfect mazes, etc., for instance, certain mazes contain islands. Do look it up; it is fascinating.

(3. Comments:)

This is the tricky one. It is easy to solve mazes if represented in some simple array formal with each element being a cell type with north, east, south and west walls and a visited flag field. However given that you are trying to do this given a hand drawn sketch it becomes messy. I honestly think that trying to rationalize the sketch will drive you nuts. This is akin to computer vision problems which are fairly involved. Perhaps going directly onto the image map may be easier yet more wasteful.

Question 34

Here’s a solution using R.

### download the image, read it into R, converting to something we can play with...
library(jpeg)
url <- "https://i.stack.imgur.com/TqKCM.jpg"
download.file(url, "./maze.jpg", mode = "wb")
jpg <- readJPEG("./maze.jpg")

### reshape array into data.frame
library(reshape2)
img3 <- melt(jpg, varnames = c("y","x","rgb"))
img3$rgb <- as.character(factor(img3$rgb, levels = c(1,2,3), labels=c("r","g","b")))

## split out rgb values into separate columns
img3 <- dcast(img3, x + y ~ rgb)

RGB to greyscale, see: https://stackoverflow.com/a/27491947/2371031

# convert rgb to greyscale (0, 1)
img3$v <- img3$r*.21 + img3$g*.72 + img3$b*.07
# v: values closer to 1 are white, closer to 0 are black

## strategically fill in some border pixels so the solver doesn't "go around":
img3$v2 <- img3$v
img3[(img3$x == 300 | img3$x == 500) & (img3$y %in% c(0:23,988:1002)),"v2"]  = 0

# define some start/end point coordinates
pts_df <- data.frame(x = c(398, 399),
                     y = c(985, 26))

# set a reference value as the mean of the start and end point greyscale "v"s
ref_val <- mean(c(subset(img3, x==pts_df[1,1] & y==pts_df[1,2])$v,
                  subset(img3, x==pts_df[2,1] & y==pts_df[2,2])$v))

library(sp)
library(gdistance)
spdf3 <- SpatialPixelsDataFrame(points = img3[c("x","y")], data = img3["v2"])
r3 <- rasterFromXYZ(spdf3)

# transition layer defines a "conductance" function between any two points, and the number of connections (4 = Manhatten distances)
# x in the function represents the greyscale values ("v2") of two adjacent points (pixels), i.e., = (x1$v2, x2$v2)
# make function(x) encourages transitions between cells with small changes in greyscale compared to the reference values, such that: 
# when v2 is closer to 0 (black) = poor conductance
# when v2 is closer to 1 (white) = good conductance
tl3 <- transition(r3, function(x) (1/max( abs( (x/ref_val)-1 ) )^2)-1, 4) 

## get the shortest path between start, end points
sPath3 <- shortestPath(tl3, as.numeric(pts_df[1,]), as.numeric(pts_df[2,]), output = "SpatialLines")

## fortify for ggplot
sldf3 <- fortify(SpatialLinesDataFrame(sPath3, data = data.frame(ID = 1)))

# plot the image greyscale with start/end points (red) and shortest path (green)
ggplot(img3) +
  geom_raster(aes(x, y, fill=v2)) +
  scale_fill_continuous(high="white", low="black") +
  scale_y_reverse() +
  geom_point(data=pts_df, aes(x, y), color="red") +
  geom_path(data=sldf3, aes(x=long, y=lat), color="green")

Voila!

This is what happens if you don’t fill in some border pixels (Ha!)…

Full disclosure: I asked and answered a very similar question myself before I found this one. Then through the magic of SO, found this one as one of the top “Related Questions”. I thought I’d use this maze as an additional test case… I was very pleased to find that my answer there also works for this application with very little modification.

Question 35

the good solution would be that instead of finding the neighbors by pixel, it would be done by cell, because a corridor can have 15px so in the same corridor it can take actions like left or right, while if it was done as if the displacement was a cube it would be a simple action like UP,DOWN,LEFT OR RIGHT

问题：Matlab的tic和toc函数的Python等效项是什么？

回答 0

回答 1

回答 2

回答 3

回答 4

回答 5

回答 6

回答 7

回答 8

回答 9

回答 10

回答 11

问题：在NumPy中相当于MATLAB的repmat

回答 0

回答 1

回答 2

回答 3

回答 4

回答 5

回答 6

问题：将MATLAB代码转换为Python的工具

回答 0

回答 1

问题：表示并解决给定图像的迷宫

回答 0

回答 1

回答 2

回答 3

回答 4

回答 5

回答 6

回答 7

回答 8

回答 9

问题：在Python中读取.mat文件

回答 0

回答 1

回答 2

回答 3

回答 4

回答 5

回答 6

回答 7

有趣好用的Python教程