Здравствуйте, Yulesik!
Вот, перевела из этого алгорима. Если будут вопросы, пишите.
Результат проверила, с паскалевской программой совпадает.
Компилировалось под MS VS 2010.
Удачи!

Приложение:
#include <iostream>
#include <conio.h>
using namespace std;

const int COUNT_POINTS =6;

void FITSP (int N, int S, int INF, int W [COUNT_POINTS+1][COUNT_POINTS+1], int ROUTE [COUNT_POINTS+1], int &PATH_WEIGHT)
{
int END1,END2,FARTHEST,I,INDEX, INSCOST,J,MAXDIST,NEWCOST,NEXTINDEX;
int CYCLE [COUNT_POINTS+1], DIST[COUNT_POINTS+1];
for (I=1; I<=N; I++) CYCLE[I]=0;
CYCLE[S]=S;
for (I=1; I<=N; I++) DIST[I]=W[S][I];
PATH_WEIGHT=0;
for (I=1; I<=N-1; I++) {
MAXDIST=-INF;
for (J=1; J<=N; J++)
if (CYCLE[J] == 0)
if (DIST[J] > MAXDIST) {
MAXDIST=DIST[J]; FARTHEST=J;
}
INSCOST=INF; INDEX=S;
for (J=1; J<=I; J++) {
NEXTINDEX=CYCLE[INDEX];
NEWCOST=W[INDEX][FARTHEST]+W[FARTHEST][NEXTINDEX]-
W[INDEX][NEXTINDEX];
if (NEWCOST < INSCOST) {
INSCOST=NEWCOST;
END1=INDEX; END2=NEXTINDEX;
}
INDEX=NEXTINDEX;
}
CYCLE[FARTHEST]=END2; CYCLE[END1]=FARTHEST;
PATH_WEIGHT=PATH_WEIGHT+INSCOST;
for (J=1; J<=N; J++)
if (CYCLE[J] == 0)
if (W[FARTHEST][J] < DIST[J]) DIST[J]=W[FARTHEST][J];
}
INDEX=S;
for (int I=1; I<=N; I++) {
ROUTE[I]=INDEX; INDEX=CYCLE[INDEX];
}
}

enum SWAPTYPE { ASYMMETRIC, SYMMETRIC };
struct SWAPRECORD {
int X1,X2,Y1,Y2,Z1,Z2,GAIN;
SWAPTYPE CHOICE;
};

void SWAPCHECK(SWAPRECORD SWAP, int W[COUNT_POINTS+1][COUNT_POINTS+1])
{
int DELWEIGHT,MAX;
SWAP.GAIN=0;
DELWEIGHT=W[SWAP.X1][SWAP.X2]+W[SWAP.Y1][SWAP.Y2]+W[SWAP.Z1][SWAP.Z2];
MAX=DELWEIGHT-(W[SWAP.Y1][SWAP.X1]+W[SWAP.Z1][SWAP.X2]+W[SWAP.Z2][SWAP.Y2]);
if (MAX > SWAP.GAIN) {
SWAP.GAIN=MAX; SWAP.CHOICE=ASYMMETRIC;
}
MAX=DELWEIGHT-(W[SWAP.X1][SWAP.Y2]+W[SWAP.Z1][SWAP.X2]+W[SWAP.Y1][SWAP.Z2]);
if (MAX > SWAP.GAIN) {
SWAP.GAIN=MAX; SWAP.CHOICE =SYMMETRIC;
}
}

void REVERSE (int START, int FINISH, int PTR [COUNT_POINTS+1])
{
int AHEAD,LAST,NEXT;
if (START != FINISH) {
LAST=START; NEXT=PTR[LAST];
do {
AHEAD=PTR[NEXT]; PTR[NEXT]=LAST;
LAST=NEXT; NEXT=AHEAD;
} while (LAST != FINISH);
}
}

