Witam, poszukuje algorytmu w C albo pseudokodzie na odnajdywanie Cyklu Hamiltona w grafie(chce go zastosować do problemu komiwojażera).
Obliczyłem sobie odległości między miastami na podstawie współrzędnych i sprawdziłem połączenia na podstawie macierzy sąsiedztwa, wszystko zapisałem do tablicy tablica_odleglosci[miastoA][miastoB].
Dobrze by było żeby algorytm nie wieszał się tak do granicy ok. 50 wierzchołków(miast).
Z góry możemy założyć, że każde miasto NIE jest połączone z każdym.
- Rejestracja:około 14 lat
- Ostatnio:około 9 lat
- Postów:88
0
rincewind
Problem cyklu Hamiltona jest silnie NP-zupełny, więc działa w czasie wykładniczym (O(|V|!)). Ale nie będzie się wieszał, po prostu dla 50 wierzchołków kilka dni/tygodni/whatever musiałbyś poczekać. :P
- Rejestracja:około 14 lat
- Ostatnio:około 9 lat
- Postów:88
0
czyli lepiej posiedzieć dłużej i rozwiązać problem komiwojażera za pomocą algorytmu mrówkowego?
- Rejestracja:około 14 lat
- Ostatnio:około 9 lat
- Postów:88
0
masz rację, na poniedziałek mam do napisania komiwojażera i jedyna opcja to wrzucić tam cykl Hamiltona z najmniejszą sumą wag(odległości), algorytm mrówkowy szczerze jest dla mnie za trudny do zrobienia... i szukam jakieś implementacji lub pseudokodu dla cyklu Hamiltona.
Nie mam już czasu na optymalizację itp.
Mógłby ktoś przepisać to na czyste C? Siedze już dłuższy czas i tylko coraz bardziej się denerwuje.....
#include <iostream>
#include <list>
using namespace std;
const int MAXV = 50; // maksymalna liczba wierzchołków
const int MAXINT = 2147483647; // maksymalna, dodatnia liczba całkowita
// Struktura krawędzi z wagą
struct edge
{
int v,d;
};
// Zmienne globalne
int n,m,d,dh; // liczba wierzchołków i krawędzi w grafie
list <edge> L[MAXV + 1];
list <int> q,qh;
bool visited[MAXV + 1];
// Rekurencyjna funkcja DFS wyszukująca cykl Hamiltona
// o minimalnej sumie wag krawędzi
void TSP(int v)
{
qh.push_back(v);
if(qh.size() == n)
{
for(list<edge>::iterator i = L[v].begin(); i != L[v].end(); i++)
if(i->v == 1)
{
dh += i->d;
if(dh < d)
{
d = dh;
q.assign(qh.begin(), qh.end());
q.push_back(1); // zamykamy cykl
}
dh -= i->d;
break;
}
}
else
{
visited[v] = true;
for(list<edge>::iterator i = L[v].begin(); i != L[v].end(); i++)
if(!visited[i->v])
{
dh += i->d;
TSP(i->v);
dh -= i->d;
}
visited[v] = false;
}
qh.pop_back();
}
main()
{
// Odczytujemy definicję grafu ze standardowego wejścia
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int v,w,dx; cin >> v >> w >> dx;
edge x;
x.v = w; x.d = dx; L[v].push_back(x);
x.v = v; L[w].push_back(x);
}
cout << endl;
// Rozpoczynamy wyszukiwanie cyklu Hamiltona
// o najmniejszej sumie wag krawędzi
for(int i = 1; i <= n; i++) visited[i] = false;
q.clear(); qh.clear();
d = MAXINT; dh = 0;
TSP(1);
// Wypisanie wyników
if(q.size())
{
cout << "CYKL HAMILTONA : ";
for(list<int>::iterator i = q.begin(); i != q.end(); i++)
cout << (* i) << " ";
cout << "\nSUMA WAG WYNOSI : " << d << endl;
}
else cout << "GRAF NIE POSIADA CYKLU HAMILTONA\n";
cout << endl;
system("PAUSE");
}
edytowany 2x, ostatnio: antoniaklja
- Rejestracja:około 14 lat
- Ostatnio:około 9 lat
- Postów:88
0
nie wyrobie się z czasem, mogę zacząć pisać w piątek i do poniedziałku musze skonczyć...