Получение количества уникальных состояний в графе

Question

Я пытался решить задачи MIT по математике для информатики, и вот одна из проблем:

Каждому монаху, входящему в Храм Навсегда, дают миску с 15 красными бусинами и 12 зеленые бусы. Каждый раз, когда звонит Гонг Времени, монах должен сделать одну из двух вещей:

1. Обмен: Если у него в чаше 3 красных шарика, он может обменять 3 красных шарика на 2 зеленых шарика.
2. Обмен: Он может заменить каждую зеленую бусину в своей миске красной бусинкой и заменить каждую красную бусину в своей миске зеленой бусинкой. То есть, если он начинает с красных бусинок и зеленых бусин, то после выполнения этой операции у него будут красные бусинки и зеленые бусины.

Монах может покинуть Храм Навсегда только когда в его чаше ровно 5 красных бусин и 5 зеленых бусин.

В этом есть дополнительные проблемы:

1. Докажите, что никто не покидает храм , Это я доказал, используя математическую индукцию.
2. Докажите, что с помощью этой задачи можно достичь только конечного числа состояний. Это доказательство также было сделано с использованием математической индукции и доказательством того, что сумма количества красных и зеленых шариков может только уменьшаться или оставаться неизменной.
3. (Это то место, где я застрял) Каково истинное максимальное количество уникальных состояний, которые монах может посетить при любом выполнении машины Храма Навсегда?

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

class Node:
    def __init__(self, r, g):
        self.r = r
        self.g = g

    def swap(self):
        if self.g <= 0 or self.r <= 0:
            return None
        return Node(self.g, self.r)

    def exchange(self):
        if self.r >= 3:
            return Node(self.r - 3, self.g + 2)
        return None

    def __hash__(self):
        return hash((self.r, self.g))

    def __eq__(self, other):
        if self is None and other is None:
            return True
        if self is None or other is None:
            return False
        return self.r == other.r and self.g == other.g

    def __repr__(self):
        return "({}, {})".format(self.r, self.g)

start = Node(15, 12)
queue = []
graph = []
visited = set()
queue.append(start)

while (queue):
    curr = queue.pop(0)
    visited.add(curr)
    graph.append(curr)
    s = curr.swap()
    e = curr.exchange()

    for el in [s, e]:
        if el != None:
            if el not in visited:
                queue.append(el)

print(visited, len(visited))

Ответ, который я получил из своей программы:

{(6, 9), (16, 9), (0, 7), (2, 5), (8, 5), (5, 8), (10, 8), ( 10, 7), (16, 3), (5, 18), (0, 17), (14, 1), (8, 15), (10, 13), (4, 16), (9, 16), (7, 5), (14, 2), (13, 10), (3, 1), (6, 13), (20, 3), (3, 11), (4, 12) , (10, 3), (6, 14), (7, 15), (18, 5), (3, 6), (8, 6), (4, 1), (9, 7), ( 6, 4), (11, 4), (16, 4), (5, 17), (11, 9), (0, 18), (14, 6), (13, 6), (19, 2), (18, 6), (1, 19), (15, 7), (0, 8), (4, 11), (3, 5), (4, 6), (9, 2) , (5, 7), (4, 17), (11, 3), (7, 4), (14, 12), (12, 4), (19, 1), (3, 15), ( 1, 3), (5, 13), (3, 21), (11, 14), (12, 9), (18, 1), (15, 12), (2, 19), (3, 10), (1, 14), (8, 10), (9, 11), (3, 16), (8, 16), (11, 13), (0, 22), (17, 5), (6, 18), (7 , 14), (12, 14), (19, 6), (15, 3), (2, 20), (1, 4), (0, 12), (1, 9), (4, 2 ), (2, 14), (9, 6), (5, 3), (6, 8), (11, 8), (16, 8), (14, 7), (13, 5), (1, 18), (2, 4), (9, 12), (4, 7), (9, 1), (12, 5), (15, 8), (0, 3), (2 , 9), (8, 1), (5, 12), (3, 20), (10, 12), (6, 3), (9, 17), (7, 10), (12, 10 ), (13, 11), (1, 13), (8, 11), (2, 10), (0, 23), (17, 4), (6, 19), (14, 11), (12, 15), (7, 9), (13, 1), (17, 9), (15, 2), (20, 2), (0, 13), (21, 3), (1 , 8), (2, 15), (5, 2), (10, 2)} 129

Итак, 129. Но когда я смотрю на решение поставленной задачи (для саб -проблема № 3), вот что она заявляет

Каждый ход в последовательности должен быть либо обменом, либо обменом, поскольку это единственные допустимые ходы. Теперь, когда монах выполняет операцию обмена, сумма r + g уменьшается на единицу.

(r - 3) + (g + 2) = (r + g) - 1

Напротив, свопы не влияют на сумму. Кроме того, мы знаем, что сумма r + g должна быть не менее 3 для выполнения операции обмена. Следовательно, в последовательности может быть не более 25 операций обмена.

Теперь рассмотрим операции обмена: между каждой парой обменов в последовательности может быть неограниченное количество обменов. Однако только один своп может перевести монаха в новое состояние: если на этапе k монах находится в состоянии (r, g), то на этапе k + 2 он вернется в то же состояние. Следовательно, верхняя граница числа уникальных состояний при любом выполнении машины составляет 25 + 26 + 1 = 52 (если в начале и конце последовательности вставляются перестановки).

