Tecnicamente questa non è una risposta alla tua domanda di base. Questa è una risposta alla tua domanda attuale che è: Come penso a questo problema, sicuramente c'è un modo migliore della forza bruta?
Come per qualsiasi problema, pensa a come faresti tu stesso.
Ti è stato fornito un elenco di connessioni e distanze che sarebbero state percorse su di loro. Quale connessione ti darebbe la maggiore possibilità di separarti dalla più lunga delle due vie di connessione?
Puoi scegliere il più piccolo, ma ciò contribuirebbe solo a una piccola distanza dal totale percorso. Che ne dici di scegliere il più grande? Sarebbe più efficace?
Okay, ora il lavoro è finito? No. Hai bisogno di un'altra connessione - ma come sceglierla? dovresti scegliere il prossimo più piccolo, o il prossimo più grande? C'è qualche altra proprietà che deve essere mantenuta, oh guarda una città deve essere condivisa tra i due lati. Quindi puoi scegliere lo stesso limite? No.
Hmm, quindi prendi tutti i bordi che si collegano alla prima o all'ultima città. Aspetta che include il primo margine, okay sbarazzati di quel limite. Ora quale lato dovrebbe essere scelto? Il più piccolo, o il più grande?
Hai finito adesso? Hai due lati, si collegano l'un l'altro. Sono i più lunghi? Come sei sicuro?
Come puoi capire che sei sicuro? Hmm, la connessione più lunga possibile sarebbe lungo i due bordi più lunghi (lascia immaginare che siano collegati). Ogni altra connessione deve essere più breve di questa. È utile? beh se sono i due lati appena colti alla grande, sono i più lunghi, non rimane altro da fare. Ma. Cosa succede se non lo sono? Hmm, non molto utile.
Ok, torna al tavolo da disegno. Come sai che hai la via più lunga, dato che hai in qualche modo scelto il primo vantaggio corretto. È il bordo più corto o più lungo collegato. Puoi assicurarti che il percorso in quella coppia sia il più grande possibile? Come?
Ora come scegli il primo bordo corretto? In modo che il percorso sia il più lungo possibile? Niente mi viene in mente. Ok, cosa ti dice questo secondo spigolo? Beh, deve essere più corto del primo, altrimenti lo avresti scelto prima. Il che significa che il secondo spigolo deve essere più piccolo, se hai scelto un bordo ancora più piccolo renderà il percorso più grande, o più piccolo? Forse puoi escludere quei bordi che possono solo creare un percorso complessivo più breve. Puoi anche escludere quel secondo bordo, quindi devi solo guardare quei bordi che potrebbero fare un percorso più lungo di questo. (altrimenti hai già il più lungo).
hmm, quindi se prima scegli il bordo più grande, e poi accoppialo. In quella coppia il cambio di uno spigolo con un altro spigolo deve fare un percorso più breve. freddo. Ma c'è un altro paio di bordi fatti di bordi che possono essere più lunghi? Forse 7 + 3 > 8 + 1. Un lato deve diventare più grande e l'altro leggermente più piccolo.
Quindi forse puoi perfezionare le possibili soluzioni fino a quando c'è un chiaro vincitore. Hai bisogno di guardare ogni riga tra le due righe? probabilmente non 8 + 1 > 4 + 3.
Quanto sopra è una serie di domande approssimative che mi sono posto fino a quando non sono diventato sicuro di poter effettivamente scrivere il codice per risolverlo. Lascerò capire queste domande e trasformarle in codice come esercizio per te. Per essere chiari, l'algoritmo è approssimativamente O (log (N) K), molto meglio della forza bruta O (N ^ 2).