0

我最近开始尝试编写一个程序，该程序使用 Zelle 的 python 编程书中的 graphics.py 模块。该程序的想法是创建一个图形窗口并接受两个点，开始和结束。它绘制起点并进行 bfs 搜索，然后一旦到达终点，它就会绘制最短路径（反正还没有对角线）。它在技术上是有效的，但它非常慢，并且在前两到三个迭代之后的任何地方都需要很长时间。而且我尝试到处寻找具有快速查找的数据结构，以及实现节点以允许回溯的有效方法，但我就是想不通。在向我解释我可以做些什么来改进我的实施时，我将不胜感激。

这是python 3.5.2中的代码：

from graphics import *
from collections import deque
TITLE = "Breadth-First Search"
WIDTH = 500
HEIGHT = 500


win = GraphWin(TITLE, WIDTH, HEIGHT)
win.setCoords(0,0,20,20)

class Node:
    def __init__(self, x, y, parent = None):
        self.x = x
        self.y = y
        self.parent = parent
        self.pos2D = Point(self.x, self.y)
        self.pos2D.draw(win)

    def getPos(self):
        return (self.x, self.y)

    def draw(self, win, color = None):
        if color != None:
            self.pos2D.undraw()
            self.pos2D.setFill(color)
            self.pos2D.draw(win)
            return
        self.pos2D.draw(win)


def neighbors(state):
    return (Node(state.x, state.y+1, state), Node(state.x, state.y-1, 
state), Node(state.x-1, state.y, state), Node(state.x+1, state.y, 
state))

def drawPath(endState):
    state.draw(win, 'red')
    while state.parent != None:
        state = state.parent
        state.draw(win, 'red')

def bfs():
    start = (10,10)
    finish = (15,15)

    explored = set()

    frontier = deque()
    frontier.append((Node(start[0], start[1])))

    while len(frontier) != 0:
        state = frontier.popleft()
        explored.add(state)

        if state.getPos() == finish:
            break

        for neighbor in neighbors(state):
            if neighbor not in explored:
                frontier.append(neighbor) 
bfs()
4

1 回答 1

1

运行代码的主要延迟是这种优化：

if neighbor not in explored:
    frontier.append(neighbor)

因为它根本行不通。在此添加一个else:子句以将单词打印skipped到控制台，您将看到else:从未使用过。优化不起作用，因为您放入集合中的东西都是独一无二的。@user2357112 关于 missing 和 methods 的评论__hash__是__eq__解决__ne__这个问题的正确方法（我在下面使用了一个更简单的修复方法。）

第二个延迟是您正在创建（和绘制）许多Node您最终没有使用的实例，因为它们已经被探索过了。

以下是您的代码的返工，试图解决这两个问题：

from collections import deque
from graphics import *

TITLE = "Breadth-First Search"

WIDTH, HEIGHT = 500, 500

class Node:
    def __init__(self, x, y, parent=None):
        self.x = x
        self.y = y
        self.parent = parent
        self.pos2D = Point(self.x, self.y)
        self.pos2D.draw(win)

    def getPos(self):
        return (self.x, self.y)

def unexplored_neighbors(state):
    neighbors = []

    for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
        if (state.x + dx, state.y + dy) not in explored:
            neighbors.append(Node(state.x + dx, state.y + dy, state))

    return neighbors

def bfs():
    start = (10, 10)
    finish = (15, 15)

    frontier = deque()
    frontier.append(Node(*start))

    while frontier:
        state = frontier.popleft()

        if state.getPos() == finish:
            break

        explored.add((state.x, state.y))

        for neighbor in unexplored_neighbors(state):
            frontier.append(neighbor)

win = GraphWin(TITLE, WIDTH, HEIGHT)
win.setCoords(0, 0, 20, 20)

explored = set()

bfs()

win.getMouse()
win.close()

可以帮助您发现性能问题的是该cProfile模块：

# bfs()
import cProfile
cProfile.run('bfs()')

# win.getMouse()
# win.close()

您可以在Python Profilers中阅读

在此处输入图像描述

于 2017-07-15T18:27:46.803 回答