Подсчет коллизий в задаче n-Queens в Python - PullRequest
Новая
       45

Подсчет коллизий в задаче n-Queens в Python

0 голосов
/ 30 сентября 2018

Я начал работать над python для Ai, и у меня возникли некоторые проблемы:

У меня проблема с n-Queens Вот подробное объяснение проблемы

Фитнес-функция получает массив в виде: 

decoded =  [3, 1, 2, 5 ... n]

, где элемент соответствует координате X, а индекс соответствует координате Y, т.е. берет координаты из приведенного выше примера: 

# [X, Y]
pairCoords = [[3,0], [1, 1], [2, 2], [5, 1], ... [n, z]]

, поэтому у меня есть функция пригодности, которая получает массив, аналогичный первому примеру. Запись var начинается с максимального числа столкновений n * (n-1) и уменьшается с каждым обнаруженным столкновением 

    def fitness(self, decodedGenes):
    record = self.numeroN * (self.numeroN-1)

    for y in range(len(decodedGenes)):
        if self.positionIsAtacking(decodedGenes, decodedGenes[y], y):
            record = record - 1
    return record

поэтому в лучшем случае мир возвращает n * (n-1) , а в худшем случае возвращает 0

вспомогательная функция, которую она вызывает, проверяет заданные X и Yкоординирует и возвращает, если есть столкновение, но оно не работает 

    def positionIsAtacking(self, coords, X, Y):
    for i in range(len(coords)):
        # Check Y
        if (coords[i] == Y):
            return True
        # Check Diagonals
        if (coords[i] - Y == i - X):
            return True
        if (coords[i] - Y == X - i):
            return True
    return False

Я пытался изменить параметры, но я не знаю, где искать, я думаю, что вторая функция не работает или, возможно, учаnged x и y

1 Ответ

0 голосов
/ 01 октября 2018 
def fitness(self, cromosoma):
    record = self.numeroN * (self.numeroN - 1)

    for row in range(len(board)):
        decodedGenes.append(self.decodeGene(board[row]))

    for y in range(len(decodedGenes)):
        x = decodedGenes[y]
        record = record - self.collisions(decodedGenes, x, y)
    return record
def collisions(self, coords, X, Y):
    board = []
    r = 0
    for i in range(len(coords)):
        board.append([0] * self.numeroN)
    for y in range(len(coords)):
        board[y][coords[y]] = 1

    for y in range(len(board)):
        for x in range(len(board)):
            # if has Queen and is not the same
            if board[y][x] == 1 and y != Y:
                # check x
                if x == X:
                    r = r + 1
                # check Diagonals
                if self.crash_diagonal(x, y, X, Y):
                    r = r + 1
    return r

def crash_diagonal(self, x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    return dx == dy
...