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

Como implementar uma solução inteligente para o problema conhecido como College Admission Problem?

+1 voto
93 visitas
perguntada Mai 31, 2016 em Ciência da Computação por Joao Ricardo (21 pontos)  

Discuta e Implemente uma solução inteligente para o problema conhecido como College Admissão Problem que generaliza o stable marriage problem em uma escola que aceita mais do que um aplicante.

Compartilhe

1 Resposta

+1 voto
respondida Mai 31, 2016 por Joao Ricardo (21 pontos)  
selecionada Jun 7, 2016 por Joao Ricardo
 
Melhor resposta

Realizaram-se as alterações no algoritmo Stable Marriage-Matching Problem conforme proposto no artigo "College Admissions and Stability of Marriage", de Gale and Shapley do ano de 1962. As alterações no algoritmo estão listadas nas páginas 13 e 14 do referido artigo. Primeiramente assume-se que se um aluno não pode aplicar para um colégio, ele não o fará. Em seguida, adotou-se o seguinte algoritmo: todos os alunos aplicam para sua primeira opção. Um colégio com cota "q" coloca os "q" estudantes com melhor rank que aplicaram para esse colégio em sua lista de espera, e rejeita os outros. Aqui a primeira diferença em relação ao algoritmo stable marriage, pois esse aceita somente 1 em vez de "q". Os alunos rejeitados então aplicam para os colégios de sua segunda opção. Os colégios, novamente, colocam os "q" melhores estudantes na sua lista de espera e rejeitam os outros. O algoritmo termina quando ou todos os estudantes estão em uma lista de espera de um colégio ou os estudantes que não estão em uma lista de espera foram rejeitados por todos os colégios. Essa é outra diferença em relação ao Stable Marriage, pois nesse algoritmo há n homens e n mulheres, não existindo a opção de "solteiros". As alterações mais significativas estão relatadas no algoritmo abaixo.

import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations
from collections import deque

np.random.seed(0)

def the_rank(collegePreference,subject):#retorna o rank do estudante, conforme o college o identifica
    return np.where(collegePreference[:]==subject)[0]

def the_worst_in_list(collegeAdmission,college):#retorna o estudante com o pior rank na lista do college
    i=0 
    theworst=collegeAdmission[college][0]
    while (i < q):
        if (the_rank(collegePreference,theworst) < the_rank(collegePreference,collegeAdmission[college][i])):
            theworst=collegeAdmission[college][i]
        i=i+1
    return theworst

def the_worst_in_list_index(collegeAdmission,college):#retorna o indice referente à lista do college do estudante com o pior rank
    return np.where(collegeAdmission[college][:]==the_worst_in_list(collegeAdmission,college))[0][0]

def freeStudent_rejectd_by_all(freeStudent,studentPosition):#retorna True se os estudantes na lista de freeStudents ja foram reprovados por todos os colleges
    R=True  
    for i in range(len(freeStudent)):
        if studentPosition[freeStudent[i]]<>(m-1):
            R=False
    return R

def stable_college_admission(studentPreferences,collegePreferences):
    n=np.shape(studentPreferences)[0]
    m=np.shape(collegePreferences)[0]
    freeStudent=deque()
    for i in range(n):
        freeStudent.append(i)
    studentPosition=np.empty([n]) 
    studentAdmitted=np.empty([n]) 
    collegeAdmission=np.empty([m,q])# introdução de "q"vagas. No Stable Marriage, q=1. 
    print freeStudent
    for i in range(n):
        studentPosition[i]=-1
        studentAdmitted[i]=-1
    for j in range(m):
        for k in range(q):        
            collegeAdmission[j,k]=-1
    while(len(freeStudent)!=0 and not (freeStudent_rejectd_by_all(freeStudent,studentPosition))):# critério de parada do algoritmo, pois pode haver mais alunos que colégios.
        student=freeStudent.popleft()
        print "student", student
        studentPosition[student]=studentPosition[student]+1
        studentAdmitted[student]=studentPreferences[student][studentPosition[student]]
        theLuckCollege=studentAdmitted[student]
        print "theLuckCollege", theLuckCollege
        if -1 in collegeAdmission[theLuckCollege][:]:
            for k in range(q):
                print "k", k
                if (collegeAdmission[theLuckCollege][k]==-1) and (student not in collegeAdmission[theLuckCollege][:]):
                    collegeAdmission[theLuckCollege][k]=student
        elif the_rank(collegePreferences,student)<the_rank(collegePreferences,the_worst_in_list(collegeAdmission,theLuckCollege)):
            freeStudent.append(the_worst_in_list(collegeAdmission,theLuckCollege))
            collegeAdmission[theLuckCollege][the_worst_in_list_index(collegeAdmission,theLuckCollege)]=student
        else:
            freeStudent.append(student)
        print collegeAdmission
        print "freeStudent", freeStudent
    print studentAdmitted

def main():
    n=13# numero de estudantes
    m=4#numero de colleges
    q=3#numero de vagas no college
    studentPreferences=np.empty([n,m])
    studentPreferences[0][:]=1,0,2,3
    studentPreferences[1][:]=1,2,3,0
    studentPreferences[2][:]=1,2,0,3
    studentPreferences[3][:]=2,1,3,0
    studentPreferences[4][:]=3,0,1,2
    studentPreferences[5][:]=2,3,0,1
    studentPreferences[6][:]=2,1,3,0
    studentPreferences[7][:]=1,2,0,3
    studentPreferences[8][:]=0,1,3,2
    studentPreferences[9][:]=2,3,0,1
    studentPreferences[10][:]=2,1,3,0
    studentPreferences[11][:]=3,1,2,0
    studentPreferences[12][:]=3,1,2,0

    collegePreference=np.empty([n])
    collegePreference[0]=0
    collegePreference[1]=1
    collegePreference[2]=2
    collegePreference[3]=3
    collegePreference[4]=4
    collegePreference[5]=5
    collegePreference[6]=6
    collegePreference[7]=7
    collegePreference[8]=8
    collegePreference[9]=9
    collegePreference[10]=10
    collegePreference[11]=11
    collegePreference[12]=12

    print studentPreferences
    print collegePreference
    stable_college_admission(studentPreferences,collegePreference)

if __name__ == '__main__':
    main()
comentou Jun 1, 2016 por danielcajueiro (5,726 pontos)  
João, seria legal se, antes de apresentar a solução, você puder explicitar as diferenças entre esse problema específico e o problema original e como você lidou para construir a solução para esse problema.
comentou Jun 1, 2016 por Joao Ricardo (21 pontos)  
Obrigado pela sugestão. Resposta editada.
...