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:
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')