迷宫的某些部分没有灯...
from PIL import Image
from IPython import display as disp
from io import BytesIO
def show(im):
b = BytesIO()
im.save(b, format='png')
disp.display(disp.Image(data=b.getvalue(), format='png', embed=True))
darkmaze = Image.open('darkmaze.jpg')
show(darkmaze)
im = darkmaze.convert('L').point(lambda x: 0 if x < 200 else 1, '1')
标黑的部分表示没有灯, 其周围的通路非常难走, 走起来比有灯的地方更加耗时.
def dark(p):
'''p点周围的7x7邻域内只要包含一处黑色的墙则认为没有灯'''
def inner():
for ox in range(-3, 4):
for oy in range(-3, 4):
x, y = p
yield darkmaze.getpixel((x + ox, y + oy)) == (0, 0, 0)
return max(inner())
def cost(p):
'''没灯的地方举步维艰...'''
return 1000 if dark(p) else 1
Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002)
算法流程:
初始化:
来自mathoverflow(该帖子中包含算法导论对应章节的电子版):
Think of what would happen if you "spill water" in the source vertex $s$.
Water would start spreading simultaneously along the edges emanating from $S$. Let the amount of time it takes a water drop to cross an edge be proportional to its weight (that is - interpret the edge weights as "distances" and assume drops move at a constant speed). Then, for each vertex, the information you would like to have is "when did water first arrive here and where did it come from".
This is what Dijkstra's algorithm simulates. Think of the (continuous) water flow processs I described and consider the events of type "water gets to a certain vertex for the first time". These events can be ordered by their time of occurrence. There are $|V|$ such events (assuming the graph is connected). Each iteration of Dijkstra's algorithm celebrates one such event. Ordering the vertices by the number of the iteration where they where extracted from $Q$ and added to $S$ is the same as ordering them by the "time when water first arrived".
详细算法描述参考维基百科.
start = (402, 984)
end = (398, 24)
top, right, bottom, left = 22, 793, 986, 7
def forbidden(p):
x, y = p
return x < left or y < top or x > right or y > bottom or im.getpixel(p) == 0
prev = {start: None}
next = [start]
closed = {}
d = {start: 0}
while next:
index = min(range(len(next)), key=lambda i: d[next[i]])
source = next.pop(index)
if source == end:
break
if source in closed:
continue
closed[source] = 1
for ox, oy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
x, y = source
target = (x + ox, y + oy)
if not forbidden(target) and target not in closed:
if d[source] + cost(target) < d.get(target, float('inf')):
d[target] = d[source] + cost(target)
prev[target] = source
next.append(target)
path = []
p = end
while p in prev:
path.append(p)
p = prev[p]
path = list(reversed(path))
out = darkmaze.point(lambda p: p / 2).convert('RGB')
for p in path:
out.putpixel(p, (255, 255, 255))
show(out)
首先来看看Dijkstra的效率如何:
def dij():
prev = {start: None}
next = [start]
closed = {}
d = {start: 0}
while next:
index = min(range(len(next)), key=lambda i: d[next[i]])
source = next.pop(index)
if source == end:
break
if source in closed:
continue
closed[source] = 1
for ox, oy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
x, y = source
target = (x + ox, y + oy)
if not forbidden(target) and target not in closed:
if d[source] + cost(target) < d.get(target, float('inf')):
d[target] = d[source] + cost(target)
prev[target] = source
next.append(target)
path = []
p = end
while p in prev:
path.append(p)
p = prev[p]
path = list(reversed(path))
return path
from time import clock
start_time = clock()
path = dij()
print clock() - start_time
105.794972077
做个memo!
def memoed(f):
memo = {}
def inner(*args):
if args not in memo:
memo[args] = f(*args)
return memo[args]
return inner
@memoed
def cost(p):
return 1000 if dark(p) else 1
def dij():
prev = {start: None}
next = [start]
closed = {}
d = {start: 0}
while next:
index = min(range(len(next)), key=lambda i: d[next[i]])
source = next.pop(index)
if source == end:
break
if source in closed:
continue
closed[source] = 1
for ox, oy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
x, y = source
target = (x + ox, y + oy)
if not forbidden(target) and target not in closed:
if d[source] + cost(target) < d.get(target, float('inf')):
d[target] = d[source] + cost(target)
prev[target] = source
next.append(target)
path = []
p = end
while p in prev:
path.append(p)
p = prev[p]
path = list(reversed(path))
return path
from time import clock
start_time = clock()
path = dij()
print clock() - start_time
49.1949072133