algorytm komiwojażera brute foce

Odpowiedz Nowy wątek
2014-02-28 22:19
0

Cześć!
Od razu zacznę, że widziałem iż takich podobnych wątków jest sporo, ale wydaje mi się, że ten jest trochę inny, tzn mam problem z jedną rzeczą. Mianowicie, jak znaleźć we w miarę szybki sposób wyszukujący wszystkie połączenia w grafie tak, żeby się nie powtarzały. Wyczytałem że takich kombinacji będzie (n-1)!, ale połowa z tego nie będzie niczego nowego wnosiła jeśli chodzi o problem komiwojażera. Znalazłem przykład na którym się wzorowałem http://www.people.vcu.edu/~gasmerom/MAT131/brutefrc.html i po dłuższym czasie główkowania udało mi się napisać coś takiego co przedstawie w pseudokodzie:

char tab[n]
for (int i = 0; i < n; i++) {
    for (int j = n-1; j > 0; j--) {
        swap(tab[j], tab[j - 1]);
    }
}

Po prostu n razy przechodzę tablicę od końca zmieniając miejscami kolejno jej elementy.
Czy jest ktoś w stanie określić czy takie generowanie połączeń będzie zawsze poprawne i sprawdzę dzięki temu wszystkie możliwości? Sprawdzałem z tym co jest na wyżej wymienionej stronie, niby się zgadza tylko w innej kolejności. Wiem, że tam na stronie pierwszy element oznaczony jako "A" jest pierwszym i ostatnim i on się nie zmienia, ale to już dodam sobie na końcu;)

edytowany 2x, ostatnio: porschelukas, 2014-02-28 22:21

Pozostało 580 znaków

2014-02-28 22:36
0

Nie bardzo rozumiem.

  1. Faktycznie tylko połowa połączeń jest potrzebna ale tylko jeśli to graf nieskierowany. Dla skierowanego nie jest to prawdą.
  2. Chcesz wygenerować sobie graf pełny? A na jakiej reprezentacji grafu bazujesz? Macierz VxV czy VxE? Dla VxV po prostu wypełniasz całą macierz (lub macierz trójkątną górną/dolną jeśli masz graf nieskierowany) a jeśli masz macierz VxE to wypełniasz sobie ją po kolei w dwóch pętlach ;]

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2014-02-28 22:52
0

Dotyczy to grafu nieskierowanego. Mam macierz VxV, ale mając taką macierz muszę jakoś wygenerować listę połączeń które będę sprawdzał i robiłem to właśnie takim sposobem jak we wcześniejszym poście

Pozostało 580 znaków

2014-02-28 22:56
0

To ja tym bardziej nie rozumiem twojego pytania. Jak masz macierz VxV to jeśli ta macierz jest wypełniona w całości powyżej albo poniżej przekątnej to musi zawierać wszystkie możliwości połączeń wierzchołków. Gdzie tu jest problem? Nie ogarniam co ty tutaj "zamieniasz" miejscami.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2014-02-28 23:05
0

No tak, ale mając taką macierz, muszę jakimś schematem wybierać połączenia które chcę sprawdzać. Tak, aby nie pominąć żadnego i też niepotrzebnie nie robić ich zbyt dużo. Tą macierz muszę jakoś wykorzystać, albo hmmm... sam nie wiem może coś przekombinowałem

Pozostało 580 znaków

2014-02-28 23:13

Chodzi ci o to jak wybierać kolejne ścieżki w grafie? Ja bym leciał DFSem ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2014-02-28 23:22
0

O wreszcie o tym samym rozmawiamy;] Faktycznie można też DFSem, ale to chyba nie wyjdzie szybciej niż wygenerowanie takich połączeń o których wspominałem w pierwszym poście:)

Pozostało 580 znaków

2014-02-28 23:31
1

W listę cykliczną złączasz 3 dowolne węzły.
W pętle wstawiasz kolejny węzeł w 3 możliwe do tego miejsca.
W pętle wstawiasz kolejny węzeł w 4 możliwe do tego miejsca.
W pętle wstawiasz kolejny węzeł w 5 możliwych do tego miejsca.
...
W pętle wstawiasz ostatni węzeł w N-1 możliwych do tego miejsca.
Całość da się zrobić rekurencyjnie.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2014-02-28 23:33

Pozostało 580 znaków

2014-03-01 07:43
0
_13th_Dragon napisał(a):

W listę cykliczną złączasz 3 dowolne węzły.
W pętle wstawiasz kolejny węzeł w 3 możliwe do tego miejsca.
W pętle wstawiasz kolejny węzeł w 4 możliwe do tego miejsca.
W pętle wstawiasz kolejny węzeł w 5 możliwych do tego miejsca.
...
W pętle wstawiasz ostatni węzeł w N-1 możliwych do tego miejsca.
Całość da się zrobić rekurencyjnie.

Czy mógłbyś jaśniej?:) bo nie rozumiem

//lista cykliczna z trzema węzłami np
A -> B -> C -> A

//"W pętle wstawiasz kolejny węzeł w 3 możliwe do tego miejsca."
//tutaj nie rozumiem, tworzę coś takiego?
A->D->B->D->C->D->A

Pozostało 580 znaków

2014-03-02 01:57
0
  1. A->D->B->C->A
  2. A->B->D->C->A
  3. A->B->C->D->A

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-03-02 21:15
0

A faktycznie da się też w ten sposób:) ale już się pospieszyłem i zrobiłem to przechodzeniem DFS.
Dzięki wszystkim za pomoc

edytowany 1x, ostatnio: porschelukas, 2014-03-02 21:16

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0