Napisałem program, dotyczący specyficznego problemu komiwojażera, właściwie wzorując się mocno na czymś co znalazłem w internecie jednak jest pewien problem, wszystko się kompiluje i kompilator nie wyrzuca żadnych błędów, a jednak program nie działa. "Strzeliłem go z palca", że tak powiem i tu tkwi właśnie szkopuł bo teraz nie mogę znaleźć powodu dla którego tenże się sypie. Jeśli ktoś znajdzie chwilkę czasu prosiłbym o rzucenie okiem na kod, który fakt, faktem jest mocno obszerny. Podejrzewam 3 funkcje, ale one wywołują coś jeszcze więc istnieje stosunkowo duże prawdopodobieństwo, że problem leży gdzieś indziej.
#include<iostream>
#include<cmath>
#include<algorithm>
#include<list>
#include<limits>
#include<vector>
#include<utility>
#include<ostream>
using namespace std;
double Min(double a, double b){
if(a > b) return b;
else return a;
}
class Point{
public:
double x;
double y;
Point(double x, double y): x(x),y(y){};
Point(): x(0),y(0){};
virtual ~Point(){};
virtual bool operator < (const Point& other) const{
return x <= other.x && (x != other.x || y < other.y);
};
virtual double Odleglosc(const Point& other) const{
return sqrt((x - other.x)*(x - other.x) + (y - other.y)*(y-other.y));
};
void Write(std::ostream& out) const{
out << x <<" "<<y;
};
friend std::ostream& operator << (std::ostream& out, const Point& p){
p.Write(out);
return out;
};
};
class BitonicTour{
public:
Point *points;
int size;
private:
double **distance;
vector<double> accumulated;
public:
virtual void Czytaj(std::istream& in){
in >> size;
if( !in ) return;
points = new Point[size];
for(int i = 0; i < size; i++){
in >> points[i].x >> points[i].y;
}
std::sort(points,points+size);
StworzDlugosci();
};
virtual void StworzDlugosci(){
double **distance = new double*[size];
for(int i=0; i < size; i++)
{
distance[i] = new double[size];
for(int j = 0; j < size; j++) distance[i][j] = points[i].Odleglosc(points[j]);
}
double temp = 0.0;
accumulated.reserve(size);
accumulated.push_back(temp);
for(int i = 1; i < size; i++) accumulated.push_back(temp += distance[i-1][i]);
};
virtual void Rand(int n){
size = n;
points = new Point[size];
for(int i = 0; i < size; i++){
points[i].x = i;
points[i].y = ::rand()%size;
}
StworzDlugosci();
};
virtual double Koszta(const list<int>& x) const{
double rezultat = 0.0;
list<int>::const_iterator i = x.begin();
list<int>::const_iterator j = i;
for( j++; j != x.end(); i++, j++) rezultat += distance[*i][*j];
return rezultat;
};
virtual const list<int>& NajbardziejWartosciowe(const list< list<int> >& x) const{
std::list< list<int> >::const_iterator rezultat;
double min = numeric_limits<double>::infinity();
for(std::list< list<int> >::const_iterator i = x.begin(); i != x.end(); i++){
double tmp = Koszta(*i);
if( min > tmp){
min = tmp;
rezultat = i;
}
}
return *rezultat;
};
template <class T>
list<int> RozwiazanieKombinatoryczne() const{
list<int> rezultat;
T c(*this);
c.Cmp();
if(!c.kombinacje.empty())
rezultat = NajbardziejWartosciowe(c.kombinacje);
return rezultat;
}
/***********************************************************************************/
public:
class Sciezki{
public:
const BitonicTour& t;
list< list<int> > kombinacje;
private:
std::vector<double> accumulated;
list<int> temp;
int licznik;
bool *odwiedzone;
public:
Sciezki(const BitonicTour& t): t(t) {};
virtual ~Sciezki(){};
virtual void Cmp(){
temp.clear();
kombinacje.clear();
odwiedzone = new bool[t.size];
for(int i = 0; i < t.size; i++) odwiedzone[i] = false;
licznik = 0;
Odwiedz(0);
};
void operator = (const Sciezki&){}
private:
virtual void Odwiedz(int x){
temp.push_back(x);
odwiedzone[x] = true;
licznik++;
if( licznik == t.size ){
temp.push_back(0);
kombinacje.push_back(temp);
temp.pop_back();
}
else{
for(int i = 1; i < t.size; i++)
if( !odwiedzone[i] ) Odwiedz(i);
}
licznik--;
odwiedzone[x] = false;
temp.pop_back();
};
};
public:
class Bitoniczny{
public:
const BitonicTour& t;
list< list<int> > kombinacje;
private:
int size;
list<int> temp;
bool *odwiedzone;
public:
Bitoniczny(const BitonicTour& t): t(t), size(t.size){};
virtual ~Bitoniczny(){};
virtual void Cmp(){
temp.clear();
kombinacje.clear();
odwiedzone = new bool[size];
for(int i = 0; i < size; i++) odwiedzone[i] = false;
Odwiedz(0);
};
void operator = (const Bitoniczny&){};
private:
virtual void Odwiedz(int x){
temp.push_back(x);
odwiedzone[x] = true;
if( x == size - 1 ){
for(int i = size - 1; i >= 0; i--){
if(!odwiedzone[i]) temp.push_back(i);
}
temp.push_back(0);
kombinacje.push_back(temp);
temp.pop_back();
for(int i = size-1; i >= 0; i--){
if(!odwiedzone[i]) temp.pop_back();
}
}
else{
for(int i = x + 1; i < size; i++){
if(!odwiedzone[i]) Odwiedz(i);
}
odwiedzone[x] = false;
temp.pop_back();
}
};
};
virtual double Penalty(int x, int y)const {
return distance[x-2][y-1]
+ accumulated[y-1] - accumulated[x-1]
- distance[x-2][x-1];
};
virtual double KosztPodstawowy(int x) const{
double rezultat = distance[0][x-1];
for(int i = 1; i < x; i++) rezultat += distance[i-1][i];
return rezultat;
};
virtual double Optymalne(int x) const{
double result = KosztPodstawowy(x);
for (int i = 3; i < x; i++)
result = Min(result, Optymalne(i) + Penalty(i, x));
return result;
};
virtual void Dodaj(list<int>& s, int x, int y) const{
if( y - 1 == s.back() ){
s.push_back(x-2);
while(s.front() > x - 1) s.push_front(s.front() - 1);
}
else{
s.push_front(x-2);
while(s.back() > x - 1) s.push_back(s.back() - 1);
}
};
virtual list<int> Rozwiazanie(int x) const{
list<int> rezultat;
rezultat.clear();
rezultat.push_back(x-1);
while(x > 3){
int i = x - 1;
while( i >= 3 && Optymalne(x) != Optymalne(i--) + Penalty(i,x)) i--;
Dodaj(rezultat,i,x);
x = i;
}
Skoncz(rezultat);
return rezultat;
};
virtual void Skoncz(list<int>& s) const{
if(s.back() != 0) s.push_back(0);
if(s.front() != 0) s.push_front(0);
list<int>::const_iterator x = s.begin();
x++;
if( *x != 1 ) reverse(s.begin(),s.end());
};
};
template<class T>
class DynamiczneSpamietywanie: public T{
public:
mutable vector<double> optimal;
double granica;
DynamiczneSpamietywanie(): optimal(), granica(-1.0){};
virtual double Otymalne(int x) const{
if( x >= static_cast<int>(optimal.size())) optimal.resize(x+1,granica);
if( optimal[x] == granica) optimal[x] = T::Optymalne(x);
return optimal[x];
};
};
void Test(){
DynamiczneSpamietywanie<BitonicTour> t;
int size = 8;
t.Rand(size);
for(int i = 0; i < size; i++) cout<<t.points[i].x<<" "<<t.points[i].y<<endl;
std::list<int> solution1 = t.RozwiazanieKombinatoryczne<BitonicTour::Sciezki>();
cout << t.Koszta(solution1) << "/";
while(!solution1.empty())
{
cout << solution1.front() << std::endl;
solution1.pop_front();
}
std::list<int> solution2 = t.RozwiazanieKombinatoryczne<BitonicTour::Bitoniczny>();
cout << t.Koszta(solution2) << "/";
while(!solution2.empty())
{
cout << solution2.front() << std::endl;
solution2.pop_front();
}
std::list<int> solution = t.Rozwiazanie(size);
cout << t.Koszta(solution) << "/";
while(!solution.empty())
{
cout << solution.front() << std::endl;
solution.pop_front();
}
cout << t.Optymalne(size) << std::endl;
}
int main()
{
Test();
system("pause");
}
Z góry dzięki za jakąkolwiek odpowiedź...