Çok parçalı algoritma - Multi-fragment algorithm

Çok parçalı algoritma
SınıfYaklaşık algoritma
Veri yapısıGrafik
En kötü durumda verim

çok parçalı (MF) algoritması bir sezgisel veya yaklaşım için algoritma seyyar satıcı sorunu (TSP) (ve ilgili sorunlar). Bu algoritmaya bazen TSP için "açgözlü algoritma" da denir.

Algoritma, seyahat eden satıcı için bir seferde bir uç tur oluşturur ve böylece her biri şehirlerin tam grafiğinde basit bir yol olan birden fazla tur parçasını korur. Her aşamada, algoritma ya yeni bir parça oluşturan, mevcut yollardan birini genişleten ya da şehirlerin sayısına eşit bir uzunluk döngüsü oluşturan minimum maliyetin kenarını seçer.[1]

Referanslar

  1. ^ Johnson, David; A. McGeoch, Lyle (1997). "Seyahat Eden Satıcı Sorunu: Yerel Optimizasyonda Bir Örnek Olay". Kombinatoryal Optimizasyonda Yerel Arama. 1. CiteSeerX  10.1.1.92.1635.