Abstract: hunt the shortest way in a map
The result:
Initiate queue: [0, (1, 1), None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
(1, 1) (1, 2) [(1, 2)]
(1, 1) (2, 1) [(1, 2), (2, 1)]
(1, 2) (2, 2) [(2, 1), (2, 2)]
(2, 1) (3, 1) [(2, 2), (3, 1)]
(2, 2) (2, 3) [(3, 1), (2, 3)]
(2, 2) (3, 2) [(3, 1), (2, 3), (3, 2)]
(3, 1) (4, 1) [(2, 3), (3, 2), (4, 1)]
(2, 3) (2, 4) [(3, 2), (4, 1), (2, 4)]
(4, 1) (5, 1) [(2, 4), (5, 1)]
(2, 4) (1, 4) [(5, 1), (1, 4)]
(2, 4) (3, 4) [(5, 1), (1, 4), (3, 4)]
(5, 1) (5, 2) [(1, 4), (3, 4), (5, 2)]
(3, 4) (4, 4) [(5, 2), (4, 4)]
(5, 2) (5, 3) [(4, 4), (5, 3)]
(4, 4) (4, 3) [(5, 3), (4, 3)]
The shortest ways: [(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (4, 3)]
The steps: 7
ok
The script:
# -*- coding: utf-8 -*-
"""
Created on Tue Jul 21 10:21:31 2015
@author: yuan
"""
import numpy as np
#the shortest way from (x,y) to (m,n) on a map
#record a queue using circling list
class queue:
def __init__(self,arr, q_len=1):
self.size=len(arr)
if q_len==1 or q_len<self.size:
self.q=[None]*self.size
self.q_len=self.size
else:
self.q=[None]*q_len
self.q_len=q_len
self.q[0]=0
self.q[1:self.size]=arr
self.head=1 #skip the index 0
self.tail=len(arr)+1 #the index of next element of arr
print 'Initiate queue:', self.q
def q_size(self):
#print 'Size of the queue:', self.size
return self.size
def export_arr(self):
if self.tail>self.head:
arr=self.q[self.head:self.tail]
elif self.tail==self.head:
arr=[]
else:
arr=self.q[self.head:(self.q_len+1)] + self.q[1:self.tail]
return arr
def enqueue(self, value):
if self.size<self.q_len:
#increase size
self.size +=1
#increase tail
if self.tail==(self.q_len+1):
self.tail=1
#add value
self.q[self.tail]=value
self.tail += 1
else:
print "queue is full, fail to adding", value
#print '##', self.q, self.head,self.tail
#return self.export_arr()
def dequeue(self):
#increase head
value='NA'
#print self.head, self.tail
if self.size>0:
value=self.q[self.head]
if self.head==self.q_len:
self.head=1
else:
self.head +=1
#decrease size
self.size -= 1
#print 'remove', value, self.export_arr()
return value
##################
class breadth_first_search(queue):
def __init__(self, pool,start,end):
self.pool=np.array(pool)
self.nrow=len(pool)
self.ncol=len(pool[1:])
self.start=start
self.end=end # book if reach the end point
self.next=[[0,1],[0,-1],[-1,0],[1,0]]
self.book=list(self.pool)#book those visited points
self.flag=0
def export_ways(self):
point=self.end
ways=[point]
if self.flag==1:
while point!=start:
x=point[0]
y=point[1]
point=self.book[x][y]#father point
ways.insert(0, point)
steps=len(ways)-1
print 'The shortest ways:', ways
print 'The steps:', steps
else:
print 'No ways!'
return ways
def shortest_way(self):
q=queue([start], self.nrow*self.ncol)
self.book[start[0]][start[1]]=start #book start point
while q.q_size()>0:
point=q.dequeue()
for i in range(4):
x=point[0]+self.next[i][0]
y=point[1]+self.next[i][1]
#print x,y
#judge if beyond bound
if x<1 or x>=self.nrow or y<1 or y>=self.ncol:
continue
#if obstacle or already passed
if self.pool[x][y]==0 and self.book[x][y]==0:
new_point=(x,y)
q.enqueue(new_point)
self.book[x][y]=point
print point, new_point, q.export_arr()
if x==self.end[0] and y==self.end[1]:
self.flag=1
break
if self.flag==1:
break
ways=self.export_ways()
return ways
#main
if __name__ == "__main__":
#0 empty, 1 obstcle, None null
pool=[ [None,None,None,None,None],[None,0,0,1,0], [None,0,0,0,0],
[None,0,0,1,0], [None,0,1,0,0],[None,0,0,0,1]]
#coordinate of the start point
start=(1,1)
end=(4,3)
#coordinate of the end point
s=breadth_first_search(pool, start, end)
out=s.shortest_way()
print 'ok'
No comments:
Post a Comment