Wszystkie cykle hamiltona
Piotr
Czy istnieje jakieś twierdzenie, które na podstawie macierzy incydencji
potrafi określić ile jest _wszystkich_ cykli hamiltona w grafie?
Zaimplementowałem algorytm genetyczny z mutacją, który to bardzo
sprawnie szuka cykli hamiltona, lecz niestety nie potrafię określić, czy
znalazł je wszystkie.
Z góry dziękuję za pomoc.
--
Piotr Piwko
http://piotr.piwko.googlepages.com/
Jakub Wróblewski
Użytkownik "Piotr" <piotr...@gmail.com> napisał w wiadomości
news:ffv3tq$g4l$1...@inews.gazeta.pl...
>
> Czy istnieje jakieś twierdzenie, które na podstawie macierzy incydencji
> potrafi określić ile jest _wszystkich_ cykli hamiltona w grafie?
Gdyby bylo znane, problem istnienia cykli Hamiltona nie bylby NP-zupelny.
Wylicz wszystkie na boku i sprawdz.
Pozdrawiam,
Jakub Wroblewski
Piotr
> Gdyby bylo znane, problem istnienia cykli Hamiltona nie bylby NP-zupelny.
Może istnieje na to jakiś dowód? Zadowalające jest dla mnie zarówno
twierdzenie na ilość cykli, a jak nie to, dowód na to, że jest to
niemożliwe.
> Wylicz wszystkie na boku i sprawdz.
Niestety, ilość danych przerasta moją moc obliczeniową :)
Dziękuję za zainteresowanie.
Jakub Wroblewski
> > Gdyby bylo znane, problem istnienia cykli Hamiltona nie bylby NP-zupelny.
>
> Może istnieje na to jakiś dowód? Zadowalające jest dla mnie zarówno
> twierdzenie na ilość cykli, a jak nie to, dowód na to, że jest to
> niemożliwe.
Alez jest mozliwe - wystarczy policzyc po kolei.
Nie jest tylko znany sposob na policzenie tego w czasie wielomianowym. Nie jest
tez znany dowod na to, ze to niemozliwe. Gdybys znalazl jeden z tych dowodow,
daj znac.
Tu jest cos na temat:
http://www.lfcs.inf.ed.ac.uk/reports/93/ECS-LFCS-93-259/
> > Wylicz wszystkie na boku i sprawdz.
>
> Niestety, ilość danych przerasta moją moc obliczeniową :)
A ile masz wierzcholkow i jak gesty graf?
Pozdrawiam,
Jakub Wroblewski
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
Piotr
>> Może istnieje na to jakiś dowód?
> Alez jest mozliwe - wystarczy policzyc po kolei.
Niestety, mam za dużo danych, aby zastosować przegląd zupełny.
> Nie jest tylko znany sposob na policzenie tego w czasie wielomianowym.
W internecie natrafiłem na coś co się nazywa "Metoda kompozycji
łacińskiej", która to ponoć znajduje _wszystkie_ cykle. Niestety owa
metoda jest opisana dość lakonicznie i mało przejrzyście. Opis znajduje
się na Wikipedii, toteż podchodzę do tego z rezerwą. Oto link:
http://tnij.org/ae4w . Praktycznie jest to jedyny dokument traktujący na
ten temat, jaki udało mi się znaleźć.
> A ile masz wierzcholkow i jak gesty graf?
Graf liczy 20 wierzchołków, z których średnio wychodzi 10-12 gałęzi.
Musi być ta no jakiś patent! Albo na określenie liczby cykli hamiltona,
albo dowód na brak możliwości dokonania tego w rozsądnym czasie.
Dziękuję za poświęcony czas.
A.L.
wrote:
>
>Musi być ta no jakiś patent! Albo na określenie liczby cykli hamiltona,
>albo dowód na brak możliwości dokonania tego w rozsądnym czasie.
Jest patent. Patent mowi ze liczby cykli nie da sie okreslic "w
rozsadnym czasie".
A.L.
jtg
> Jakub Wroblewski pisze:
>
>>> Może istnieje na to jakiś dowód?
>> Alez jest mozliwe - wystarczy policzyc po kolei.
>
> Niestety, mam za dużo danych, aby zastosować przegląd zupełny.
>
>> Nie jest tylko znany sposob na policzenie tego w czasie wielomianowym.
>
> W internecie natrafiłem na coś co się nazywa "Metoda kompozycji
> łacińskiej", która to ponoć znajduje _wszystkie_ cykle. Niestety owa
> metoda jest opisana dość lakonicznie i mało przejrzyście. Opis znajduje
> się na Wikipedii, toteż podchodzę do tego z rezerwą. Oto link:
> http://tnij.org/ae4w . Praktycznie jest to jedyny dokument traktujący na
> ten temat, jaki udało mi się znaleźć.
>
>> A ile masz wierzcholkow i jak gesty graf?
>
> Graf liczy 20 wierzchołków, z których średnio wychodzi 10-12 gałęzi.
>
Jak taki mały, to na dzisiejszym sprzęcie można to policzyć metodą
programowania dynamicznego.
(Oczywiście mogę się mylić zgodnie z zasadą: "For every complex problem,
there is at least one solution that is simple, easy to explain, and
completely wrong.") :-)
Tworzysz tablicę
tab[2^20][20]
gdzie pierwszy indeks jest maską bitową odwiedzonych wierzchołków, a
druga ostatnim odwiedzonym wierzchołkiem. Każdy element tab[maska][i]
oznacza liczbę ścieżek Hamiltona rozpoczynających się w wierzchołku 0,
przechodzących przez wierzchołki określone maską bitową i kończących się
w wierzchołku i.
Obierasz wierzchołek startowy, np. 0
tab[2^0][0] = 1 (jest jedna ścieżka składająca się tylko z
wierzchołka 0)
A potem przedłużasz wszystkie ścieżki do długości 2, 3, 4...19:
jeśli wierzchołki i, j są połączone
jeśli (maska AND (2^j))=0 (czyli ścieżka nie zawiera jeszcze
wierzchołka j)
tab[maska OR (2^j)][j] += tab[maska][i]
Na końcu wystarczy zsumować liczby ścieżek Hamiltona o długości 19,
kończących się w wierzchołkach mających połączenie z wierzchołkiem 0.
Złożoność pamięciowa 2^n * n
Złożoność czasowa 2^n * n * k
gdzie k jest średnią liczbą połączeń
Dla takiego grafu to czas poniżej sekundy.
A.L.
>>
>> Graf liczy 20 wierzchołków, z których średnio wychodzi 10-12 gałęzi.
>>
>
>Jak taki mały, to na dzisiejszym sprzęcie można to policzyć metodą
>programowania dynamicznego.
Maly?...
>(Oczywiście mogę się mylić zgodnie z zasadą: "For every complex problem,
>there is at least one solution that is simple, easy to explain, and
>completely wrong.") :-)
>
>
>Tworzysz tablicę
> tab[2^20][20]
Chesz przenumerowac wszystkie cykle Hamiltona?... Powodzenia. W
pelnym grafie o n wierzcholkach jest (n-1)! cykli Hamiltona. 20! to
dosyc duza liczba, cos 2* 10^18. Ta liczba to o ile mnie pamiec nie
myli, to wiek Wszechswiata w milisekundach, czy cos takiego.
Oryginalny Pytacz bedzie mial troche mniej tych cykli, bo graf nie
jest pelny, ale tez dosyc duzo.
W kazdym razie zycze powodzenia. Proponuje zaczac jak najszybciej bo
czas ucieka!
A.L.
jtg
> On Sat, 27 Oct 2007 14:26:22 CST, jtg <jt...@poczta.onet.pl> wrote:
>
>
>>> Graf liczy 20 wierzchołków, z których średnio wychodzi 10-12 gałęzi.
>>>
>> Jak taki mały, to na dzisiejszym sprzęcie można to policzyć metodą
>> programowania dynamicznego.
>
> Maly?...
Mały, bo można stablicować wszystkie kombinacje wierzchołków i obliczyć
wszystko w mniej niż sekundę.
>>
>> Tworzysz tablicę
>> tab[2^20][20]
>
> Chesz przenumerowac wszystkie cykle Hamiltona?... Powodzenia. W
> pelnym grafie o n wierzcholkach jest (n-1)! cykli Hamiltona. 20! to
> dosyc duza liczba, cos 2* 10^18. Ta liczba to o ile mnie pamiec nie
> myli, to wiek Wszechswiata w milisekundach, czy cos takiego.
Ale 2^20 to całkiem mała liczba, rzędu miliona. Mamy więc 20 milionów
elementów, a na każdym wystarczy wykonać mniej niż 20 dodawań.
Duże grafy zaczynają się od 25-30 wierzchołków. :-)
>
> Oryginalny Pytacz bedzie mial troche mniej tych cykli, bo graf nie
> jest pelny, ale tez dosyc duzo.
>
> W kazdym razie zycze powodzenia. Proponuje zaczac jak najszybciej bo
> czas ucieka!
W programowaniu dynamicznym nie chodzi o to, żeby liczyć po jednym. Przy
każdym przedłużeniu ścieżki DODAJE się wyniki wyliczone dla krótszych
ścieżek.
W grafie pełnym wygląda to mniej więcej tak:
długość 1 : 1, 0, 0, 0, ... 0
długość 2 : 1, 1, 1, 1, ... 1
długość 3 : 1, 1+1...+1, 1+1.. +1, ...
= 1, 18, 18, 18 ... 18
długość 4 : 1, 18+18+...+18, 18+18+...+18, ...
= 1, 306, 306, ... 306
i tak dalej.
Pewną analogią może być liczenie silni tylko przy użyciu dodawania:
1! = 1
2! = 1+1 = 2
3! = 2 + 2 + 2 = 6
4! = 6 + 6 + 6 + 6 = 24
5! = 24 + 24 + 24 + 24 + 24 = 120
Jak wiadać nie potrzeba wcale n! dodawań, wystarczy n*(n-1)/2 dodawań.
argothiel
> Musi być ta no jakiś patent! Albo na określenie liczby cykli hamiltona,
> albo dowód na brak możliwości dokonania tego w rozsądnym czasie.
Problem określenia, czy w danym grafie istnieje co najmniej jeden cykl
Hamiltona, jest NP-zupełny, więc tym bardziej Twój problem jest
NP-zupełny. Trzeba jeszcze poczekać, zanim znajdą algorytmy wielomianowe
dla takich problemów.
> Dziękuję za poświęcony czas.
Pozdrawiam, argothiel
Piotr
> Jak taki mały, to na dzisiejszym sprzęcie można to policzyć metodą
> programowania dynamicznego.
Też o tym myślałem, ale niestety zrezygnowałem z tego pomysłu z powodów
opisanych poniżej.
> Tworzysz tablicę
> tab[2^20][20]
Rozmiar tablicy wynosi tab[1048576][20], czyli rezerwowane jest 20 971
520 komórek. Przyjmując, że każda komórka będzie miała wartość 1-bajtową
(char), to osiągamy rozmiar zarezerwowanej pamięci na poziomie 20MB.
> Dla takiego grafu to czas poniżej sekundy.
Otóż nie. Przeprowadzałem testy. Sama pętla wykonująca się 20 971 520
razy zajmuje ok 1s 360ms. Dodając to tego inne instrukcje, przypisania,
warunki, ogólny czas przekroczy dość znacznie 3s. Dodam jeszcze, że
szukanie cykli hamiltona jest jednym z etapów, na które mam magiczne 3s. :)
Jak już wspomniałem wcześniej zaimplementowałem algorytm genetyczny,
który to naprawdę w bardzo krótkim czasie znajduje mi kilkanaście cykli
hamiltona, po czym zaczyna się powtarzać. Jestem prawie pewien, że
znajduje je wszystkie, lecz aby wysunąć taką tezę muszę mieć na to jakiś
dowód. Na pewno dowodem nie jest algorytm genetyczny, który to w samej
swojej istocie polega na prawdopodobieństwu.
Mimo wszystko, dziękuję Wam za zaangażowanie.
A.L.
>
>
>Ale 2^20 to całkiem mała liczba, rzędu miliona. Mamy więc 20 milionów
>elementów, a na każdym wystarczy wykonać mniej niż 20 dodawań.
>Duże grafy zaczynają się od 25-30 wierzchołków. :-)
A skad ci sie wzielo 2^20?... Anyway, powtorze jeszcze raz: jesli
chcesz przenumerowac wszystkie cykle, to nad kazdym musisz spedzic
troche czasu. Jezeli tych cykli jest 10^18, a nad kazdym spedzisz
mikrosekunde, czyli 10^-6 sekundy, to ogolny czas bedzie 10^12. To
tez jest starsznie duza liczba.
A.L.
jtg
> jtg pisze:
> Rozmiar tablicy wynosi tab[1048576][20], czyli rezerwowane jest 20 971
> 520 komórek. Przyjmując, że każda komórka będzie miała wartość 1-bajtową
> (char), to osiągamy rozmiar zarezerwowanej pamięci na poziomie 20MB.
Bajt to trochę mało jak na taki graf, może Ci się wynik przepełnić.
>
>> Dla takiego grafu to czas poniżej sekundy.
>
> Otóż nie. Przeprowadzałem testy. Sama pętla wykonująca się 20 971 520
> razy zajmuje ok 1s 360ms. Dodając to tego inne instrukcje, przypisania,
> warunki, ogólny czas przekroczy dość znacznie 3s. Dodam jeszcze, że
> szukanie cykli hamiltona jest jednym z etapów, na które mam magiczne 3s. :)
>
Chyba zazwyczaj liczę na trochę silniejszych procesorach. :-)
Nie chciałem wcześniej komplikować, ale właściwie wystarczy tablica
[2^19][19], bo po co maska dla wierzchołka 0. Powinno być dwa razy
szybciej. Tylko na początku potrzebna jest odpowiednia inicjalizacja
wierzchołków.
I upewnij się, że kompilujesz z włączonymi opcjami optymalizacji.
jtg
>
> >
> >
> >Ale 2^20 to całkiem mała liczba, rzędu miliona. Mamy więc 20 milionów
> >elementów, a na każdym wystarczy wykonać mniej niż 20 dodawań.
> >Duże grafy zaczynają się od 25-30 wierzchołków. :-)
>
> A skad ci sie wzielo 2^20?...
Przecież napisałem w poprzednim poście. Ale powtórzę: jest to liczba wszystkich
kombinacji wierzchołków, albo inaczej liczba wszystkich podzbiorów wierzchołków.
> Anyway, powtorze jeszcze raz: jesli
> chcesz przenumerowac wszystkie cykle.
Nie chcę przenumerować wszystkich cykli. Chcę wiedzieć, ile ich jest. Więcej
wiary w matematykę. :-)
Żeby się upewnić, poświęciłem chwilę na napisanie programu liczącego cykle
Hamiltona. Działa trochę wolniej niż myślałem, bo dla 20-wierzchołkowego grafu
pełnego potrzebuje 3 sekund (MS C#, procesor 32-bitowy), niemniej jednak działa
w "rozsądnym czasie" i zwraca poprawne wyniki. Gdybyś chciał się zapoznać, mogę
Ci go przesłać na priv.
A.L.
wrote:
Program mnie nei interesuje, albowiem nie wydaje mi sie aby twoj
algorytm byl prawidlowy. Jezeli jested w stanie przeprowadzic dowod
poprawnosci, z checia go zobacze.
A.L.
Richard Roe
> Problem określenia, czy w danym grafie istnieje co najmniej jeden cykl
> Hamiltona, jest NP-zupełny, więc tym bardziej Twój problem jest
> NP-zupełny.
Jest dużo gorzej. Nie wiadomo nawet, czy ten problem jest NP-zupełny. Na
pewno jest #P-zupełny (o czym pisał już p. Jakub Wróblewski). Do NP
jeszcze daleko.
jt...@poczta.onet.pl
> algorytm byl prawidlowy.
"I find your lack of faith disturbing" :-)
> Jezeli jested w stanie przeprowadzic dowod
> poprawnosci, z checia go zobacze.
W takim razie z chęcią go przytoczę. Obawiam się jednak, że mamy zupełnie inne
pojęcie na temat tego, co jest "oczywiste". Spróbuję po kawałku.
Niech S będzie dowolnym podzbiorem wierzchołków grafu G, zawierającym
wierzchołek v0. Oznaczmy przez
T(S, i)
liczbę wszystkich ścieżek Hamiltona, które zaczynają się w wierzchołku v0,
przechodzą przez wszystkie wierzchołki z podzbioru S i kończą się w wierzchołku
i. Oczywiście i należy do S.
Liczbę T(S, i) można przedstawić jako sumę liczb T(S\{i}, k) dla tych
wierzchołków k, które mają połączenie z wierzchołkiem i.
T(S, i) = suma(po wszystkich k należących do S\{i}) G(k,i) * T(S\{i}, k)
gdzie G(k,i) przyjmuje wartość 1, jeśli wierzchołki k,i są połączone, lub 0
jeśli nie są połączone.
Czy na razie jest to dla Ciebie oczywiste (przechodzimy dalej), nieoczywiste
(mam dokładniej wyjaśnić dlaczego tak jest), czy fałszywe (napisz dlaczego)?