我只能做一个无向图。不知道如何制作一个定向的。
任何想法？
问问题
490 次
3 回答
1
Apologies for the rather long winded post. I had time to kill on the train.
I'm guessing what you're after is a directed graph representing all paths leading away from your starting position (as opposed to a graph representation of the maze which once can use to solve arbitrary start/end positions).
(No offence meant, but) this sounds like homework, or at least, a task that is very suitable for homework. With this in mind, the following solution focuses on simplicity rather than performance or elegance.
Approach
One straight-forward way to do this would be to first store your map in a more navigable format, then, beginning with the start node do the following:
- look up neighbours (top, bottom, left, right)
- for each neighbour:
- if it is not a possible path, ignore
- if we have processed this node before, ignore
- else, add this node as an edge and push it a queue (not a stack, more on this later) for further processing
- for each node in the queue/stack, repeat from step 1.
(See example implementation below)
At this point, you'll end up with a directed acyclic graph (DAG) with the starting node at the top of the tree and end node as one of the leaves. Solving this would be easy at this point. See this answer on solving a maze representing as a graph.
A possible optimisation when building the graph would be to stop once the end point is found. You'll end up with an incomplete graph, but if you're only concerned about the final solution this doesn't matter.
stack or queue?
Note that using a stack (first in last out) would mean building the graph in a depth-first manner, while using a queue (first in first out) would result in a breadth-first approach.
You would generally want to use a queue (breadth first if the intention is to look for the shortest path. Consider the following map:
START
######## ######
######## ######
### b a ######
### ## ######
### ## e ######
### c d ######
######## ######
######## END
#################
If the path is traversed depth-first and at branch a you happen take the a->b path before a->e, you end up with the graph:
START
|
a
/ \
b e <-- end, since d already visited
|
c
|
d
\
END
However, using a breadth-first approach the a->e path would come across node d earlier, resulting in a shorter graph and a better solution:
START
|
a
/ \
b e
| |
c d
|
END
Example code
Sample input provided:
..........
#########.
..........
.#########
......#...
#####...#.
##...####.
##.#......
...#######
e = (0,0)
s = (8,0)
DISCLAIMER: The following code is written for clarity, not speed. It is not fully tested so there is no guarantee of correctness but it should give you an idea of what is possible.
We assumes that the input file is formatted consistently. Most error checking left out for brevity.
# regex to extract start/end positions
import re
re_sepos = re.compile("""
^([se])\s* # capture first char (s or e) followed by arbitrary spaces
=\s* # equal sign followed by arbitrary spaces
\( # left parenthesis
(\d+),(\d+) # capture 2 sets of integers separated by comma
\) # right parenthesis
""", re.VERBOSE)
def read_maze(filename):
"""
Reads input from file and returns tuple (maze, start, end)
maze : dict holding value of each maze cell { (x1,y1):'#', ... }
start: start node coordinage (x1,y1)
end : end node coordinate (x2,y2)
"""
# read whole file into a list
f = open(filename, "r")
data = f.readlines()
f.close()
# parse start and end positions from last 2 lines
pos = {}
for line in data[-2:]:
match = re_sepos.match(line)
if not match:
raise ValueError("invalid input file")
c,x,y = match.groups() # extract values
pos[c] = (int(x),int(y))
try:
start = pos["s"]
end = pos["e"]
except KeyError:
raise ValueError("invalid input file")
# read ascii maze, '#' for wall '.' for empty slor
# store as maze = { (x1,y1):'#', (x2,y2):'.', ... }
# NOTE: this is of course not optimal, but leads to a simpler access later
maze = {}
for line_num, line in enumerate(data[:-3]): # ignore last 3 lines
for col_num, value in enumerate(line[:-1]): # ignore \n at end
maze[(line_num, col_num)] = value
return maze, start, end
def maze_to_dag(maze, start, end):
"""
Traverses the map starting from start coordinate.
Returns directed acyclic graph in the form {(x,y):[(x1,y1),(x2,y2)], ...}
"""
dag = {} # directed acyclic graph
queue = [start] # queue of nodes to process
# repeat till queue is empty
while queue:
x,y = queue.pop(0) # get next node in queue
edges = dag[(x,y)] = [] # init list to store edges
# for each neighbour (top, bottom, left, right)
for coord in ((x,y-1), (x,y+1), (x-1,y), (x+1,y)):
if coord in dag.keys(): continue # visited before, ignore
node_value = maze.get(coord, None) # Return None if outside maze
if node_value == ".": # valid path found
edges.append(coord) # add as edge
queue.append(coord) # push into queue
# uncomment this to stop once we've found the end point
#if coord == end: return dag
return dag
if __name__ == "__main__":
maze,start,end = read_maze("l4.txt")
dag = maze_to_dag(maze, start, end)
print dag
于 2011-01-20T15:03:39.023 回答
0
由于您已经有一个列表，请尝试创建一个邻接矩阵而不是字典。
list_of_houses = []
directed_graph = [][]
for i in xrange(len(list_of_houses)):
for i in xrange(len(list_of_houses)):
directed_graph[i][i] = 0
然后对于从一所房子到另一所房子的任何新边缘（或 w/e 连接）
directed_graph[from_house][to_house] = 1
你就完成了。house_a如果从到house_b那里有边directed_graph[house_a][house_b] == 1。
于 2011-01-19T18:29:33.657 回答