Witam,
muszę napisać program który weryfikuje czy inny program poprawnie obliczył odległość problemu komiwojażera. Program sprowadza się do tego iż wczytujemy współrzędne wierzchołków i koszt przebycia cyklu i sprawdzamy czy zachodzi: wczytanyKoszt<= mojKoszt <= wczytanyKoszt*2 . Stosujemy metrykę taksówkarską wzór: abs((A.x-A.x)) + abs((B.y-b.y)).
Muszę zastosować procedurę "APPROX-TSP-TOUR". Problem polega na tym iż napisałem ten algorytm ale dla jednego przypadku jest on za wolny. Zakładam że ten graf jest grafem pełnym. Według debuggera 95% CPU używa dodawanie krawędzi do kolejki priorytetowej
pq.push(Edge(macierz_vector.at(i), next, i));
. Proszę was o porady i z góry dziękuję za każdą uwagę czy też podpowiedź.
"APPROX-TSP-TOUR(G,c)//c[u,v] oznacza koszt przebycia krawędzi uv
- Za pomocą algorytmu Prima, wyznacz minimalne drzewo rozpinające T dla grafu
G, o dowolnie wybranym korzeniu r z G, przy koszcie c. - Przejdź przez T w kolejności preorder i wynik zapisz do listy L.
- Na podstawie listy L, zbuduj cykl Hamiltona H, odwiedzając kolejne elementy
listy. - Cykl H jest poszukiwanym wynikiem."
Kod w c++:
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#define LL long long
using namespace std;
LL i, wynikKupionego;
class Edge {
public:
Edge(int w, int v1, int v2) : weight(w), vertex1(v1), vertex2(v2) {};
bool operator > (const Edge& rhs) const
{
return weight > rhs.weight;
};
LL weight;
LL vertex1; // in tree
LL vertex2; // not in tree
};
struct Point
{
LL x, y;
Point(LL x, LL y): x(x),y(y){}
LL odleglosc(Point p) const
{
return abs(x - p.x) + abs(y - p.y);
}
};
vector<vector<LL> > macierz;
priority_queue<Edge, vector<Edge>, greater<Edge> > pq;
priority_queue<Edge, vector<Edge>, greater<Edge> > pq_Clear;
vector<Point> punkty;
inline LL prim(LL start)
{
vector<bool> odwiedzone(macierz.size(), false);
odwiedzone.at(start) = true;
for (i = 0; i < macierz.at(start).size();i++)
{
if (macierz.at(start).at(i)>0) pq.push(Edge(macierz.at(start).at(i),start,i));
}
const Edge *aktualny;
LL next;
LL wynik = 0, licznikSprawdzonychPunktow=0;
while(!pq.empty())
{
aktualny = &pq.top();
next = aktualny->vertex2;
pq.pop();
if(!odwiedzone[next])
{
odwiedzone.at(next) = true;
// printf_s("%lld\n", licznikSprawdzonychPunktow);
if (++licznikSprawdzonychPunktow == macierz.size()-1) {
wynik+=macierz.at(0).at(aktualny->vertex1) + aktualny->weight;
return wynik;
}
wynik += aktualny->weight;
if (wynik > wynikKupionego * 2) return -1;
LL macierzsize = macierz.size();
vector<LL> macierz_vector = macierz.at(next);
for (i = macierzsize; i--;)
{
if (!odwiedzone.at(i) &&macierz_vector.at(i)>0 )
pq.push(Edge(macierz_vector.at(i), next, i));
}
}
}
return wynik;
}
int main()
{
LL iloscSerii, iloscPunktow, tmpx, tmpy, odleglosc, matka = 0,wynik;
scanf("%lld", &iloscSerii);
while (iloscSerii--)
{
scanf("%lld", &iloscPunktow);
macierz.resize(iloscPunktow);
for (i = 0; i < iloscPunktow; i++) {
macierz.at(i).resize(iloscPunktow);
}
while (iloscPunktow--)
{
scanf("%lld %lld", &tmpx, &tmpy);
punkty.push_back(Point(tmpx, tmpy));
for (i = 0; i < punkty.size() ; i++)
{
if (i == matka) odleglosc=0;
else odleglosc = punkty.back().odleglosc(punkty.at(i));
macierz.at(matka).at(i) = odleglosc;
macierz.at(i).at(matka) = odleglosc;
}
matka++;
}
matka = 0;
punkty.clear();
scanf("%lld", &wynikKupionego);
wynik = prim(0);
if (wynik >= wynikKupionego && (wynikKupionego * 2) >= wynik) printf("ok\n");
else printf("bambuko\n");
// printf_s("\nwynik: %lld", wynik);
//Clear
pq = pq_Clear;
macierz.clear();
}
}
C++ 
