Esercizio 1:
Applicare l'algoritmo primale-duale relativo al node-cover per trovare la soluzione 2-approssimata del problema. Individuare pertanto la sequenza di voli che garantisca il minimo costo.Sono dati i seguenti pairings ammissibili:
- Berlino-Amsterdam-Atene {1,2,3}
- Roma-Budapest {4,5}
- Roma-Amsterdam-Helsinki {4,2,6}
- Helsinki-Londra {6,7}
- Berlino-Londra {1,7}
- Atene-Budapest {3,5}
Abbiamo I = {F1, F2, ..., F7} V servizio h = 1,...,7.Fn ⊆ J sono insiemi che contengono lo stesso servizio h.J = {1,...,6} pairings ammissibili
Svolgimento:
- Determino gli Fn:
- F1 = {1,5}
- F2 = {1,3}
- F3 = {1,6}
- F4 = {2,3}
- F5 = {2,6}
- F6 = {3,4}
- F7 = {4,5}
- T ⊆ J è un cover ⟺ |Fi ∩ T| ≥ 1 ∀ Fi ∈ I
Nodi := pairings ammissibiliArchi := FiVediamo che ogni arco sia coperto
Esercizio 1:
Applicare l'algoritmo primale-duale relativo al Node-Cover per trovare la soluzione 2-approssimata del problema. Individuare pertanto la sequenza di voli che garantisca il minimo costo.
Sono dati i seguenti pairings ammissibili:
- Berlino - Amsterdam - Atene {1, 2, 3}
- Roma - Budapest {4, 5}
- Roma - Amsterdam - Helsinki {4, 2, 6}
- Helsinki - Londra {6, 7}
- Berlino - Londra {1, 7}
- Atene - Budapest {3, 5}
Abbiamo I = {F1, F2, ..., F7} ∀ servizio ń = 1, ..., 7.
Fn ⊆ J sono insiemi che contengono lo stesso servizio ń J = {1, ..., 6} pairings ammissibili
Svolgimento:
- Deterimino gli Fn:
F1 = {1, 5} F2 = {1, 3} F3 = {1, 6} F4 = {2, 3} F5 = {2, 6} F6 = {3, 4} F7 = {4, 5}
- T ⊆ J è un cover <=> |Fi ∩ T| ≥ 1 ∀ Fi ∈ I
Nodi := pairings ammissibili Archi := Fi
Vogliamo che ogni arco sia coperto
- Vogliamo trovare il cammino a costo minimo
- Definiamo primale e duale
Primale
min cTu
ΣeεF ue ≥ 1 FεI
ue ≥ 0 eεJ
Duale
max 1Ty
ΣFεI yF ≤ ce eεJ
yF ≥ 0 FεI
- F1 u1 + u5 ≥ 1
- F2 u1 + u3 ≥ 1
- F3 u1 + u6 ≥ 1
- F4 u2 + u3 ≥ 1
- F5 u2 + u6 ≥ 1
- F6 u3 + u4 ≥ 1
- F7 u4 + u5 ≥ 1
u1, ..., u6 ≥ 0
- Paso Φ: Scelgo una soluzione iniziale
- Passo 1: Scelgo una &overline;F
=> Aggiungo J¯:
J¯ = J¯ ∪ {1,3} = {1,3}
=> Aggiungo Y¯F2 = 1
=> Aggiungo T - J¯ = {1,3}
● PASSO 2:
Scelgo una F¯ che non interseca J¯:
F¯ = F5 = {2,6} ^ {1,3} = ∅
Infatti in J¯ = {1,3} non ci sono {2,6}
=> non avrei potuto inserire F1, F3, F4, F6.
=> Aggiungo YF = Y¯F5 = Y¯F5 + min{2,6} (ce - ΣY¯F)
= 0 + min{(1 - Y¯F4 - YF5), (1 - Y¯F3 - YF5)}{2,6}
= 0 + min{(1,1)}{2,6} = 1
=> Aggiungo J¯:
J¯ = J¯ ∪ {2,6} = {1,3,2,6}
=> Aggiungo Y¯ = Y¯F5 = 1
=> Aggiungo T - J¯ = {1,3,2,6}
● PASSO 3:
Scelgo una F¯ che non interseca J¯:
=> F¯ = F7 = {4,5}
● Aggiungo YF¯ = Y¯F7 = Y¯F7 + minc∈F¯ (ce - ΣY¯F)
= 0 + min{(1 - Y¯
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Recensioni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
