优化图类算法
优化图类算法
提问于 2019-03-25 01:19:30
我为我的一个班级布置了以下作业。我当前的解决方案显示在作业文本下方。我正在寻找正确的结果，但我的代码太慢了，无法提供所需的点。
作业
Josefine和她的小妹妹正在玩一个叫做字母迷宫的游戏。在这个游戏中，一个N乘以N的矩阵用A和B填充(见下面的例子)。挑战是找到从左上角到右下角的最短路径。路径必须在A和B之间交替，即。当阅读路径上的字母时，它应该拼写为ABABABA...路径只能向上/右/下/左。在下面的示例中，用小写字母标记了最短路径。
aAaba
bBbBb
abaAa
ABBBb
AAAAa因为他们发现很难确定是否找到了最短路径，所以他们需要您为他们编写一个程序来验证这一点。
输入格式
Line 1: The integer N
Line 2..N+1: The N times N matrix of letters (A or B) corresponding to the labyrinth.输出格式
Line 1: The number of letters on the shortest path from the top left corner to the lower right corner.我的代码
首先，我创建了一个Graph类。在这里，我将主要使用类的shortPath函数。
class Graph:
# Laver en graph, hvis intet input så laves en tom graph.
# Input et dict med hver verticy samt dens edges.
def __init__(self, gd=None):
if gd is None:
gd = {}
self.gd = gd
def genEdges(self):
edges = []
# Her er v vertecies og n er neighbours til hver edge.
for v in self.gd:
for n in self.gd[v]:
if {n,v} not in edges:
edges.append({v,n})
return edges
def addVert(self,v):
# Tilføjer vertex med tom liste af edges.
if v not in self.gd:
self.gd[v] = []
def addEdge(self, edges):
# Her skal edges være en liste med 2 verticies som skal forbindes.
self.gd[edges[0]].append(edges[1])
self.gd[edges[1]].append(edges[0])
def pVert(self):
return list(self.gd.keys())
def pEdges(self):
return self.genEdges()
def BFS(self, v):
# Laver dict til at tjekke om en verticy er besøgt
b = {}
for i in self.gd:
b[i] == False
b[v] = True
# Laver en que
q = []
q.append[v]
paths = {}
while q:
v = q.pop(0)
print(v)
for i in self.gd[v]:
if b[i] == False:
q.append(i)
b[i] = True
def shortPath(self, start, slut, path = list()):
# Laver en list som vejen til slut.
path = path + [start]
# Tjekker om start og slut er den samme
if start == slut:
return path
# Tjekker om start er i grafen
if start not in self.gd:
return None
# Laver en variabel til at gemme shortest path
sPath = []
for v in self.gd[start]:
if v not in path:
nPath = self.shortPath(v, slut, path)
if len(nPath) > 0:
if len(sPath) == 0 or len(nPath) < len(sPath):
sPath = nPath
return sPath之后，我将在以下代码中创建和使用图形类。
g = Graph()
N = int(input())
countA = 1
countB = 1
for i in range(0,N):
Line = list(input())
for j in range(0,len(Line)):
if Line[j] == "A":
Line[j] = "A" + str(countA)
countA += 1
elif Line[j] == "B":
Line[j] = "B" + str(countB)
countB += 1
# Tilføjer Vertecies
g.addVert(Line[j])
if Line[j][0] == "A":
if j > 0 and Line[j-1][0] == "B":
# Tilføjer Edges til venstre
g.addEdge([Line[j],Line[j-1]])
if Line[j][0] == "A":
if i > 0 and Line2[j][0] == "B":
g.addEdge([Line[j],Line2[j]])
if Line[j][0] == "B":
if j > 0 and Line[j-1][0] == "A":
# Tilføjer Edges til venstre
g.addEdge([Line[j],Line[j-1]])
if i > 0 and Line2[j][0] == "A":
g.addEdge([Line[j],Line2[j]])
# Tilføjer edges opad
if i == 0:
Start = Line[0]
if i == N-1:
End = Line[-1]
Line2 = Line
sp = g.shortPath(Start,End)
print(len(sp))如上所述，我的问题是代码太慢了。如果有人知道优化它的方法，我将不胜感激。
提前谢谢。
回答 1
Stack Overflow用户
发布于 2019-03-25 02:07:14
在我看来，你的代码要复杂得多，用DFS解决这个问题是一个很好的方法，但我认为你的实现中有不必要的循环。伪代码：
import Queue
# storeing edges
Class Edge(i,j):
isVisited
distance = -1
i
j
char
# main function to call
DFS(input):
maxIndex = getN()
q = Queue.Queue()
edgeMatrix = initNtimesNMartixWithNulls()
end = False
q.put(edgeMartix[0][0];
for i in range(0,N):
for(j in range(0,N):
char = someFunc(input,i,j)
edgeMartix[i][j] = Edge(i,j)
while not q.empty() and not end:
e = q.get()
end = addElement(q, e.i +1, e.j, q.char, q.distance) or end
end = addElement(q, e.i -1, e.j, q.char, q.distance) or end
end = addElement(q, e.i, e.j +1, q.char,q.distance) or end
end = addElement(q, e.i, e.i -1, q.char, q.distance) or end
return edgeMartix[N-1][N-1]
addElement(edgeMartix, q,i,j,maxIndex, char, dist):
if(i < 0 or i > maxIndex or j < 0 or i > maxIndex):
return False
e = edgeMartix[i][j]
if (not e.isVisited and e.char != char):
e.isVisited = True
e.distance = distance + 1
q.put(e)
if (i == max and j == max ) :
return True
return False页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55326427
复制相关文章
相似问题
腾讯云开发者
