Здесь у меня есть некоторый код, который решает проблему n queens с использованием обратного отслеживания в python. Когда я запускаю его, шансы всегда занимают намного меньше времени, чем четные. Это особенно очевидно, когда n достигает более 20. Кто-нибудь знает, почему это?

 import time
global N
N = int(input("Enter N: "))


def display_solution(board):
    print('n'.join(['t'.join([str(cell) for cell in row]) for row in 
    board]))


def safe(board, row, col):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True


def solve_help(board, col):
    if col >= N:
        return True

    for i in range(N):
        if safe(board, i, col):
            board[i][col] = 1
            if solve_help(board, col   1) is True:
                return True
            board[i][col] = 0
    return False


def solve():
    board = [[0 for x in range(N)] for y in range(N)]
    if solve_help(board, 0) is False:
        print("Solution does not exist")
        return False
    display_solution(board)
    return True


start = time.clock()
solve()
end = time.clock()
print(N, "t", end-start)
  

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

Алгоритм занимает значительно больше времени, когда в одном из первых столбцов происходит откат и необходимо попробовать следующую строку. И сравнение нечетных N плат с N-1 платами действительно показывает, что часто решение для четной платы требует больше такой обработки возврата / повторной попытки. Например, верхний левый угол решения для N = 19 выглядит следующим образом:

 1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1*
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
  

Эти 5 ферзей в первых пяти столбцах находятся быстро, так как они первые, которые не сталкиваются с предыдущими ферзями. И, по-видимому, другие ферзи могут быть размещены без необходимости пересматривать эти первые пять ферзей.

Для N = 18 тот же угол решения выглядит следующим образом:

 1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0-
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1*
  

Обратите внимание на позицию, отмеченную минусом. Этот вариант выглядит многообещающим (как и для 19-й доски): его исследование занимает значительное время, прежде чем делается вывод о том, что другие ферзи не могут быть размещены правильно. Этот ранний сбой стоит.

Таким образом, решение для платы 19 найдено раньше, чем для платы 18.

Обратите внимание, что решение для 27 занимает немного больше времени, чем для 26, хотя это несущественно: похоже, что временная сложность составляет O (2ⁿ), и поэтому для сравнения времени разных размеров платы это лучше было бы сделать по логарифмической оси Y:

«работа» представляет собой количество раз, когда выполняется функция safe .

Неясно, всегда ли этот алгоритм занимает относительно больше времени для четных досок (по сравнению со временем, необходимым для доски N 1), но для этих нескольких размеров доски это, по-видимому, связано с прыжками коня, которые естественным образом формируются этим алгоритмом, начиная с верхнего левого угла. Обратите внимание, как этот шаблон идеально подходит для размеров доски 5 и 7: первое место, где следующий ферзь может сидеть, не мешая предыдущим расположенным ферзям, всегда является частью решения. В то время как для досок размером 4 и 6 даже не существует какого-либо решения с ферзем в углу, которое является отправной точкой этого алгоритма.

Альтернативы

Чтобы ответить на этот вопрос с точки зрения программиста, есть одно средство, с помощью которого разница (в среднем) исчезнет: выберите столбцы в другом (или даже случайном) порядке. Оказывается, что использование обычного порядка является одним из менее эффективных способов получения решения.

Выбор сдвига

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

В solve_help измените это:

 for i in range(N):
  

Для:

 for i in range(N):
   i = (i   2) % N
  

Посмотрите, как теперь улучшилась средняя производительность: все показатели log (work) / n ниже 1, за исключением n = 6. Но также: теперь просмотры чаще выполняются для нечетных значений N.

Случайный выбор

 for i in random.sample(range(N), N):
  

Вот как получился один такой случайный запуск:

Гораздо лучшая статистика, чем исходный порядок! Конечно, время от времени вы будете получать плохие показатели … потому что это случайно. Но в среднем он работает (намного) лучше.

Другие способы неслучайного порядка могут включать col , и N//2 с разными коэффициентами, например i = (i col*2 N//2) % N , … и т.д. Но смотрите заключительное замечание ниже.

Другие замечания

Я бы применил следующую оптимизацию: следите за тем, какие строки, прямые «диагонали» и обратные «диагонали» уже заняты. Для этого вы можете использовать list (ы) или set (ы). Обратите внимание, что две ячейки находятся на одной прямой диагонали, если сумма их координат равна. Ячейки на обратных диагоналях имеют то общее, что разница их координат равна. Таким образом, вам не нужно каждый раз сканировать «1» в этих строках.

Кроме того, board может быть просто список номеров столбцов. Нет необходимости хранить все эти нули. Сохраните это только для отображения.

Наконец, есть простые способы получить решение за линейное время. Смотрите Википедию.