Жадные алгоритмы и временная сложность № 2

Question

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

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

Мы имеем, скажем, n = 4 переключателя в настоящее время в положении ^ vvv. Нам нужно вернуть их на позицию ^ v ^^. Запрещенные позиции: vvv ^, ^ vv ^, ^ v ^ v и ^^^ v.

а.) Мне пришлось нарисовать это вручную и найти кратчайшую последовательность движений переключателя, которая решает задачу - результат, который я получил, был 4 ... и я нашел две такие последовательности, если я прав ...

б.) Вот тут-то и получается - напишите код, который отвечает на поставленные выше вопросы / вопросы (кратчайшая последовательность и сколько). Код должен быть обобщен, чтобы он работал с другим числом переключателей и другими начальными, целевыми и запрещенными комбинациями; целевые и запрещенные комбинации могут быть несколько или даже меньше. Единственное, что мы точно знаем, это то, что переключатели имеют только два положения. Это также должно обеспечить возможность того, что желаемое условие недоступно; в этом случае программа должна, конечно, сказать.

c.) Следующие вопросы - это временная сложность кода, но сейчас я думаю, что я просто остановлюсь здесь ...

Вместо этого я использовал «0» и «1», потому что мне легче представить это.

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

Ключевая часть кода, которую мне еще предстоит написать, и в этой части мне нужна помощь.

all_combinations = ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011' , '1100', '1101', '1110', '1111']


def distance (position1, position2):
     distance = 0
     for i in range (len (position1)):
         if position1 [i]! = position2 [i]:
             distance + = 1
     return distance


def allowed_positions (current, all_combinations):
     allowed = set ()
     for combination and all combinations:
         if the distance (current, combination) == 1:
             allowed.add (combination)
     return allowed


def best_name (current, all_combinations, target):
     list = []
     for option and permitted_mood (current, all_combinations):
         list.append (distance (option, target), option)

Answer 1

Задача под рукой - найти кратчайший путь на графике.Для этого существует один типичный подход, а именно алгоритм поиска в ширину (https://en.wikipedia.org/wiki/Breadth-first_search).

) Нет реальной необходимости вдаваться в подробности того, как это делается, потому что его можно прочитать в другом месте более подробно.и гораздо лучше объяснено, чем я могу сделать это в ответе StackOverflow.

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

Представьте себеу вас есть только два переключателя. Тогда у вас есть именно этот график:

^^---^v
|     |
|     |
v^---vv

Если ваша начальная позиция ^^ и ваша конечная (разрядная) позиция vv, тогда как позиция ^v взрывающаясяположение, то ваш график будет приведен к следующему:

^^   ^v
|       
|       
v^---vv

В этом небольшом примере кратчайший путь очевиден и прост.

На графике легко нарисовать в 2D, каждое измерение(x и y), представляющий один из переключателей. Если у вас есть больше переключателей, то вы просто добавляете одно измерение для каждого переключателя. Для трех переключателей это будет выглядетьэто:

^^^--------^^v
 |\         |\
 | \        | \
 |  \       |  \
 |   \      |   \
 |   ^v^--- | --^vv
 |    |     |    |
 |    |     |    |
v^^--------v^v   |
  \   |      \   |
   \  |       \  |
    \ |        \ |
     \|         \|
     vv^--------vvv

Если позиции ^^v, v^^ и vv^ запрещены, то этот график сводится к этому:

^^^        ^^v
  \           
   \           
    \           
     \           
     ^v^--------^vv
                 |
                 |
v^^        v^v   |
             \   |
              \  |
               \ |
                \|
     vv^        vvv

, который уже показываетясный путь и поиск в ширину легко найдетЭто становится интересным только для многих измерений / переключателей.

Рисование этого для большего количества измерений / переключателей, конечно, сбивает с толку (посмотрите тессеракты по 4D).Но не обязательно иметь визуальный образ.После того, как вы написали алгоритм для создания графика в 2D и 3D в общем виде, он легко масштабируется до n измерений / переключателей без добавления какой-либо сложности.

Answer 2

start = 8
target = 11
forbidden = {1: -1 , 9: -1, 10: -1, 14: -1}
dimensions = 4

def distance(start, target, forbidden, dimensions):
stack1 = []

stack1.append(start)
forbidden[start] = -1

while(len(stack1) > 0):
    top = stack1.pop()
    for i in range(dimensions):
        testVal = top ^ (1 << i)

        if testVal is target:
            forbidden[testVal] = top
            result = [testVal]
            while testVal is not start:
                testVal = forbidden[testVal]
                result.insert(0, testVal)
            return result


        if testVal not in forbidden:
            forbidden[testVal] = top
            stack1.append(testVal)

return [-1]


print(distance(start, target, forbidden, dimensions))

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

Это решение использует поиск в ширину и возвращает первый раз, когда цель найдена.Это означает, что он не гарантирует кратчайший путь от начала до цели, но он гарантирует рабочий путь, если он доступен.Поскольку все возможные коды, возможно, пройдены, и число узлов равно 2 ^ измерениям, временная сложность этого алгоритма также составляет O (2 ^ n)