# # Problema di "orienteering" con finestre temporali # # Dati 7 punti, ad ogni punto i siano associati il premio e la finestra temporale, # cioe' l'intervallo di tempo, descritti nella seguente tabella. # # i | Premio Inizio Fine # ---+--------------------------- # 1 | 0 0 400 # 2 | 80 0 100 # 3 | 250 60 50 # 4 | 100 20 200 # 5 | 180 55 100 # 6 | 50 30 250 # 7 | 200 10 210 # # E' anche dato il tempo necessario a muoversi fra un punto e ogni altro. # In generale questo tempo potrebbe non essere simmetrico. # # | 1 2 3 4 5 6 7 # ---+---------------------- # 1 | 0 86 49 57 31 69 50 # 2 | 86 0 68 79 93 24 5 # 3 | 49 68 0 16 7 72 67 # 4 | 57 79 16 0 90 69 1 # 5 | 31 93 7 90 0 86 59 # 6 | 69 24 72 69 86 0 81 # 7 | 50 5 67 1 59 81 0 # # Un esploratore deve partire dal punto 1 e tornarvi, raccogliendo i premi # dei punti che visita e rispettando le loro finestre temporali. # # Se indichiamo la finestra temporale del punto i con [e_{i},l_{i}]: # - l'esploratore non puo' passare per il punto i dopo l'istante l_{i} # - se l'esploratore arriva fra e_{i} ed l_{i}, puo' ripartire immediatamente # - se l'esploratore arriva prima di e_{i}, puo' ripartire solo all'istante e_{i} # # Si vuole trovare il percorso ammissibile che raccolga il massimo premio totale. #