Почему четные N занимают больше времени, чем нечетные? - PullRequest
Новая
       76

Почему четные N занимают больше времени, чем нечетные?

0 голосов
/ 22 апреля 2019

У меня есть некоторый код, который решает проблему n ферзей, используя возврат в 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)

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

1 Ответ

0 голосов
/ 23 апреля 2019

Алгоритм занимает значительно больше времени, когда в одном из первых столбцов происходит обратное отслеживание, и необходимо попробовать следующую строку. И сравнение плат нечетных 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 n ) , и поэтому, чтобы сравнить времена разных размеров плат, лучше сделать это по логарифмической оси Y:

enter image description here

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

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

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

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

Shift Pick

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

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

for i in range(N):

до: 

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

enter image description here

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

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

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

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

enter image description here

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

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

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

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

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

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

...