Home > Term: Algorisme Christofides
Algorisme Christofides
(1) Un algorisme heurístic per trobar una solució al problema de venedor ambulant a prop òptim. Pas 1: trobar un mínim que abasta arbre T. pas 2: trobar una perfecta concordança M entre els vèrtexs amb grau senar. Pas 3: combinar les vores del M i T a fer un multigraph G. pas 4: trobar un cicle d'Euler en G saltant-se vèrtexs ja vist. (2) Un algorisme per trobar el número cromàtic d'un gràfic.
- Jenis Kata: noun
- Industri / Domain: Sains komputer
- Kategori: Algorithms & data structures
- Government Agency: NIST
0
Penulis
- Carmesina
- 100% positive feedback
(Spain)