Algoritme del veí més pròxim

El algoritme del veí més pròxim va ser, en les ciències de la computació, un dels primers algoritmes utilisats per a determinar una solució per al problema del viajante. Este método genera ràpidament un camí curt, pero generalment no l'ideal.

Avall està l'aplicació de l'algoritme del veí més pròxim al problema del viajante.

Estos són els passos de l'algoritme:

1. elecció d'un vèrtiç arbitrari respecte al vèrtiç actual.
2. descobrixca l'aresta de menor pes que ya este conectada al vèrtiç actual i a un vèrtiç no visitat V.
3. convertixca el vèrtiç actual en V.
4. marque V com visitat.
5. si tots els vèrtiços del domini estigueren visitats, tancament l'algoritme.
6. vaja al pas 2.

La seqüència dels vèrtiços visitats és l'eixida de l'algoritme.

L'algoritme del veí més pròxim és fàcil d'implementar i eixecutar ràpidament, pero algunes voltes pot perdre rutes més curtes, que són fàcilment notades en la visió humana, per la seua naturalea més "ávida". Com a norma general, si els últims passos del recorregut són comparables en llongitut al dels primers passos, el recorregut és raonable; si estos són molt majors, llavors és provable que existixquen camins molt millors.

Vore també

• Algoritme K-NN