Где моя программа go не так? Правильно ли я понимаю формулировку проблемы (в написанной мной программе)? Кроме того, я не очень понимаю решение, которое они дали. Есть ли лучший способ объяснить это? Например, одна из проблем / вещей, которые я не понимаю, заключается в том, что решение гласит, что сумма шариков уменьшается на 1 при каждой операции обмена. И, следовательно, мы можем получить 25 новых государств с обменными операциями. Но каждая сумма на каждом уровне графика может быть выражена несколькими способами, да? Таким образом, должно быть больше состояний, созданных из операций обмена? Вот ссылка на полный набор проблем, и это решение .

Answer 1

График, построенный с помощью кода в вопросе, связывает КАЖДОЕ ВОЗМОЖНОЕ состояние и, таким образом, подсчитывает общее количество состояний, возможных для конечного автомата, но НЕ максимальное количество уникальных состояний, которые монах может посетить в ЛЮБОМ исполнении Храма Навсегда. машина.

Подсчитывая узлы в стиле BFS, я исхожу из предположения, что можно достичь любого состояния через любое другое состояние. Это не так. После того, как операция обмена создает новое состояние, невозможно go вернуться в свое «родительское» состояние через своп (очевидно), и, таким образом, после того, как выбор сделан в ринге гонга, нет любое возвращение.

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

Вот код:

class Node:
    def __init__(self, r, g):
        self.r = r
        self.g = g

    def swap(self):
        ## if self.g <= 0 or self.r <= 0:
            ## return None
        ## Swaps with 0 allowed (only by commenting
        ## out the code above I get 52)
        return Node(self.g, self.r)

    def exchange(self):
        if self.r >= 3:
            return Node(self.r - 3, self.g + 2)
        return None

    def neighbours(self):
        s = self.swap()
        e = self.exchange()
        n = []
        for el in [s, e]:
            if el is not None:
                n.append(el)
        return n

    def __hash__(self):
        return hash((self.r, self.g))

    def __eq__(self, other):
        if self is None and other is None:
            return True
        if self is None or other is None:
            return False
        return self.r == other.r and self.g == other.g

    def __repr__(self):
        return "({}, {})".format(self.r, self.g)

start = Node(15, 12)
dfs_visited = set()
max_len = [0]  ## need a mutable data structure

def dfs(s, curr_len):
    for n in s.neighbours():
        if curr_len > max_len[0]:
            max_len[0] = curr_len
        if n not in dfs_visited:
            dfs_visited.add(n)
            dfs(n, curr_len+1)
    return max_len[0]

print(dfs(start, 0))

52

Answer 2

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

Мы должны отличаться guish между двумя разными числами:

1. Максимальное количество n посещенных состояний на любом пути, который может пройти монах;
2. Общее число N состояний, которые может достигнуть монах.

Обратите внимание, что N является количеством элементов объединения (принято по всем возможным путям) наборов состояний, посещаемых в любом одном пути. Это подразумевает n <= N </em>, и легко видеть, что эти числа не равны. В вопросе MIT задавался вопрос о n , тогда как оригинальный код OP был разработан для поиска N .

---

Приведенное доказательство является правильным, так что "верхняя граница для [ n ] составляет 25 + 26 + 1 = 52 ".

Я попытался использовать метод Монте-Карло для приближения N : Выберите случайным образом, обменивать или менять местами, когда есть выбор, повторять, пока процесс не будет колебаться между (2, 0) и (0, 2) и повторять все это огромное количество раз, при этом отслеживая все уникальные посещенные состояния.

Однако это не представляется практичным, поскольку число возможных путей слишком велико, поэтому число, которое мы получаем, не приближается к N с любым возможным числом итераций. Следующий код уже занял на моей машине около 15 минут.

import random

def swap(i, j):
    i, j = j, i
    return i, j

def exchange(i, j):
    i, j = i - 3, j + 2
    return i, j

x, y = 15, 12
visited = {(x, y)}

for run in range(1_000_000_000):
    while x + y > 2:
        if x < 3:
            x, y = swap(x, y)
        else:
            coinflip = random.randint(0, 1)
            if coinflip == 0:
                x, y = swap(x, y)
            else:
                x, y = exchange(x, y)
        visited = visited.union({(x, y)})

    x, y = swap(x, y)    
    visited = visited.union({(x, y)})

print('Visited states:', visited)
print('Number of visited states:', len(visited))

Посещенные состояния: {(18, 0), (4, 7), (1, 3), (3, 0), ( 0, 2), (4, 12), (11, 14), (2, 5), (0, 3), (8, 5), (5, 8), (15, 12), (8, 1), (16, 3), (5, 18), (1, 14), (14, 1), (3, 16), (8, 16), (4, 1), (12, 14) , (2, 20), (0, 18), (2, 10), (1, 4), (1, 19), (4, 2), (17, 4), (5, 3), ( 14, 11), (4, 6), (15, 2), (20, 2), (16, 8), (4, 17), (11, 3), (3, 1), (7, 4), (14, 12), (1, 8), (12, 4), (2, 0), (19, 1), (5, 2), (2, 4), (10, 2) }

Количество посещенных состояний: 46

Обновление: Вот график полного пространства состояний. N = 140

И вот путь в 52 государства. Зеленый X является отправной точкой, и каждый синий кружок обозначает посещенное состояние. Поскольку мы знаем из приведенного доказательства, что n <= 52, это доказывает <strong> n = 52 .