Cykl Hamiltona

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.

czyli lepiej posiedzieć dłużej i rozwiązać problem komiwojażera za pomocą algorytmu mrówkowego?

Przy tej ilości jedynym sensownym rozwiązaniem wydaje się jakiś algorytm przybliżony. Dla 50 wierzchołków będzie przecież miał 0.5 * 49! Także normalnie tego nie policzysz w "optymalnym czasie".

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");
} 

To zrób genetyka. Jest znacznie łatwiejszy niż mrówkowy.

nie wyrobie się z czasem, mogę zacząć pisać w piątek i do poniedziałku musze skonczyć...