Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Jogo com base round-robin scheduler (fila circular)

0 votos
81 visitas
perguntada Set 10, 2020 em Matemática por daniel cunha (31 pontos)  

Questão C-6.30 do livro "Data Structures and Algorithms in Python" de Michael T. Goodrich, Roberto Tamassia e Michael H. Goldwasser.

Alice has two queues, \( Q\) and \( R\) , which can store integers, Bob gives Alice 50 odd integers and 50 even integers and insists that she store all 100 integers in \( Q\) and \( R\). They then paly a game where Bob picks \( Q\) or \( R\) at random and then applies the round-robin scheduler, described in the chapter, to the chosen queue a random number of times. If the last number to be processed at the end of this game was odd, Bob wins. Otherwise Alice wins. How can Alice allocate integers to queues to optimize her change of winnning? What is her chance of winning?

Alice tem duas filas, \( Q\) e \( R\), que podem armazenar inteiros, Bob dá a Alice 50 inteiros ímpares e 50 inteiros pares e insiste que ela armazene todos os 100 inteiros em \( Q\) e \( R\). Eles então jogam um jogo em que Bob pega \( Q\) ou \( R\) aleatoriamente e, em seguida, aplica o agendador round-robin, descrito no capítulo, à fila escolhida um número aleatório de vezes. Se o último número a ser processado no final do jogo for ímpar, Bob ganha. Caso contrário, Alice ganha. Como Alice pode alocar números inteiros para filas para otimizar sua mudança de vitória? Qual é a chance dela de ganhar?

Compartilhe

3 Respostas

0 votos
respondida Set 10, 2020 por daniel cunha (31 pontos)  
editado Dez 15, 2020 por daniel cunha

A ideia do round-robin schedular e' retirar o primeiro elemento de fila e depois move-lo para o final da fila, ou seja, para dada fila \(Q\) devemos fazer \(Q.enqueue(Q.dequeue())\)

O capitulo 7 do livro em comento possui uma figura que ilustra essa operacao:
A imagem será apresentada aqui.

Analiticamente, podemos calcular a probabilidade de Alice ganhar o jogo considerando 3 casos:

Caso 1: Distribuicao proporcional \((1/2)\) de ímpares e pares nas duas filas.
Se duas filas tiverem número igual de inteiros pares e ímpares, a probabilidade de Alice ganhar será:

\( 0.5 \times \left(\frac{20}{40} + \frac{30}{60}\right) = 50(\%) \)

Caso 2: Alocando somente numeros pares uma fila com \(len(Q)>1\) e outros numeros pares residuais na outra fila com os numeros impares.

Por exemplo, Alice pode alocar 30 pares numa fila e os 20 restantes na outra

\(0.5 \times \left(1 + \frac{20}{70}\right) \approx 64.29(\%)\)

Caso 3 (solucao otima): Alocando um número par para uma fila e outros na outra fila.

Assim, a probabilidade de Alice ganhar sera:

\(0.5 \times \left(1 + \frac{49}{99}\right) \approx 74.75(\%)\)

Indo para a resolucao do problema, precisamos importar uma biblioteca para fazer simulacoes e criar uma classe para fazer operacoes em filas circulares. Para fazer tal classe, tomei a classe detalhado no capitulo 7 do livro em quesito.

import random

class Empty(Exception):

pass

class CircularQueue:

class _Node:
    __slots__ = '_element', '_next'
    def __init__(self, element, next):
        self._element = element
        self._next = next

######### Methods for CircularQueue.

def __init__(self):
    # we just need a single pointer that points to tail
    self._size = 0
    self._tail = None

def __len__(self):
    return self._size

def is_empty(self):
    return self._size == 0

def first(self):
    if self.is_empty():
        raise Empty('Queueu is Empty')
    return self._tail._next._element

def dequeue(self):
    # raise exception in the Queue is empty
    if self.is_empty():
        raise Empty('Queueu is Empty')

    old_head = self._tail._next
    if self._size == 1:
        self._tail = None
    else:
        self._tail._next = old_head._next


    # Update the current size
    self._size -= 1

    return old_head._element

def enqueue(self, e):
    # Create node to be enqueued from the tail.
    new_node = self._Node(e, None)
    # _next of the Current tail point to the head.
    if self.is_empty():
        # If the queue is currently empty.
        # tail and head both should be new node. 
        new_node._next = new_node
    else:
        new_node._next = self._tail._next
        self._tail._next = new_node

   # current_head = self._tail._next
   # Since new_node would become the tail, its _next should point to the head.
   #new_node._next = current_head
   # _next of The current tail should point the new_node.
   # self._tail._next = new_node
   # Update the current tail.
    self._tail = new_node
    # Update the current size
    self._size += 1


