Как я могу улучшить мой алгоритм в Python?


Я пытаюсь реализовать свой собственный в* навигаторе, но голоса в моей голове кричат лучшего способа сделать это. Наверное, потому что я превысил допустимый по умолчанию в Python рекурсии глубина 1000.

class PathFinder():

    ## grid is a list of 8 sub-lists, each containing 8 nodes.
    ## start and goal are tuples representing the grid indexes of my start and goal.

    def __init__(self, start, goal, grid):
        ## I don't do anything with these yet, 
        ## just thought they would be good to have.
        self.goal = goal
        self.start = start
        self.grid = grid

    def find_path(self, start, goal, path=[]):

        ## My seemingly hackish method of looping through 
        ## the 8 cells surrounding the one I'm on.
        for row in (-1,0,1):
            for col in (-1,0,1):
                if row == 0 and col == 0:
                    continue
                cell = [start[0]+row,start[1]+col]


                ## Catching the inevitable exception when I try to examine
                ## the surroundings of cells that are already on the edge.
                try:
                   ## Skip if the cell is blocked ("X").
                    if self.grid[cell[0]][cell[1]] == "X":
                        continue
                except IndexError:
                    continue


                path.append(cell)
                if cell == goal:
                    return path
                self.find_path(cell, goal, path)

def main():
    import Gridder2
    grid = Gridder2.board()
    start = (0,0)
    goal = (0,3)
    pt = PathFinder(start, goal, grid)
    print(pt.find_path(start, goal))

    return 0

if __name__ == '__main__':
    main()

Мой find_path функция особенно кажется, что он должен работать. Похоже, я должен быть в состоянии вычислить путь через 8х8 с глубины рекурсии менее 1000.

Как я могу улучшить это?



820
4
задан 7 октября 2011 в 03:10 Источник Поделиться
Комментарии
2 ответа

class PathFinder():

Но объект в () или удалить их. Их там пустые заставляет меня чувствовать себя полый внутри.

    ## grid is a list of 8 sub-lists, each containing 8 nodes.
## start and goal are tuples representing the grid indexes of my start and goal.

def __init__(self, start, goal, grid):
## I don't do anything with these yet,
## just thought they would be good to have.
self.goal = goal
self.start = start
self.grid = grid

def find_path(self, start, goal, path=[]):

Не ставьте изменяемые значения списка в качестве параметров по умолчанию. Python не будет создать новый список каждый раз, когда вызывается эта функция, а он будет продолжать повторно использовать тот же список, который, вероятно, не то, что вы хотите

        ## My seemingly hackish method of looping through 
## the 8 cells surrounding the one I'm on.
for row in (-1,0,1):
for col in (-1,0,1):
if row == 0 and col == 0:
continue

Я предлагаю создать глобальную константу с в 8 направлениях и делает: для Row, col в направлениях:

                cell = [start[0]+row,start[1]+col]

Не используйте списки, если они фактически перечислены. Это должен быть кортеж.

                ## Catching the inevitable exception when I try to examine
## the surroundings of cells that are already on the edge.
try:
## Skip if the cell is blocked ("X").
if self.grid[cell[0]][cell[1]] == "X":
continue
except IndexError:
continue

Я предлагаю функцию get_blocked , что вы проходите клетки, которые проверяют на 'X' и также возвращает true, если ячейка находится на краю карты. Также ловить IndexError может не совсем то, что вы хотите, потому что отрицательные числа допустимых индексов, но, наверное, не хочешь. Я предлагаю проверить в функции get_blocked для inboundedness.

                path.append(cell)
if cell == goal:
return path
self.find_path(cell, goal, path)

def main():
import Gridder2

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

    grid = Gridder2.board()
start = (0,0)
goal = (0,3)
pt = PathFinder(start, goal, grid)

пт?

    print(pt.find_path(start, goal))

Решить вопрос о начале/цели вам передать в конструктор или метод найти. Не делай так.

    return 0

if __name__ == '__main__':
main()

Если вы собираетесь возвращать значение из main функции, вы должны передать его в sys.выход() так, что он на самом деле работает в качестве кода возврата.

И все, что сказал Томас.

5
ответ дан 7 октября 2011 в 04:10 Источник Поделиться

Примечание: это справедливое расстояние от бытия* алгоритм - возможно, правильно осуществляет рекурсивным поиском в глубину (то, что ваш алгоритм является в настоящее время слишком близким) было бы хорошим началом.

Вы правы, вы должны быть в состоянии вычислить путь через 8х8, не превышая ограничение рекурсии. Попробуйте трассировать код, как вы ожидаете его, чтобы выполнить, или добавить распечатать заявление, чтобы показать, что клетка проверяется каждый раз. (и raw_input() или что-то, так что вы можете легко читать - я бы предложил отладчик, но это костыль вы можете сделать без на этом уровне)

(спойлер) из-за отрицательных показателей не поднимая IndexError в Python (редактировал этот ответ после того, как Уинстон указал на это), путь вы пытаетесь не один ты думаешь. И путь, который превышает ограничение рекурсии является, вероятно, одним, что неоднократно пытается остаться в нынешней незалежной, проверяя снова и снова, что произойдет, если следующий посещаемый узел является текущим площади.

Если только там был способ, чтобы закрыть некоторые из этих путей выполнения; знать, что определенный путь-не стоит проверять дальше, так другая ветвь исполнения, которое, вероятно, имеет лучшее решение должно быть, а не попробовал. Хорошее начало, что, стоя на том же месте-это не очень полезно для статического лабиринт, так вот вы как раз были в разгаре проверки решений! Но есть и другие случаи, в которых вы собираетесь проверяют угольником, вы должны уже выяснили, не стоит разобраться. Проверить любую литературу на глубину поиска решения.

5
ответ дан 7 октября 2011 в 03:10 Источник Поделиться