Vícefragmentový algoritmus - Multi-fragment algorithm
| Třída | Aproximační algoritmus |
|---|---|
| Datová struktura | Graf |
| Nejhorší případ výkon |
The více fragmentový (MF) algoritmus je heuristický nebo přiblížení algoritmus pro problém obchodního cestujícího (TSP) (a související problémy). Tento algoritmus se také někdy nazývá „chamtivý algoritmus“ pro TSP.
Algoritmus vytváří cestu pro obchodního cestujícího po jedné hraně a udržuje tak několik fragmentů prohlídky, z nichž každý představuje jednoduchou cestu v úplném grafu měst. V každé fázi algoritmus vybere hranici minimálních nákladů, která buď vytvoří nový fragment, rozšíří jednu ze stávajících cest, nebo vytvoří cyklus délky rovný počtu měst.[1]
Reference
- ^ Johnson, David; A. McGeoch, Lyle (1997). „Problém obchodního cestujícího: případová studie v místní optimalizaci“. Místní vyhledávání v kombinatorické optimalizaci. 1. CiteSeerX 10.1.1.92.1635.
 | Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |