Как разблокировать все сундуки в сокровищнице?

Ответ 1

Удивительно, но эта проблема разрешима с помощью жадного алгоритма. Я также внедрил его в виде замеченного поиска в глубину. Только после этого я заметил, что поиск никогда не возвращался, и в кэш memoization не было хитов. Только две проверки состояния проблемы и частичного решения необходимы для того, чтобы узнать, следует ли продолжать дальнейшую дальнейшую работу. Они легко иллюстрируются парой примеров.

Сначала рассмотрим этот тестовый пример:

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  2                       |  1
2             |  1                       |  1 1
3             |  1                       |  1
4             |  2                       |  1
5             |  2                       |  2

Initial keys: 1 1 2 

Здесь есть всего лишь два ключа типа 2: один в сундуке № 5 и один из вас в вашем распоряжении. Однако для трех сундуков требуется открыть ключ типа 2. Нам нужно больше ключей этого типа, чем существует, поэтому ясно, что невозможно открыть все сундуки. Мы сразу знаем, что проблема невозможна. Я вызываю этот ключ, подсчитывая "глобальное ограничение". Нам нужно только один раз проверить его. Я вижу, что эта проверка уже включена в вашу программу.

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

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             | 1                        | 1
2             | 6                        |
3             | 3                        |
4             | 1                        |
5             | 7                        | 7 
6             | 5                        | 
7             | 2                        |
8             | 10                       | 10
9             | 8                        | 
10            | 3                        | 3
11            | 9                        | 
12            | 7                        |
13            | 4                        | 4
14            | 6                        | 6
15            | 9                        | 9
16            | 5                        | 5
17            | 10                       |
18            | 2                        | 2
19            | 4                        |
20            | 8                        | 8

Initial keys: 1 2 3 4 5 6 7 8 9 10 

После краткого осмотра структура этого теста очевидна. У нас есть 20 сундуков и 10 ключей. Каждый из десяти типов ключей откроет ровно два сундука. Из двух сундуков, которые можно открыть с заданным типом ключа, один содержит другой ключ того же типа, а другой не содержит никаких ключей. Решение очевидно: для каждого типа ключа мы должны сначала открыть сундук, который даст нам еще один ключ, чтобы открыть второй сундук, который также требует ключа этого типа.

Решение очевидно для человека, но программа долгое время решала его, поскольку у него еще не было возможности определить, есть ли какие-либо ключевые типы, которые больше не могут быть приобретены. "Глобальное ограничение" касалось количества каждого типа ключа, но не того порядка, в котором они должны были быть получены. Это второе ограничение касается вместо этого порядка, в котором ключи могут быть получены, но не их количества. Вопрос просто: для каждого типа ключа, который мне понадобится, есть ли способ, которым я все еще могу его получить?

Здесь код, который я написал, чтобы проверить это второе ограничение:

# Verify that all needed key types may still be reachable
def still_possible(chests, keys, key_req, keys_inside):
    keys = set(keys)         # set of keys currently in my possession
    chests = chests.copy()   # set of not-yet-opened chests

    # key_req is a dictionary mapping chests to the required key type
    # keys_inside is a dict of Counters giving the keys inside each chest

    def openable(chest):
        return key_req[chest] in keys

    # As long as there are chests that can be opened, keep opening
    # those chests and take the keys.  Here the key is not consumed
    # when a chest is opened.
    openable_chests = filter(openable, chests)
    while openable_chests:
        for chest in openable_chests:
            keys |= set(keys_inside[chest])
            chests.remove(chest)
        openable_chests = filter(openable, chests)

    # If any chests remain unopened, then they are unreachable no 
    # matter what order chests are opened, and thus we've gotten into
    # a situation where no solution exists.
    return not chests   # true iff chests is empty

Если эта проверка не удалась, мы можем немедленно прекратить ветвь поиска. После выполнения этой проверки моя программа работала очень быстро, требуя примерно 10 секунд вместо 1 минуты. Более того, я заметил, что количество обращений в кеш упало до нуля, и, кроме того, поиск никогда не возвращался. Я удалил memoization и преобразовал программу из рекурсивной в итеративную форму. Тогда решение Python могло решить "большой" тестовый ввод примерно через 1,5 секунды. Почти идентичное решение C++, составленное с оптимизацией, решает большой вход за 0,25 секунды.

Доказательство правильности этого итеративного, жадного алгоритма приведено в официальном анализе проблемы Google.

Ответ 2

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

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

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

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

Существует алгоритм вырезания. Вычислить все достижимые вершины из набора вершин, у вас есть ключ в вашей должности. Если есть недостижимые вершины, для которых есть еще закрытый сундук, то вы разрезаете ветку. (Это означает, что вы назад)

Этого было достаточно, чтобы решить большой набор. Но мне пришлось добавить первое условие, которое вы написали:

if any(required > keys_across_universe):
    return False

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

Это условие сокращения не является дешевым. Это может стоить O (N²). Но он сократил так много веток, что это определенно стоит того... при условии, что наборы данных хороши. (Справедливая?)

Ответ 3

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

1. Как сказал Валентин, я подсчитал доступные ключи, чтобы быстро отказаться от сложных случаев

2. Пытался игнорировать сундуки без ключей внутри при первом попадании, переходя к следующему

3. Пропустить решения, начиная с более высоких сундуков

4. Проверьте наличие "клавишных петель", если доступных клавиш недостаточно, чтобы открыть сундук (сундук содержит ключ для себя внутри)

Производительность была хорошей (<2 с для 25 небольших случаев), я вручную проверил случаи и работал правильно, но все равно получил неправильный ответ: P