void THREEOPT (int N, int W[COUNT_POINTS+1][COUNT_POINTS+1], int ROUTE [COUNT_POINTS+1])
{
SWAPRECORD BESTSWAP,SWAP;
int I,INDEX,J,K;
int PTR [COUNT_POINTS+1];
for (I=1; I<=N-1; I++) PTR[ROUTE[I]]=ROUTE[I+1];
PTR[ROUTE[N]]=ROUTE[1];
SWAP.GAIN = 0;
do {
BESTSWAP.GAIN=0;
SWAP.X1=1;
for (I=1; I<=N; I++) {
SWAP.X2=PTR[SWAP.X1]; SWAP.Y1=SWAP.X2;
for (J=2; J<=N-3; J++) {
SWAP.Y2=PTR[SWAP.Y1]; SWAP.Z1=PTR[SWAP.Y2];
for (K=J+2;K<=N-1; K++) {
SWAP.Z2=PTR[SWAP.Z1];
SWAPCHECK(SWAP, W);
if (SWAP.GAIN > BESTSWAP.GAIN) BESTSWAP=SWAP;
SWAP.Z1=SWAP.Z2;
}
SWAP.Y1=SWAP.Y2;
}
SWAP.X1=SWAP.X2;
}
if (BESTSWAP.GAIN > 0) {
if (BESTSWAP.CHOICE == ASYMMETRIC) {
REVERSE(BESTSWAP.Z2,BESTSWAP.X1, PTR);
PTR[BESTSWAP.Y1]=BESTSWAP.X1; PTR[BESTSWAP.Z2]=BESTSWAP.Y2;
} else {
PTR[BESTSWAP.X1]=BESTSWAP.Y2; PTR[BESTSWAP.Y1]=BESTSWAP.Z2;
}
PTR[BESTSWAP.Z1]=BESTSWAP.X2;
}
} while (BESTSWAP.GAIN != 0);
INDEX=1;
for (I=1; I<=N; I++) {
ROUTE[I]=INDEX; INDEX=PTR[INDEX];
}
}

void TWOOPT(int N, int W [COUNT_POINTS+1][COUNT_POINTS+1], int ROUTE [COUNT_POINTS+1], int &PATH_WEIGHT)
{
int AHEAD,I,I1,I2,INDEX,J,J1,J2,LAST,LIMIT,MAX,MAX1,NEXT,S1,S2,T1,T2;
int PTR [COUNT_POINTS+1];
for (I=1; I<=N-1; I++)
PTR[ROUTE[I]]=ROUTE[I+1];
PTR[ROUTE[N]]=ROUTE[1];
do {
MAX=0; I1=1;
for (I=1; I<=N-2; I++) {
if (I == 1) LIMIT=N-1;
else LIMIT=N;
I2=PTR[I1]; J1=PTR[I2];
for (J=I+2; J<=LIMIT; J++) {
J2=PTR[J1];
MAX1=W[I1][I2]+W[J1][J2]-(W[I1][J1]+W[I2][J2]);
if (MAX1 > MAX )
{
S1=I1; S2=I2;
T1=J1; T2=J2;
MAX=MAX1;
}
J1=J2;
}
I1=I2;
}
if (MAX > 0 ) {
PTR[S1]=T1;
NEXT=S2; LAST=T2;
do {
AHEAD=PTR[NEXT]; PTR[NEXT]=LAST;
LAST=NEXT; NEXT=AHEAD;
} while (NEXT != T2);
PATH_WEIGHT=PATH_WEIGHT-MAX;
}
} while (MAX != 0);
INDEX=1;
for (I=1; I<=N; I++) {
ROUTE[I]=INDEX; INDEX=PTR[INDEX];
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int W [COUNT_POINTS+1][COUNT_POINTS+1] = {{-1, -1, -1, -1, -1, -1, -1},
{-1, 0, 0, 0, 3, 3, 6},
{-1, 0, 0, 1, 4, 1, 0},
{-1, 1, 2, 0, 0, 0, 3},
{-1, 4, 5, 0, 0, 0, 3},
{-1, 4, 2, 0, 0, 0, 0},
{-1, 7, 1, 3, 3, 0, 0}
};

int PATH_WEIGHT;
int ROUTE [COUNT_POINTS+1];
int i;
PATH_WEIGHT=0;
for (i=1; i<=COUNT_POINTS; i++) ROUTE[i]=i;
FITSP(COUNT_POINTS,1,999999,W,ROUTE,PATH_WEIGHT);
TWOOPT(COUNT_POINTS,W,ROUTE,PATH_WEIGHT);
THREEOPT(COUNT_POINTS,W,ROUTE);
for (i=1; i<=COUNT_POINTS; i++) cout << ROUTE[i] << "->";
cout << 1 << " = " << PATH_WEIGHT;
_getch();
return 0;
}