广度优先搜索算法太慢

Question

我试图编程一个人工智能。我用广度优先搜索为路径查找编写了这个脚本，但它似乎很慢。我不知道如何使它更快。请帮帮我。顺便说一下，如果你需要的话，我用了这个教程https://www.youtube.com/watch?v=hettiSrJjM4

import queue


class AIRoadMap(object):
    def __init__(self, game):
        self.game = game
        self.road_list = []
        self.initialize_road_list()

    def initialize_road_list(self):
        # This method adds all empty coordinates to list (self.road_list)
        for y_row in self.game.map:
            y_coord = self.game.map.index(y_row)
            for x in y_row:
                if x['symbol'] == '.':
                    x_coord = y_row.index(x)
                    self.road_list.append({'x' : x_coord, 'y' : y_coord})

    def check_valid_moves(self, x_from, y_from, moves):
        unreal_x = x_from
        unreal_y = y_from
        valid = False
        for move in moves:
            if move == "L":
                unreal_x -= 1

            elif move == "R":
                unreal_x += 1

            elif move == "U":
                unreal_y -= 1

            elif move == "D":
                unreal_y += 1
            valid = False
            for item in self.road_list:
                if item['x'] == unreal_x and item['y'] == unreal_y:
                    valid = True
            if valid is False:
                break
        return valid

    def IsPathEnd(self, x_from, y_from, to_x, to_y, moves):
        unreal_x = x_from
        unreal_y = y_from
        for move in moves:
            if move == "L":
                unreal_x -= 1

            elif move == "R":
                unreal_x += 1

            elif move == "U":
                unreal_y -= 1

            elif move == "D":
                unreal_y += 1

        if unreal_y == to_y and unreal_x == to_x:
            return True
        if unreal_x != to_x or unreal_y != to_y:
            return False
        if unreal_x != to_x and unreal_y != to_y:
            return False

    def generate_road(self, from_x, to_x, from_y, to_y):
        nums = queue.Queue()
        nums.put("")
        add = ""

        while not self.IsPathEnd(from_x, from_y, to_x, to_y, add):
            add = nums.get()
            # print(add)
            for j in ["L", "R", "U", "D"]:
                put = add + j
                if self.check_valid_moves(from_x, from_y, put):
                    if len(put) < 3:
                        nums.put(put)
                    else:
                        if put[-1] == "L" and put[-2] != "R" or put[-1] == "R" and put[-2] != "L" or put[-1] == "U" and \
                                put[-2] != "D" or put[-1] == "D" and put[-2] != "U":
                            nums.put(put)
                    #nums.put(put)

        return add

方法initialize_road_list()将self.game.map（基本上是一个网格）中的所有空坐标添加到self.road_list

Answer 1

您的代码似乎有很多可能的改进，我现在只建议一些：

1）替换：

        valid = False
        for item in self.road_list:
            if item['x'] == unreal_x and item['y'] == unreal_y:
                valid = True
        if valid is False:
            break
    return valid

与

       if not any(item['x'] == unreal_x and item['y'] == unreal_y for item in self.road_list):
           return False
   return True

2）更换：

    if unreal_y == to_y and unreal_x == to_x:
        return True
    if unreal_x != to_x or unreal_y != to_y:
        return False
    if unreal_x != to_x and unreal_y != to_y:
        return False

与：

    return unreal_y == to_y and unreal_x == to_x

3）替换：

if put[-1] == "L" and put[-2] != "R" or put[-1] == "R" and put[-2] != "L" or put[-1] == "U" and \
                                put[-2] != "D" or put[-1] == "D" and put[-2] != "U":

与：

if put[-2:] in frozenset(('LR', 'RL', 'UD', 'DU')):