Graf - hamiltona

0

Siemanko,

Mam do was pytanie, czy ktoś miał styczność z grafem hamiltona tzn droga od do

Mamy podane kilka wierzchołków np. i ułożyć z tego drogę a-b-c-d lub w druga zrobiłem to na forach jednak potrzebne zrobić to metoda grafu,
[a - b]
[c-d]
[c-b]
Dotrałem do tego:
http://eduinf.waw.pl/inf/alg/001_search/0136.php
https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/
Czy ktoś jest to w stanie wytlumaczyć mi na jave/c#?
https://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/
Najlepiej jakos z gotowymi elementami, teorie rozumiem ale nie wiem jak to przełożyc na kod :(

Z góry dzięki

1

Przeciez w podanym przez ciebie ostatnim linku masz kod w Javie. Poza tym obawiam się że twój problem jest znacznie większy niż przełożenie tego na jakiś język programowania, skoro piszesz grafem hamiltona tzn droga od do, bo sensu w tym zupełnie nie ma. Tak samo zdanie Mamy podane kilka wierzchołków np. i ułożyć z tego drogę a-b-c-d lub w druga jest totalnie bez sensu i nijak się ma do problemu ścieżki/cyklu Hamiltona w grafie.

Ścieżka Hamiltona w grafie to jest uporządkowana lista wierzchołków, która pozwala odwiedzić wszystkie wierzchołki grafu, przechodząc po istniejących krawędziach, w taki sposób że żaden wierzchołek nie jest odwiedzony więcej niż raz. Cykl Hamiltona to ścieżka, dla której istnieje krawędź łącząca ostatni wierzchołek ścieżki z wierzchołkiem początkowym.

To jest nietrywialny problem, bo już samo stwierdzenie czy graf w ogóle posiada taką ścieżkę jest problemem NP-zupełnym. Nie ma do tego żadnego prostego ani szybkiego algorytmu i generalnie możesz to zrobić wykładniczym algorytmem, np. tak jak sugerują w tych twoich linkach -> DFSem z powrotami. Czyli w wielkim skrócie:

  1. Wybierz wierzchołek początkowu
  2. Jeśli z aktuanego wierzchołka da się przejść do wierzchołka którego jeszcze nie odwiedziliśmy to idziemy tam i oznaczamy ten wierzchołek jako odwiedzony
  3. Jeśli z danego wierzchołka nie możemy już dalej przejść, a nie odwiedziliśmy jeszcze wszystkich wierzchołków, to cofamy się o 1 krok, oznaczamy wierzchołek z którego sie wycofaliśmy jako "nieodwiedzony"

Powtarzamy to aż nie znajdziemy ;]

0

@Shalom:
Wiem, próbuje z niego przejść na to co chce czyli z wierzchołków tablicy bool (tylko tam to połączenie jest kilkukrotne ) na string i tutaj tylko dwukrotnie występuje w danym węźle.
Pisałem skóry myślowe o co mi chodzi, zakładam ze jak ktoś będzie na siłach pomóc to wie o co chodzi :)
No ok tylko trzeba najpierw wybrać wierzchołek początkowy i co mam to robić metodą 2x for?
Kurde własnie te kroki znam i kumam o co chodzi, tylko jakoś nie mogę z tym przejść na kod i zrobić to elegancko. Po prostu blok

0

Wiem, próbuje z niego przejść na to co chce czyli z wierzchołków tablicy bool (tylko tam to połączenie jest kilkukrotne ) na string i tutaj tylko dwukrotnie występuje w danym węźle.

Nie rozumiem o co ci chodzi. Chcesz zamienić macierz incydencji (VxV) na listę sąsiedztwa (V -> v1,v2,v3...)? Gdzie tu widzisz problem?

No ok tylko trzeba najpierw wybrać wierzchołek początkowy i co mam to robić metodą 2x for?

Nie wiem po co 2 pętle. Masz N wierzchołków, w pętli możesz sobie testować każdy z nich po kolei po prostu.

0

@Shalom: dobra wstałem i rozumiem bardziej idee, zastosuje sie dzis do wskazówek i dam znac :p

0

@Shalom: da sie to zrobic bez rekurencji?

