Witam, muszę znaleźć cykl w grafie o największej ilości krawędzi (m.in. taki) używając algorytmu genetycznego. Mam to zrobione klasycznie ale wiadomo, przy większej ilości krawędzi i wierzchołków komputer będzie to mielił w nieskończoność. Dlatego chcę zaprząc algorytm genetyczny, który niekoniecznie musi dawać najlepszy wynik, ma dać wynik zbliżony. Mniej więcej wiem jak działają takie algorytmy ale mam problem z implementacją i nazwaniem co jest czym (co jest populacją, co chromosomem itd.) i implementacją.

Mam parę pomysłów ale potrzebują weryfikacji. Pomysł:

  1. Tworzę graf.
  2. Wybieram liczebność populacji np. 20 (ilosc cykli)
  3. Losowo wybieram wierzchołki i szukam DFSem jakiegoś cyklu, jak go znajdę to zapisuję do tablicy z cyklami.
  4. Sprawdzam czy te cykle mają jakąś wspólną (jedną)krawędź ze sobą. Łącze je w większe cykle (operacja krzyżowania), tablica się zmniejsza. Zostawiam "ileś" (to ileś to np. ten jeden najdłuższy) najlepszych cykli, resztę odrzucam.
  5. Ponownie losuję cykle żeby dopełnić tablicę do 20 i ponownie krzyżuję (jeśli się nie da krzyżować to usuwam tablicę i ponownie szukam cykli)
  6. I tak do pewnego momentu.
    Nie wiem czy dobrze chcę robić, trochę mi tu ten DFS się nie podoba bo zajeżdża klasycznym podejściem do problemu. Może macie lepsze pomysły? Stawiam piwo.

Pzdr