SaraP
90 lines
3.5 KiB
C++
90 lines
3.5 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2015-2015
|
|
//----------------------------------------------------------------------------
|
|
// File : NN.cpp Data : 22.12.15 Versione : 1.6l4
|
|
// Contenuto : Miglioramento del percorso con metodo ibrido (ad ogni passo
|
|
// si sceglie il meglio tra i metodi Popt e TwoOpt). *
|
|
//
|
|
//
|
|
//
|
|
//
|
|
// Modifiche : 22.12.15 DS Creazione modulo.
|
|
//
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
//--------------------------- Include ----------------------------------------
|
|
#include "stdafx.h"
|
|
#include "ShortestPath.h"
|
|
|
|
// ----------------------------------------------------------------------------
|
|
long long unsigned
|
|
ShortestPath::Hybrid( NODE* pPath)
|
|
{
|
|
const int MAX_TRY = 2048 ;
|
|
unsigned count = 1 ;
|
|
NODE* pFirst = pPath ;
|
|
unsigned nTry = 1 ;
|
|
do {
|
|
NODE* pLast = pFirst->pPrev ;
|
|
NODE* pKth = pFirst->pNext ;
|
|
do {
|
|
// Point-Opt ( D1=new, D3=original)
|
|
unsigned D1 = ArcCost( pKth->nPos, pKth->pNext->pNext->nPos) +
|
|
ArcCost( pKth->pNext->nPos, pFirst->nPos) +
|
|
ArcCost( pLast->nPos, pKth->pNext->nPos) ;
|
|
unsigned D3 = ArcCost( pLast->nPos, pFirst->nPos) +
|
|
ArcCost( pKth->nPos, pKth->pNext->nPos) +
|
|
ArcCost( pKth->pNext->nPos, pKth->pNext->pNext->nPos) ;
|
|
// Two-Opt ( D2=new, D4=original)
|
|
unsigned D2 = ArcCost( pFirst->nPos, pKth->pNext->nPos) +
|
|
ArcCost( pLast->nPos, pKth->nPos) ;
|
|
unsigned D4 = ArcCost( pLast->nPos, pFirst->nPos) +
|
|
ArcCost( pKth->nPos, pKth->pNext->nPos) ;
|
|
// Lunghezze originali e nuova del tratto intermedio che viene invertito
|
|
for ( NODE* pCurr = pFirst ; pCurr != pKth ; pCurr = pCurr->pNext) {
|
|
D4 += ArcCost( pCurr->nPos, pCurr->pNext->nPos) ;
|
|
D2 += ArcCost( pCurr->pNext->nPos, pCurr->nPos) ;
|
|
}
|
|
if ( D1 < D3 || D2 < D4) {
|
|
if ( D1 < D3 &&
|
|
( D2 >= D4 || ( D3 - D1) >= ( D4 - D2))) {
|
|
NODE* pSave = pKth->pNext ;
|
|
pKth->pNext = pKth->pNext->pNext ;
|
|
pKth->pNext->pPrev = pKth ;
|
|
pLast->pNext = pSave ;
|
|
pFirst->pPrev = pSave ;
|
|
pSave->pNext = pFirst ;
|
|
pSave->pPrev = pLast ;
|
|
}
|
|
else {
|
|
for ( NODE* pReverse = pFirst ; pReverse != pKth ;) {
|
|
NODE* pSave = pReverse->pNext ;
|
|
pReverse->pNext = pReverse->pPrev ;
|
|
pReverse->pPrev = pSave ;
|
|
pReverse = pSave ;
|
|
}
|
|
pFirst->pNext = pKth->pNext ;
|
|
pKth->pNext->pPrev = pFirst ;
|
|
pKth->pNext = pKth->pPrev ;
|
|
pKth->pPrev = pLast ;
|
|
pLast->pNext = pKth ;
|
|
}
|
|
count = 0 ;
|
|
pFirst = pLast->pNext ;
|
|
pKth = pFirst->pNext ;
|
|
}
|
|
else
|
|
pKth = pKth->pNext ;
|
|
} while ( pKth != pLast->pPrev->pPrev && count != 0) ;
|
|
if ( count != 0)
|
|
pFirst = pFirst->pNext ;
|
|
count ++ ;
|
|
nTry ++ ;
|
|
} while ( count < m_nNumPnts && nTry < MAX_TRY) ;
|
|
|
|
// ricalcolo il costo del percorso
|
|
return TotalCost( pPath) ;
|
|
}
|
|
|