Za wolny algorytm komiwojażera.

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

1. Za pomocą algorytmu Prima, wyznacz minimalne drzewo rozpinające T dla grafu
   G, o dowolnie wybranym korzeniu r z G, przy koszcie c.
2. Przejdź przez T w kolejności preorder i wynik zapisz do listy L.
3. Na podstawie listy L, zbuduj cykl Hamiltona H, odwiedzając kolejne elementy
   listy.
4. 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();
	}
}

Wygeneruj sobie taki pesymistyczny przypadek testowy a następnie odpal swój kod z profilerem (np. gprof) i zobacz co ci zjadło najwięcej czasu.

Zobacz czy użycie deque zamiast vector jako podstawy priority_queue coś pomoże. W przeciwnym przypadku zastanowiłbym się nad użyciem std::set

Po zastosowaniu "deque" i przypadku z 250 punktami (ze współrzędnymi około 100 000 000) okazuje się że dodawanie do kolejki priorytetowej zajmuje najwięcej czasu. Rano zobaczę jak sprawdzarka zareagowała na tą zmianę. Zastosuje jeszcze "std::set" i będę próbował jakoś ogarnąć tą kolejkę. Dzięki za odpowiedź :)

Udało się :D Zamiast

vector<bool> odwiedzone(macierz.size(), false);

Użyłem wskaźników bool *odwiedzone2= new bool[macierz.size()];
for (i = 0; i < macierz.size(); i++) odwiedzone2[i] = false;

 a później je usuwałem. Dzięki wielkie za pomoc. :) taka mała zmiana a tyle daje. W załączniku kod.

PS Ten mój kod w pierwszym poście był błędny ze względu na to że wskaźnikowi przypisywałem adres elementu kolejki a następnie usuwałem ten element z kolejki. Czyli wskaźnik finalnie pokazywał na następny element.

Zamiast vector<bool> użyj vector<uint8_t>, a nie tych herezji.

@snowroot Zapodasz linka do sprawdzaczki/testów?

Kolega z zapomniał dodać, że na wejściu dostaje się graf zupełny (ale da się wywnioskować z kodu).
Przeglądanie nieodwiedzonych sąsiadów jest nieoptymalne - wyjdzie O(NN), a można zjechać do O(Nlog(N))