Mulţumiri

FamiliaDeCurbe.OptimizeazăFHTSP(Întreg nRezolvăComplet = 40)

{

FamiliaDeCurbe fcTemp;

Curbă cStart, cCurent;

Punct pCurent, pStart;

//dacă sunt puţine curbe rezolvă complet problema

Dacă(nNr <= nRezolvăComplet)

OptimizeazăTSP();

Altfel

{

cStart = [1];

fcTemp.PuneLa(cCurent); //adună curba 1

pStart = cStart[cStart.nNr]; //capătul de sfârşit

Şterge(1); //şi o şterge

PentruFiecare(Întreg nI = 2; nI <= nNr; nI++)

{

Real rDist = 1e100;

Întreg nDist = 0;

PentruFiecare(Întreg nJ = 1; nJ <= nNr; nJ++)

{

cCurent = [nI];

pCurent = cCurent[1]; //capătul de start

Dacă(DistXYZ(pCurent, pStart) < rDist)

{

rDist = DistXYZ(pCurent, pStart);

nDist = nI;

} //Dacă

} //PentruFiecare

cStart = [nDist];

pStart = cStart[cStart.nNr]; //capătul de sfârşit

Şterge(nDist);

} //PentruFiecare

} //Altfel

sdAceasta = fcTemp; //!! actualizează familia de curbe

} //OptimizeazăFHTSP

Algoritmul nu face altceva decât să sorteze curbele, în funcţie de distanţa minimă dintre capetele de sfârşit şi start, pornind cu prima curbă. Algoritmul care analizează distanţa dintre ambele capete, şi în cazul în care este parcursă în ordine inversă o inversează, este prea complicat pentru a fi expus.

Acest algoritm este însoţit de altul, care leagă capetele mai multor curbe, mai mici decât o distanţă (uzual 3..6 * pasul de procesare), şi astfel, necesarul de ieşiri şi intrări în material se reduce drastic (în exemplul ilustrat, de la circa 500 de intrări şi ieşiri au mai rămas 10, deci o optimizare de circa 98 %, iar timpul necesar acestei optimizări a fost de 2 secunde !).

Se prezintă, spre exemplificare, un caz de fişier NC echipotenţial, cu şi fără acest tip de optimizare, procesat cu aceleaşi condiţii iniţiale.

Figura 6.51 Optimizarea FHTSP pentru reducerea mişcărilor în avans rapid

• 
  fără FHTSP
  
• 
  cu FHTSP