Алгоритм поиска в ширину Python слишком медленно - PullRequest
Новая
       47

Алгоритм поиска в ширину Python слишком медленно

0 голосов
/ 24 февраля 2020

Я пытался запрограммировать ИИ. Я сделал этот скрипт для поиска пути с помощью поиска в ширину, но он кажется медленным. Я не знаю, как сделать это быстрее. Пожалуйста, помогите мне. Кстати, если вам нужно, я использовал этот учебник 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.road_list из self.game.map, который в основном сетка

1 Ответ

0 голосов
/ 24 февраля 2020

Кажется, есть много возможных улучшений вашего кода, сейчас я предложу лишь несколько:

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')):
...