Da tempo cerco di risolvere Edifici Universitari, ma non riesco a capire come affrontarlo. Avevo pensato di vedere le distanze tra gli edifici di studio e provare a corstruire un ciclo, ma non sono sicuro.
Un indizio?
Vediamo cosa ti dice il testo del problema:
- Devi visitare tutti i K nodi e tornare al punto di partenza.
- Puoi passare più volte dallo stesso nodo, ergo di tutto il resto del grafo eccetto i K nodi (e il punto di partenza scelto) te ne importa poco.
- Puoi quindi ridurre il grafo a una tabella di distanze, dove in
dist[i][j]c’è la distanza tra il nodo i e il nodo j. - K ha valori molto bassi, quindi anche una soluzione esponenziale, mettiamo O(2^n) O per la precisione, O(n^2 2 ^n) potrebbe funzionare.
Ti ricorda qualche problema molto conosciuto? Dai un’occhata al Traveling Salesman Problem
1 Mi Piace
Grazie, é piu o meno quello che pensavo