Ho pensato al Problema del venditore ambulante . Nell'esaminarlo e nelle reti delle città, ho notato che potevo spesso scegliere il percorso più breve semplicemente fissandolo. Certo, non potevo necessariamente ottenere le soluzioni per le griglie complesse, ma se potessi ottenere quelle semplici ci doveva essere un modo per risolverle in modo coerente.
Mi sono reso conto che la maggior parte (tutti quelli che ho visto) hanno un percorso circolare intorno alle città, seguono un po 'un confine esterno. La mia idea era di iniziare con un algoritmo che segni i punti più esterni di una griglia sul maggior numero di lati possibile. Che è sempre almeno 4 (a meno che tu non abbia meno di 4) una città per ogni direzione cardinale. Qualcosa del genere:
(Dato, sono solo umano quindi ho per lo più indovinato quali città sarebbero state scelte. È possibile che l'algoritmo iniziale abbia scelto in modo diverso o scelto più di 4. Allo scopo di esempi però ...)
Quindil'algoritmotrovaunaltroinsiemedeipuntipiùesterni,esclusiipuntiprecedentementetrovati.Corrispondeaquestipunticonlalinearossapiùvicinaesiinseriscelì.
loripetefinoaquandotuttiipuntisonostatiselezionatieuniti.
Questo sembra funzionare abbastanza bene per le selezioni più semplici di città più piccole. Se non cade a pezzi per modelli più grandi e più complessi è ancora sconosciuto. Sospetto che si possa creare una città che rompe questo.
Comunque, sono per lo più curioso di sapere come si chiamerà questo algoritmo. Lo trovo affascinante e mi piacerebbe saperne di più.
Questa è davvero una soluzione al problema, o solo una stretta approssimazione?
