Riccardo Elitropi
558b590810
- Aggiunta classe di calcolo per ottimizzazione ordine delle lavorazioni - Aggiunti vincoli obbligatori e dipendenze suggerite a ShortestPath.
150 lines
5.3 KiB
C++
150 lines
5.3 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2015-2015
|
|
//----------------------------------------------------------------------------
|
|
// File : ShortestPath.h Data : 22.12.15 Versione : 1.6l3
|
|
// Contenuto : Classe per calcolo del percorso minimo di visita di
|
|
// un insieme di oggetti.
|
|
//
|
|
//
|
|
// Modifiche : 22.12.15 DS Creazione modulo.
|
|
//
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
#pragma once
|
|
|
|
#include "/EgtDev/Include/ENkShortestPath.h"
|
|
#include <string>
|
|
|
|
//----------------------------------------------------------------------------
|
|
#define MAXDIST 1073741823U // 2^30 - 1 per evitare overflow
|
|
#define ENABLE_DEBUG 0
|
|
|
|
//----------------------------------------------------------------------------
|
|
struct SpPoint {
|
|
double dXi ;
|
|
double dYi ;
|
|
double dZi ;
|
|
double dHi ;
|
|
double dVi ;
|
|
double dXf ;
|
|
double dYf ;
|
|
double dZf ;
|
|
double dHf ;
|
|
double dVf ;
|
|
} ;
|
|
|
|
struct OpenBound {
|
|
int nF ;
|
|
double dX ;
|
|
double dY ;
|
|
double dZ ;
|
|
double dH ;
|
|
double dV ;
|
|
} ;
|
|
|
|
struct NODE {
|
|
NODE* pPrev ;
|
|
unsigned nPos ;
|
|
NODE* pNext ;
|
|
} ;
|
|
|
|
//----------------------------------------------------------------------------
|
|
class ShortestPath : public IShortestPath
|
|
{
|
|
public :
|
|
~ShortestPath( void) override ;
|
|
bool AddPoint( double dX, double dY) override ;
|
|
bool AddPoint( double dXi, double dYi, double dXf, double dYf) override ;
|
|
bool AddPoint( double dXi, double dYi, double dZi, double dHi, double dVi,
|
|
double dXf, double dYf, double dZf, double dHf, double dVf) override ;
|
|
bool SetOpenBound( bool bStartVsEnd, int nFlag, double dX, double dY) override ;
|
|
bool SetOpenBound( bool bStartVsEnd, int nFlag, double dX, double dY, double dZ, double dH, double dV) override ;
|
|
bool SetAngularParams( double dAngHAdd, double dAngHMul, double dAngVAdd, double dAngVMul) override ;
|
|
bool SetZzOwStep( double dStep) override ;
|
|
bool Calculate( int nType) override ;
|
|
bool GetOrder( INTVECTOR& vOrder) override ;
|
|
bool GetMinLength( double& dMinLen) override ;
|
|
bool SetDistMatrix( const INTMATRIX& mDistMatrix) override ;
|
|
bool SetConstraintOrder( int nPrev, int nNext) override ;
|
|
bool SetSuggestedOrder( int nPrev, int nNext) override ;
|
|
|
|
public :
|
|
ShortestPath( void) ;
|
|
|
|
private :
|
|
bool Tsp( void) ;
|
|
bool CalculateImprovements( NODE* pPath) ;
|
|
void CalcDistances( void) ;
|
|
unsigned GetDistance( float dDx, float dDy, float dDz, float dDh, float dDv) ;
|
|
void PreparePath( NODE* pPath) ;
|
|
void SavePath( NODE* pPath) ;
|
|
void RestorePath( NODE* pPath) ;
|
|
void CopyPath( NODE* pPath, NODE* pPathCopy) ;
|
|
void CopyPathAdv( NODE* pPath, NODE* pPathCopy,
|
|
NODE* pLast, NODE* pFirst, NODE* pKth,
|
|
NODE** pLastCopy, NODE** pFirstCopy, NODE** pKthCopy) ;
|
|
long long unsigned TotalCost( NODE* pPath) ;
|
|
void UpdateOrder( NODE* pPath) ;
|
|
unsigned Index( unsigned i, unsigned j)
|
|
{ return ( i * m_nNumPnts + j) ; }
|
|
unsigned ArcCost( unsigned i, unsigned j)
|
|
{ return m_Dists[ Index( i, j)] ; }
|
|
long long unsigned NearNeighbor( void) ;
|
|
unsigned CheapArc( unsigned i) ;
|
|
long long unsigned FarNeighbor( void) ;
|
|
unsigned HighArc( unsigned i) ;
|
|
long long unsigned PointOpt( NODE* pPath) ;
|
|
long long unsigned TwoOpt( NODE* pPath) ;
|
|
long long unsigned Hybrid( NODE* pPath) ;
|
|
bool ZigZag( void) ;
|
|
long long unsigned TotalCost( void) ;
|
|
bool IsViolatingContraints( int nPrev, int nNext) ;
|
|
bool IsPathRespectingContraints( NODE* pPath) ;
|
|
bool IsChangingStartPathRespectingConstraints( NODE* pPath, NODE* pFirst) ;
|
|
bool IsPathRespectingSuggestedDependences( NODE* pPath, int& nBreak) ;
|
|
unsigned CalcMaxDist( void) ;
|
|
bool ExistConstraints( void)
|
|
{ return ! ( m_vOrderConstr.empty()) ; }
|
|
bool ExistSuggDependences( void)
|
|
{ return ! ( m_vOrderSugg.empty()) ; }
|
|
bool ChooseFirstNode( unsigned& iFirst) ;
|
|
bool ChooseNextNode( NODE* pPath, unsigned nSize, unsigned& j, bool bNearVsFar) ;
|
|
|
|
// _debug
|
|
void _printPath( NODE* pPath, std::string sFun) ;
|
|
|
|
|
|
private :
|
|
static const int MAX_SPPS = 32766 ; // 2^15-2 per evitare problemi nell'allocazione di m_Dists a 32bit
|
|
|
|
private :
|
|
int m_nType ;
|
|
bool m_bSolved ;
|
|
float m_dAngHAdd ;
|
|
float m_dAngHMul ;
|
|
float m_dAngVAdd ;
|
|
float m_dAngVMul ;
|
|
float m_dStep ;
|
|
unsigned m_nNumPnts ;
|
|
SpPoint m_Points[MAX_SPPS+1] ;
|
|
unsigned m_nOrder[MAX_SPPS+1] ;
|
|
OpenBound m_ObStart ;
|
|
OpenBound m_ObEnd ;
|
|
unsigned* m_Dists ;
|
|
bool* m_Available ;
|
|
NODE* m_pMain ;
|
|
NODE* m_pDupl ;
|
|
NODE* m_pCheckDep ;
|
|
long long unsigned m_nTotMin ;
|
|
long long unsigned m_nMinCost ;
|
|
INTINTVECTOR m_vOrderConstr ;
|
|
INTINTVECTOR m_vOrderSugg_tmp ;
|
|
|
|
BOOLVECTOR m_vOrderSugg ;
|
|
BOOLVECTOR m_vOrderSuggRowMap ;
|
|
|
|
unsigned m_nMaxDistSuggDep ;
|
|
INTMATRIX m_ExtDistMat ;
|
|
} ;
|