def rotate(self):
    # This function makes the current head as the new tail.
    current_head = self._tail._next
    self._tail = current_head



    pass

Precisamos tambem criar uma funcao para na qual o jogo sera "jogado" de modo que temos que definir o numero de turnos do jogo bem como numero rotacoes que cada jogador podera fazer em cada turno.

def jogo_round_robin(Q, R, num_turns = 50, max_rotations = 25):
for _ in range(num_turns):
    current_array = Q if random.random()>0.5 else R
    for _ in range(random.randint(0, max_rotations)):
        final_processed_value = current_array.first() 
        current_array.rotate()

return final_processed_value % 2 == 0

Vamos agora calcular a probabilidade de vitoria de Alice em cada caso. Para tanto, vamos fazer uma simulacao com 10000 cenarios. A simulacoes demoram um pouco para rodar, sinalizando que a eficiencia pode ser melhorada. Ademais, pela lei do grandes numeros, e' razoavel supor que a probabilidade calculada abaixo se aproxime assintoricamente para aquela computada na parte analitica da resposta.

Calculando a probabilidade para o caso 1:

if __name__ == '__main__':

Q, R = CircularQueue(), CircularQueue()

total_wins = 0
num_games = 10000
for game in range(num_games):
    for i in range(0, random.randint(-1, 99)):
        Q.enqueue(i)
    for k in range(len(Q),100):
        R.enqueue(k)
    if jogo_round_robin(Q, R): total_wins+=1



print(f'Alice ganhou {total_wins/num_games*100}% dos jogos')

Calculando a probabilidade para o caso 2:

if __name__ == '__main__':

Q, R = CircularQueue(), CircularQueue()

total_wins = 0
num_games = 10000
for game in range(num_games):
    g = random.randint(0, 98)
    if g % 2 ==0:
        g =g
    else:
        g = g+1
    l1=[]
    for k in range(g+3,100):
        l1.append(k)
    l2=[]
    for z in range(1, g+1, 2):
        l2.append(z)
    l = l1 + l2
    for i in range(0, g, 2):
        Q.enqueue(i)
    for x in l:
        R.enqueue(x)
    if jogo_round_robin(Q, R): total_wins+=1

print(f'Alice ganhou {total_wins/num_games*100}% dos jogos')

Calculando a probabilidade para o caso 3:

if __name__ == '__main__':


Q, R = CircularQueue(), CircularQueue()

Q.enqueue(0)

for i in range(1, 100):
    R.enqueue(i)

total_wins = 0
num_games = 10000
for game in range(num_games):
    if jogo_round_robin(Q, R): total_wins+=1

print(f'Alice ganhou {total_wins/num_games*100}% dos jogos')
0 votos
respondida Nov 29, 2020 por Lucas Lourenço (91 pontos)  

A implementação do Daniel é bastante interessante, parabéns pelo trabalho.
Comentários:
1.
Na solução do caso 2, não entendi muito bem algumas etapas, em especial a construção das filas l1 e l2. Me parece inclusive haver um typo na linha “l1.append(z)”. Dado que l2 foi definida logo acima, não seria l2.append(z)? No mais, observei também que as filas Q e R não estão sendo zeradas e recalculadas ao longo das diversas vezes em que o jogo é jogado. Por exemplo, ao introduzir

print(len(Q),len(R),f'Alice ganhou {total_wins/num_games*100}% dos jogos')

pude notar que a fila Q tinha comprimento 248.385 e a fila R, 721.848. Aparentemente, a magnitude desses objeto não chegam a comprometer a eficiência temporal do código. De qualquer forma, se pudermos reiniciar as filas a cada jogo, poderíamos ao menos melhorar a eficiência alocativa.
2.
Eu entendi aqui que o Daniel quis calcular qual probabilidade o caso genérico 2 converge independente do tamanho das filas Q e R (afinal, em cada loop elas assumem tamanhos diferentes e o resultado final é uma média de todos os casos possíveis). Como curiosidade, editei o código também para vermos qual a probabilidade com tamanhos fixos de listas. Isso é interessante pois note que ambos os casos abaixo se enquadram no caso 2, mas possuem resultados bem distintos:

