Dichtstbijzijnde buuralgoritme
Dit zijn de stappen van het algoritme:
- Initialiseer alle hoekpunten als niet bezocht.
- selecteer een willekeurig hoekpunt, stel het in als het huidige hoekpunt u. Markeer u als bezocht.
- ontdek de kortste rand die het huidige vertex u verbindt met een niet-bezocht vertex v.
- stel v in als het huidige vertex u. Markeer v als bezocht.
- als alle hoekpunten in het domein worden bezocht, beëindig dan. Else, ga naar stap 3.
De volgorde van de bezochte hoekpunten is de uitvoer van het algoritme.,
het dichtstbijzijnde buuralgoritme is eenvoudig te implementeren en snel uit te voeren, maar het kan soms kortere routes missen die gemakkelijk worden opgemerkt met menselijk inzicht, vanwege zijn “hebzuchtige” aard. Als algemene gids, als de laatste etappes van de tour qua lengte vergelijkbaar zijn met de eerste etappes, dan is de tour redelijk; als ze veel groter zijn, dan is het waarschijnlijk dat er veel betere tours bestaan. Een andere controle is om een algoritme zoals het ondergrens algoritme te gebruiken om in te schatten of deze tour goed genoeg is.,
in het ergste geval resulteert het algoritme in een tour die veel langer is dan de optimale tour. Om precies te zijn, voor elke constante r is er een voorbeeld van het reizende verkoper probleem zodanig dat de lengte van de tour berekend door het dichtstbijzijnde buur algoritme groter is dan r keer de lengte van de optimale tour. Bovendien is er voor elk aantal steden een toewijzing van afstanden tussen de steden waarvoor de dichtstbijzijnde buur heurist produceert de unieke slechtst mogelijke tour., (Als het algoritme wordt toegepast op elk hoekpunt als het startpunt, zal het beste gevonden Pad beter zijn dan ten minste N / 2-1 andere tours, waarbij N het aantal hoekpunten is.)
het algoritme van de dichtstbijzijnde buur vindt mogelijk helemaal geen haalbare toer, zelfs niet als er een bestaat.