Как сделать ход, который набирает максимальное количество очков?

Question

У нас есть ход, который начинается с любого элемента из первого ряда, получает его энергию, и он должен собрать максимальное количество энергии из этой исходной позиции, пока она не достигнет последнего ряда, он двигается только к (i + 1, j +1) или (i + 1, j-1) или (i + 1, j) и он фиксированное количество энергии при движении.

Я пробовал жадный подход, и иногда он говорит мне «индекс списка вне диапазона» в строках, где я написал инструкции, и я думаю, что есть лучший способ сделать это, но не могу понять это, спасибо заранее

import random

class robot:
    def __init__(self, column, row = 0):
        self.row = row
        self.column = column
        self.power = a[row][column]
        self.consume = random.randint(1,5)

    def left(self):
        self.row = self.row + 1
        self.column = self.column - 1
        self.power = self.power + a[self.row][self.column] - self.consume

    def right(self):
        self.row = self.row + 1
        self.column = self.column + 1
        self.power = self.power + a[self.row][self.column] - self.consume

    def center(self):
        self.row = self.row + 1
        self.power = self.power + a[self.row][self.column] - self.consume

    def decision(self):
        row = self.row
        column = self.column
        if row < 9:
            if column < 9:
                if a[row + 1][column + 1] > a[row + 1][column] and a[row + 1][column  + 1] > a[row + 1][column - 1]:
                    self.right()
            else:
                if a[row + 1][column - 1] > a[row + 1][column]:
                    self.left()
                else: 
                    self.center
            if a[row + 1][column] > a[row + 1][column + 1] and a[row + 1][column] > a[row + 1][column - 1]:
                self.center()
            else:
                if a[row + 1][column  + 1] > a[row + 1][column - 1]:
                    self.right()
                else: 
                    self.left()
            if column > 0:
                if a[row + 1][column - 1] > a[row + 1][column] and a[row + 1][column  - 1] > a[row + 1][column + 1]:
                    self.left()
            else:
                if a[row + 1][column] > a[row + 1][column + 1]:
                    self.center()
                else:
                    self.right()

a = [[random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10)]]
for i in range (0,10):
    a.append([random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10)])
x = 0
y = random.randint(0,9)
p = robot(y)
while (x<9):
    x= x + 1
    p.decision()
print(p.power)

Answer 1

Я использовал pprint для визуализации вашей матричной платы, но вы можете удалить эту часть. Ваша проблема возникла из сложного блока if / else в методе decision(). Где-то там, вы заканчиваете индексированием вне диапазона, когда вы вызываете [row + 1] [column] с плюсом или минусом для колонки. Я исправил эту часть, чтобы найти три значения под роботом, затем переместился влево, если слева - максимум, в центре, если центр - максимум, справа - если максимум. Три значения инициализируются в -1, так что если слева или справа не существует по краям, оно никогда не будет максимальным из трех значений.

import random, pprint

class robot():
    # omitted other methods
    def decision(self):
        row = self.row
        column = self.column
        if row == len(a):
            return
        # initialize local variables to store left, center, and right values at -1
        values = [-1, -1, -1]

        # set left value if it exists
        if column > 0:
            values[0] = a[row+1][column-1]
        # set center value
        values[1] = a[row+1][column]
        # set right value if it exists
        if column < 9:
            values[2] = a[row+1][column+1]

        if values[0] == max(values):
            self.left()
        elif values[1] == max(values):
            self.center()
        elif values[2] == max(values):
            self.right()

a = [[random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10)]]
for i in range (0,10):
    a.append([random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10), random.randint(0,10)])

x = 0
y = random.randint(0,9)
p = robot(y)

pprint.pprint(a)
print('starting:', y)

while(p.row<9):
    p.decision()
print(p.power)

P.S. Я не думаю, что это обязательно означает наивысшую суммарную энергию в конце, так как иногда следование наибольшему значению непосредственно под роботом не приведет к наивысшему пути. Например, на этой доске 4х4, предполагая, что робот начинается с строки = 0 и столбца = 0: R 0 0 0 0 1 0 0 0 0 1 0 9 0 0 1

Робот получит энергию 3 (игнорируя потребление энергии), но было бы лучше, если бы он просто пошел прямо вниз, чтобы добраться до 9. Поэтому я думаю, что вам нужна BFS, чтобы проверить каждое возможное движение ко дну грести и найти максимум этих путей. По сути, проблема обхода дерева.