Fila Q com 2 pares e 50 ímpares (comprimento = 52)
Fila R com 48 pares e 0 ímpares (comprimento = 48)

Probabilidade de vitória de Alice = 51,92%

Fila Q com 48 pares e 50 ímpares (comprimento = 98)
Fila R com 2 pares e 0 ímpares (comprimento = 2)

Probabilidade de vitória de Alice = 74,49%

No código original, ambos cenários poderiam ocorrer nas 10.000 partidas simuladas. O resultado obtido (≅ 66.2%) seria uma média entre todos os casos em que o número de pares em Q varia de 2 a 48. O código abaixo considera uma escolha fixa de números pares em Q. Após, organizei as probabilidades em uma tabela.

# Se quisermos olhar para a probabilidade de vitória dada uma escolha específica de números pares a serem alocados 
# na fila Q, basta tirarmos a definição de g do loop. Assim, jogamos 10 mil jogos para um g fixo. Ao final,
# comparamos a probabilidade teórica com a simulada:

lst=50*[0]+50*[1]
num_games = 10000
g = random.randint(2, 49)
#g = 30 # Pode usar essa linha para escolher um g específico 
total_wins=0
for game in range(num_games):   
    Q, R = CircularQueue(), CircularQueue()
    random.shuffle(lst)
    for k in lst:
        if len(Q)<g:       
            if k%2==0:
                Q.enqueue(k)
            else:
                R.enqueue(k)
        else:
            R.enqueue(k)
    if jogo_round_robin(Q, R): total_wins+=1

real_prob = round((0.5*(((50-g)/(100-g))+1)),4)

print(f'Número de pares alocados na fila Q: {g}')
print(f'Probabilidade teórica = {real_prob*100}%')
print(f'Probabilidade simulada = {round((total_wins/num_games)*100,2)}%')

Um exemplo do output do código acima:

Número de pares alocados na fila Q: 5
Probabilidade teórica = 73.68%
Probabilidade simulada = 73.5%

Finalmente, temos que a probabilidade converge para aproximadamente 65,2%, que é a média entre todas as alocações possíveis de pares na lista Q e mostrou-se mais precisa que o código original (≅66.2%). Não consegui diagnosticar se essa diferença de fato consiste em alguma falha na construção dos experimentos.

lst=50*[0]+50*[1]
total_wins = 0
total_games = 0
num_games = 1000
for g in range(2,50):
    for game in range(num_games):   
        Q, R = CircularQueue(), CircularQueue()
        random.shuffle(lst)
        for k in lst:
            if len(Q)<g:       
                if k%2==0:
                    Q.enqueue(k)
                else:
                    R.enqueue(k)
            else:
                R.enqueue(k)
        if jogo_round_robin(Q, R): total_wins+=1
        total_games += 1

total_wins/(total_games)

total = float()
for g in range(2,50):
    real_prob_g = round((0.5*(((50-g)/(100-g))+1)),4)
    total += real_prob_g
real_prob = total/48

print(f'Probabilidade teórica = {round(real_prob*100,2)}%')
print(f'Probabilidade simulada = {round((total_wins/(total_games))*100,2)}%')

A imagem será apresentada aqui.

comentou Dez 15, 2020 por daniel cunha (31 pontos)  
Muito obrigado, Lucas! De fato tinha um typo no caso 2 que ja foi corrigido.
0 votos
respondida Nov 29, 2020 por Lucas Lourenço (91 pontos)  

No exercício resolvido pelo Daniel, Bob escolhia aleatoriamente entre as filas Q e R. Porém, o que aconteceria se Bob ficasse desconfiado de que a estratégia ótima de Alice fizesse com que ele tivesse probabilidade maior de vitória em uma das filas? Um exercício possível seria considerar que agora, ao final de cada rodada, Bob trocará de fila sempre que perder e continuará escolhendo a mesma fila sempre que ganhar. Duas perguntas: as probabilidades calculadas pelo Daniel seguiriam as mesmas? A decisão ótima de Alice, dada pelo caso 3, seguiria sendo a mesma?
Primeiro, um pouco de probabilidade e teorema de Bayes ao nosso problema. Vamos inverter a lógica do problema para o ponto de vista de Bob e denominar \( P(Q) \) e \( P(R) \) as probabilidades de ele escolher as filas Q e R, respectivamente. Podemos representar as probabilidades de vitória e derrota em termos de esperança condicional:

\[ P(perder│Q)=49,49\% \\ P(perder│R)=100\% \\ P(ganhar│Q)=50,51\% \\ p(ganhar│R)=0\% \\ \]

