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

Jogo com base round-robin scheduler (fila circular)

0 votos
14 visitas
perguntada Set 10 em Matemática por daniel cunha (11 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

1 Resposta

0 votos
respondida Set 10 por daniel cunha (11 pontos)  
editado Set 10 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):
        l1.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')
...