Zakładam na początek tak
v=3
że graf to String graph [][] = { { "KA" , "WA"},
{ "DW", "MW"},
{"DW",WA"}};
I teraz idąc pojdesciem ze biore pierwszy z brzegu i sprawdzam czy moge z niego ułożyć scieszke to dość nie optymalne bo jeżeli taki element byłby ostatni to sprawdzimy wszystkie możliwości czyli prawie n^2.

Teraz jak znaleźć pierwszy? Tutaj pojawia się problem bo nie wiem jak to zrobic zeby to nie bylo kilka petli.
connection=0
for (i=0 , i<v, i++)

for(j=0, i<v,i++)

 if(graph[i,0]==graph[j,0] || graph[i,1]=graph[j,1] || graph[i,0]==graph[j,1] graph[i,1]=graph[j,0])

i liczenie liczby połaczen.. ale to mi sie wydaje bez sensu, ktos cos?\

I tu jeszcze pytanie bo może nie upatruje własciwego rozwiązania czy scieżka hamiltona dotyczy tylko:

      (0)--(1)--(2)
        |   / \   |
        |  /   \  |
        | /     \ |
       (3)-------(4)    

a ja chce np to:
(0) (1)--(2)
| |
\
| |
(3)-------(4)

Kurde nie moge tego edytować poprawnie chodzi mi o pojedyncza sciezke np 0-3-4-1-2

0
  1. ścieżka
  2. Taka reprezetancja grafu est zupełnie bez sensu i tylko utrudni ci życie. Użyj jakiejś NORMALNEJ reprezetancji, czyli macierzy VxV, macierzy VxE albo listy V->v1,v2,v3...
  3. Widzę że nie dość że nie umiesz algorytmów, to nie umiesz też matematyki na poziomie podstawówki. Wszystkich możliwości przejścia jest ZNACZNIE więcej niż n^2. Podpowiem że jest ich wykładniczo dużo...
  4. Nie rozumiem gdzie jest jakiś problem ze znalezieniem pierwszego wierzchołka. Bierzesz losowy, szukasz rozwiązania, jeśli nie znalazłeś to bierzesz kolejny i odpalasz wszystko od nowa.
  5. Tego ifa z orami nie będę komentował. Uznam ze chciałeś sobie zażartować.
  6. Nie rozumiem pytania. Napisałem już wyżej co to jest ścieżka Hamiltona.

da sie to zrobic bez rekurencji?

Koncepcyjnie? Nie. Można to zaklepać bez rekurencji, posiłkując się jakąś kolejką/stosem jeśli bardzo chcesz.

0

Może takie komentarze to sobie daruj kolego, bo to że ktoś czego nie wie to nie znaczy ze jest głupi, myślę ze wiem wielu rzeczy których inni nie wiedzą a się nigdy nie wywyższam... Ja wiem ze jak sie cos umie albo wie to jest to łatwe, z matematyka nie mam problemów i bardzo dobrze radziłem sobię z mata i fizą na studiach technicznych wiec odpuść sobie takie komenatrze, a to że nie do końca wiem jak zaklepać takie coś w programie to nie wiem co to ma wspólnego.

  1. tylko dla macierzy VxV to dla miliona miast macierz milion na milion którą najpierw bym musiał wypełnic czyli posprawdzac de facto połaczenia między miastami zeby uzupełnic sama macierz a to kupa obliczeń bo musze sprawdzic kazdy z kazdym.
    VxE - E jest tutaj ogolna liczba krawedzi czyli V-1 czy krawędzi np w sensie pomiędzy elemntami?
  2. Czyli nie da sie tego zrobic w zaloznosci mniejszej n^2?
  3. No wiem jednak chciałem się dowiedzieć czy mozna unikąc takiego scenariuszu bo to znowu dla każdego elementu (zakladając ze element dla którego możęmy ułożyć scieżkę jest ostatni) to wykonujemy prawie wszystko * wszystko
  4. Paradoksalnie można tak znaleźć pierwszy element :> bo one maja po jednym wspolnym połaczeniu a pozostałe po dwa :)
  5. Wiem własnie chciałem to wykreslić nvm
0

z matematyka nie mam problemów

Dowody temu przeczą.

  1. Dla miliona miast? :D I znów wracamy do problemów z matematyką. Naiwny algorytm to jest O(n!) i już dla 20 wierzchołków tego nie policzysz. State of the art dynamiczny algorytm to O(n^2 * 2^n) i generalnie też już dla kilkudziesięciu wierzchołków możesz zapomnieć o wyliczeniu tego.
  2. Jak ci sie uda, to znaczy że rozwiazałeś w czasie wielomianowym (i to ekstremalnie niskim!) problem NP zupełny. Możesz iść odebrać nagrodę Turinga.
  3. Zapewniam cię, że ten dodatkowy czynnik n na szukanie początkowego wierzchołka jest tutaj zupełnie nieistonym szczegółem, biorąc pod uwagę złożoność problemu.
  4. No chyba tylko w tym twoim banalnym przykładzie, do którego nie trzeba żadnych algorytmów bo można go rozwiazać na kartce...

Mówimy tu o problemach o złożoności n! i 2^n. Skoro byłeś taki dobry z matematyki to weź do ręki kartkę i policz ile to jest n! dla 20 czy 30...

0

Dobra, nie sprawdziłem na początku złożoności racja Hamiltona nie zrobi się niżej to może inaczej
Czy taki prosty przypadek czyli mamy połączenia pary miast Krakow-Poznan, Szczecin-Warszawa, Poznan-Szczecin i wiecej i chce z tego zrobic trase w jedna lub w druga
można w jakis inny prosty sposób zrobic?

0

@yarel: no coś takiego tylko moja ścieżka musi przebiegać od początku do końca bazując na połączeniach, czyli chce wykorzystać wszystkie wierzchołki nie znając początkowego.
@Shalom juz sobie sprawdziłem złożność, moj bład wynikał z tego ktos powiedział że da sie to zrobic mniej niż n^2 i też zaznaczam że nie do końca skupiłem się na tym grafie Hamiltona (dałem tylko przykład) tylko na ogólnym zarysie mojego problemu i czy można ten przypadek zrobić prościej, może inny algorytm. Jeżeli nie to ok

0
CryArturek napisał(a):

@yarel: no coś takiego tylko moja ścieżka musi przebiegać od początku do końca bazując na połączeniach, czyli chce wykorzystać wszystkie wierzchołki nie znając początkowego.

To jak może przebiegać od początku do końca, skoro nie znasz początku? :| Mam wrażenie, że masz problem z wyrażeniem tego co chcesz osiągnąć.

0

@yarel:
Początek muszę znaleźć - początkiem jest miasto które występuje raz.
Czyli masz powiedzmy połaczenia PKP Lodz-Warszawa, , Krako-Gdynia, Gdynia-Wrocław , Warszawa - Krakow (to tylko przykład bez orientacji geograficznej) i teraz masz z tego ułożyc trase PKP od do na podstawie połączeń wszystkich połączeń czyli Lodz-Warszawa-Krakow-Gdynia-Wrocław lub Wroclaw-Gdynia-Krakow-Warszawa-Lodz

0

@CryArturek no dobra ale jakie są założenia? Musisz koniecznie odwiedzić każde miasto? Każde można odwiedzić tylko raz? Jeszcze nam zaraz powiesz ze w sumie to szukasz jeszcze takiej ścieżki żeby waga (np. czas przejazdu albo koszt) był minimalny i nagle zrobi się z tego TSP/problem Komiwojażera...
Napisz jasno co masz dane, co chcesz osiągnąć i jakie są założenia/ograniczenia.

0

@Shalom:
Wczoraj już o tym czytałem ale ten problem nie jest aż tak skomplikowany.
Dane mam w pliku tekstowym zapisane jako połączenie dwóch miast rozdzielone -
Czyli tak jak pisałem:
Lodz-Warszawa
Krako-Gdynia,
Gdynia-Wrocław
Krakow - Warszawa

I dla takiej nieuporzadkowanej listy połączeń mam utworzyć możliwa podróż w dowolnym kierunku
czyli tak jak pisalem Lodz-Warszawa-Krakow-Gdynia-Wrocław lub Wroclaw-Gdynia-Krakow-Warszawa-Lodz
Polaczenie Lodz-Warszawa nie mowi czy to z Lodzi do Warszawy czy z Warszawy do Lodzi

Czyli tak jakbyś miał nieuporządkowane połaczenia miast i zrobic z tego trase PKP zawierające wszystkie miasta w jedna strone lub w druga obojetne.

0

Wczoraj już o tym czytałem ale ten problem nie jest aż tak skomplikowany.

Jest.
Nie jest skomplikowany tylko jak masz 4 czy 5 miast na krzyż i prawie żadnych krawędzi pomiędzy nimi.

0

@Shalom: no chodzi mi o ten przypadek jak tu z jedna krawędzią pomiędzy miastami, masz pomysł jak to zrobić? Można to zrobic inaczej czy muszę z Hamiltiona korzystać?

0

Dla takiego przykładu jaki masz nie musisz żadnego skomplikowanego algorytmu stosować. Ot malujesz to sobie na kartce i rysujesz rozwiązanie...

0

@Shalom: dzięki wielkie, rozwiązane -_-
a tak serio?

0

Nikt nie wie?

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