# Implementation of the module {heuristic3}. # Last edited on 2021-02-08 19:58:44 by jstolfi def best_path (R, G, Delta, parameters, start_time): S_end = [].copy() T_end = None Cmax_end = 0 smax_end = 0 while True: Front = front.get_one(rev=False) (R) #Front = front.get_one(rev=True) (R) #Front = front.get_initial_fringe (R) #Front = front.get_initial_all (R) if Front != None: S_end, Cmax, smax = best_path_aux (S_end, Front, Delta, G, R, parameters, start_time) if S_end == None or S_end == -3: T_end = None break else: T_end = S_end[len(S_end)-1]['Tend'] if Cmax > Cmax_end: Cmax_end = Cmax smax_end = smax else: break return S_end, T_end, Cmax_end, smax_end def best_path_aux (S, Front, Delta, G, R, parameters, start_time): ind = 2 * len(S) indx = ' ' * ind if len(Front) == 0: return S, 0, None N = len(S) if N == 0: Rend = None Tend = 0 qend = None else: Rend = S[len(S)-1] Tend = Rend['Tend'] rbitend = Rend['rbit'] qend = Rend['p'][1-rbitend] Cands = [].copy() #List of pairs (move, reversebit) sameGroup = False # Variável utilizada para controlar a criação da lista candidatos {Cands}. # Adiciona na lista de canditados {Cands} apenas as linhas de raster # que atendem as restrições impostas na heurística 3. for i in range(len(Front)): if not sameGroup: # Verifica se é autorizado adicionar novos candidatos à lista de candidatos {Cands}. assert Front[i]['Tini'] == None # Certifica-se que a linha de raster {Front[i]} ainda não foi visitada. rasterLink = None if len(S) > 0: # Verifica se já existe alguma linha de raster adicionada na solução {S}. R1 = S[len(S)-1] # Última linha de raster adicionada à solução {S}. R2 = Front[i] # Linha de raster sendo analisada. # Caso a linha de raster sendo analisada pertença ao mesmo bloco que a última linha de # raster adicionada na solução {S}, procura o raster link que realiza a ligação entre elas. if R1['group'] == R2['group'] or ((R2['first'] and R1['rbit'] == 1-R2['rbit'])or (R2['last'] and R1['rbit'] == R2['rbit'])): for edge in range(2): R2 = Front[i] for side in R1['links'][edge]: if (side[0][3]['sid'] == R1['sid'] and side[0][5]['sid'] == R2['sid']) or (side[0][3]['sid'] == R2['sid'] and side[0][5]['sid'] == R1['sid']): if side[2 + (1 - R1['rbit'])] != None: # Como existe uma restrição que obriga que todas as linhas de raster de um bloco sejam visitadas em sequência # (ou seja, ao entrar em um bloco só é possível sair do mesmo depois que todas suas linhas são adicionadas à solução {S}), # quando existe uma linha de raster no {Front} que pertence ao mesmo bloco que a última linha adicionada à {S}, esta se # torna a única opção viável para ser adicionada em seguida à solução. # # OBS: apenas o lado da linha de raster que possui uma ligação com a linha de raster anterior é adicionado à # lista de candidatos. # # OBS2: caso existam duas linhas de raster no {Front} do mesmo grupo que a última linha de raster adicionada # em {S} pertence, apenas quem possui um raster link é adicionada aos candidatos. # # Nesse caso, a lista de candidatos é esvaziada, e apenas a linha de raster do mesmo bloco a compõe. if R1['group'] == R2['group']: sameGroup = True Cands = [].copy() rasterLink = side[2 + (1 - R1['rbit'])][0] Cands.append((Front[i], 1 - R1['rbit'], rasterLink)) if R2['first'] and R2['last']: # No caso da linha de raster em questão pertencer à um bloco composto por uma única linha de raster, # ou seja, {Front[i]} ser o início e o final do bloco ao mesmo tempo, é possível adicionar à lista de candidatos # os dois lados da linha de raster como entrada para o bloco. # Cands.append((R2, R1['rbit'], air_time(calculate_distance(qend, R2['p'][R1['rbit']]), parameters))) # Caso a linha de raster analisada {Front[i]} não pertença ao mesmo bloco que a última linha de raster adicionada à # solução {S}, e {Front[i]} seja a primeira e/ou última linha de raster de outro bloco, ela pode ser adicionada à # lista de candidatos {Cands}. if rasterLink == None and (Front[i]['first'] or Front[i]['last']): # Caso {Front[i]} não esteja conectada diretamente com a última linha de raster adicionada em {S}, # apenas linhas de raster que estão nas bordas de blocos podem entrar na lista de candidatos. Front[i]['rbit'] = Front[i]['rbitoriginal'] if Front[i]['first'] and Front[i]['last']: # No caso da linha de raster em questão pertencer à um bloco composto por uma única linha de raster, # ou seja, {Front[i]} ser o início e o final do bloco ao mesmo tempo, é possível adicionar à lista de candidatos # os dois lados da linha de raster como entrada para o bloco. # Cands.append((Front[i], 1-Front[i]['rbit'], air_time(calculate_distance(qend, Front[i]['p'][1-Front[i]['rbit']]), parameters))) elif Front[i]['last']: # Caso a linha de raster seja o "final" de um bloco, é necessário inverter seu sentido # antes de adicionar como candidata. Front[i]['rbit'] = 1-Front[i]['rbit'] Cands.append((Front[i], Front[i]['rbit'], air_time(calculate_distance(qend, Front[i]['p'][Front[i]['rbit']]), parameters))) Cands = exclude_bad_candidates_group (Rend, R, G, Cands, Front, Delta, ind, parameters) #Cands = sort_candidates_raster (qend, Cands) Cands = sort_candidates_dist (qend, Cands) #Cands = sort_candidates_none (qend, Cands) if len(S) == 99999: print_cands (Cands, ind) sys.exit() if (time.time() - start_time) > 600: return -3, 0, 0 for k in range(len(Cands)): Ck = Cands[k] Rk = Ck[0] #assert Rk['rbit'] == 0 rbitk = Ck[1] pk = Rk['p'][rbitk] qk = Rk['p'][1-rbitk] ek = Rk['e'] assert Rk['Tini'] == None assert Rk['Tend'] == None if qend != None: Tinik = Tend + Ck[2]#air_time (calculate_distance(qend, pk), parameters) else: Tinik = 0 Rk['Tini'] = Tinik Tendk = Tinik + ek Rk['Tend'] = Tendk qend = qk Rk['rbit'] = rbitk S.append(Rk) if verbose: sys.stderr.write("%s---------------------------------------------\n" % indx) print_move (Rk, 0, 'appended', ind) sys.stderr.write("%s---------------------------------------------\n" % indx) else: sys.stderr.write("%sappended R%03d:%d, Tini = %.6f, Tend = %.6f \n" % (indx, Rk['sid'], Rk['rbit'], Rk['Tini'], Rk['Tend'])) Cmax_k, smax_k = worst_cooling_one (Rk) NewFront = heuristic3.update_front (Front, Rk, G, R) S_rec, Cmax_rec, smax_rec = best_path_aux (S, NewFront, Delta, G, R, parameters, start_time) if S_rec != None: if Cmax_rec > Cmax_k: return S_rec, Cmax_rec, smax_rec else: return S_rec, Cmax_k, smax_k else: Rk['rbit'] = Rk['rbitoriginal'] Rk['Tini'] = None Rk['Tend'] = None S.pop() if verbose: sys.stderr.write("%s---------------------------------------------\n" % indx) print_move (Rk, rbitk, 'deleted', ind) sys.stderr.write("%s---------------------------------------------\n" % indx) else: sys.stderr.write("%sdeleted R%03d:%d \n" % (indx, Rk['sid'], rbitk)) sys.stderr.write("%s**FAILED\n" % indx) return None, None, None def update_front(Front, el, G, R): L = [] # Keep all {Front} elements that are not {el}: for Fk in Front: if Fk != el: L.append (Fk) # Add the elements adjacent to {el} and group entry ones: ct = path.contacts(el) for ctk in ct: for i in range(2): el_new, ix_new = contact.side(ctk, i) added = add_element(L, el_new) if added and el_new.grp != el.grp: # Add the entry elements of the same group: grp = el_new.grp added0 = add_element(L, grp.entry[0]) added1 = add_element(L, grp.entry[1]) return L