Note que na fila R ele sempre perde, enquanto que na fila Q as chances se equilibram entre Bob e Alice (já que Alice alocou 49 pares e 50 ímpares). No primeiro round, Bob escolhe aleatoriamente (isto é, \( P(Q)=P(R)=50% \) ). As chances no primeiro round são as mesmas de antes, pois até aqui o problema é idêntico ao original, e consistem no melhor cenário possível para Alice:
\[ P(ganhar)=25,25\% \\ P(perder)=74,75\% \\ \]
No round 2, Bob atualizará sua escolha de acordo com o resultado da primeira rodada. Como ele muda de fila quando perde, as probabilidades condicionais ficam sendo o complementar da fórmula de Bayes (a intuição é que para Bob escolher Q dado que perdeu, ele precisa ter escolhido R no round 1 pois, lembre-se, ele troca de fila quando perde):
\[ \bar{P} (Q│perdeu)= \frac{P(perder│R).P(R)}{P(perder│R).P(R)+ P(perder│Q).P(Q)} \\ \bar{P} (Q│perdeu)= \frac{1-P(perder│Q).P(Q)}{P(perder│R).P(R)+ P(perder│Q).P(Q)} \\ \]

Em caso de vitória, usamos a fórmula original de Bayes:
\[ \bar{P} (Q│ganhou) = \frac{P(ganhar│Q).P(Q)}{(P(ganhar│R).P(R)+ P(ganhou│Q).P(Q))} \]

As probabilidades condicionais ficam:
\[ P(Q│perdeu)=66,89\% \\ P(R│perdeu)=33,11\% \\ P(Q│ganhou)=100\% \\ P(R│ganhou)=0\% \\ \]

Com esses valores, obtemos as probabilidades incondicionais de escolha de Q e R na rodada 2:
\[ P(Q)=P(Q│ganhou).P(ganhar)+ P(Q│perdeu).P(perder) \\ P(Q)=1 .0,2525+0,6689 .0,7475=75,25\% \\ P(R)=P(R│ganhou).P(ganhar)+ P(R│perdeu).P(perder) \\ P(R)=0 .0,2525+0,3311 .0,7475=24,75\% \\ \]
Chegamos então às probabilidades na rodada 2:
\[ P(ganhar)=38,01\% \\ P(perder)=61,99\% \\ \]
Assim, Bob melhora suas chances de 25,25% para 38,01%. No entanto, essas não são as probabilidades finais se o jogo for repetido n vezes. As probabilidades de vitória e derrota convergem para 33,78% e 66,22%. Bob melhora suas chances, mas continua consideravelmente atrás. A escolha ótima de Alice segue a mesma.

Implementação em Python:
A modificação no código original é bem simples. Na primeira rodada, a escolha é aleatória, como antes. A partir da segunda, memorizamos o resultado da rodada passada para que Bob possa tomar a decisão.

# Na primeira parte (após if count == 0), a escolha entre as filas é aleatória, igual o problema original.
# Na segunda parte (a partir do else), o objeto 'next_row' definirá qual fila Bob escolherá. 

def jogo_round_robin2(Q, R, num_turns = 10, max_rotations = 10):
    if count == 0:
        for _ in range(num_turns):
            random_number = random.random()
            current_array = Q if random_number>0.5 else R
            for _ in range(random.randint(0, max_rotations)):
                final_processed_value = current_array.first() 
                current_array.rotate()
        return final_processed_value % 2 == 0, "Q" if random_number>0.5 else "R"
    else:
        current_array = Q if next_row == "Q" else R
        for _ in range(num_turns):
            for _ in range(random.randint(0, max_rotations)):
                final_processed_value = current_array.first()
                current_array.rotate()
        return final_processed_value % 2 == 0, next_row

# Calculando a probabilidade para o caso 3:

Q, R = CircularQueue(), CircularQueue()
Q.enqueue(0)
for i in range(1, 100):
    R.enqueue(i)

results=[]
count=0
total_wins = 0
num_games = 10000
for game in range(num_games):
    result=jogo_round_robin2(Q, R)
    if result[0]:
        total_wins+=1
        next_row = "Q" if result[1] == "R" else "R"
    else:
        next_row = "Q" if result[1] == "Q" else "R"
    count += 1
results.append(total_wins)

print(f'Alice ganhou {(sum(results)/len(results)/10000)*100}% dos jogos')
...