Autor Wątek: Jak szybko wykryć, że nie da się gdzieś dojść  (Przeczytany 4941 razy)

Offline Angru

  • Użytkownik

# Listopad 03, 2009, 12:20:06
Nie ma co, aura tajemniczosci narasta.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline matmis

  • Użytkownik

# Listopad 03, 2009, 12:29:54
Tylko dla tych, co nie potrafią użyć google'a.

Offline raver

  • Użytkownik
    • Moja strona domowa.

# Listopad 03, 2009, 17:16:13
Ja bym liczył od razu dla wszystkich obiektów (w czasie O(n) gdzie n=liczba wierzchołków) jadąc po wierzchołkach BFSem i przypisując wierzchołkom wygenerowanym po jednym przejściu BFSa taką samą liczbę. Wtedy agent zajmujący dany wierzchołek może dostać się do miejsc oznaczonych numerami wierzchołków sąsiadujących z jego wierzchołkiem.

Coś takiego:
int nr=0;
for wszystkie wierzchołki V
  jeśli V nie odwiedzony to
  {
     nr++;
     bfs(V); ( tu wszystkich odwiedzonym w tym przebiegu wierzchołkom przypisujemy wartość nr)
  }


A sprawdzanie czy agent może dojść do V:
  for U takim, że ma wspólną krawędź z wierzchołkiem agenta
    if(nr[U] == nr[V])
      return można dojść;
  return nie można dojść;

Mam nadzieję, że się nie wygłupiłem :).

pozdrawiam

#edit: yay, prawda, było już :P
« Ostatnia zmiana: Listopad 03, 2009, 18:50:07 wysłana przez raver »

Offline DamorK

  • Użytkownik

# Listopad 03, 2009, 18:45:27
Mam nadzieję, że się nie wygłupiłem :).

Było o silnie spójnych składowych więc może się nie wygłupiłeś, ale odkrywczego to też nic nie powiedziałeś :P

Offline Angru

  • Użytkownik

# Listopad 03, 2009, 19:35:07
Tylko dla tych, co nie potrafią użyć google'a.
To google to taka stronka z takim okienkiem gdzie można się zapytać co i jak? Nie zaglądałem, bo obecnie nie potrzebuję tej struktury. Nie rozumiem jednak dlaczego podajesz tak enigmatyczne wskazówki.

@raver
Nie nie wygłupiłeś się :), jeżeli dobrze Cię rozumiem, to na tym właśnie mniej więcej polega znajdowanie spójnych składowych dla grafu. Jadę po prostu rekurencyjnie po siąsiadach każdego wierzchołka oznaczając już te sprawdzone. Nie jest to chyba O(n) bo jeśli obecnie sprawdzana spójna składowa się skończy, to muszę jakby wrócić i znaleźć w całym grafie następny niesprawdzony wierzchołek, ale to nie wielka strata, bo spójnych składowych jest niewiele. W każdym razie idzie szybko.
« Ostatnia zmiana: Listopad 03, 2009, 19:39:34 wysłana przez Angru »

Offline matmis

  • Użytkownik

# Listopad 03, 2009, 21:05:02
Nie zaglądałem, bo obecnie nie potrzebuję tej struktury. Nie rozumiem jednak dlaczego podajesz tak enigmatyczne wskazówki.
Z paru przyczyn:
1) właśnie dlatego, że (jeszcze?) nie potrzebujesz takiej struktury
2) na forum www, w odróżnieniu od zwykłej rozmowy, jest tak, że prostym gestem myszki możesz zaznaczyć fragment mojej wypowiedzi i wrzucić jako zapytanie do wyszukiwarki - i faktycznie prowadzi to dalej mimo że wskazówka wydaje się Tobie enigmatyczna
3) zawsze możesz zadać pytanie bez aluzji - będziesz głupcem przez 5 minut zamiast przez całe życie (podobno tak głosi chińskie przysłowie)

Offline raver

  • Użytkownik
    • Moja strona domowa.

# Listopad 03, 2009, 21:10:13
Cytuj
Nie jest to chyba O(n) bo jeśli obecnie sprawdzana spójna składowa się skończy, to muszę jakby wrócić i znaleźć w całym grafie następny niesprawdzony wierzchołek

Jest to O(n): każdy wierzchołek jest przechodzony w BFSie tylko raz i każdy wierzchołek w głównej pętli for jest sprawdzany tylko raz. Więc jak nie masz dużo wierzchołków w tym grafie... :)

@down: http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz, wg tego O(n+k), gdzie k przy grafie gęstym może wynosić nawet n^2, jak już idziemy tak bardzo szczegółowo :), teoria, w praktyce będzie to coś koło O(n)

@edit2: dobra, już się nie wypowiadam, bo mieszam :D
« Ostatnia zmiana: Listopad 03, 2009, 22:00:45 wysłana przez raver »

Offline Troll

  • Użytkownik
    • Oficjalna strona gry Gizarma

# Listopad 03, 2009, 21:39:25
Jest to O(n): każdy wierzchołek jest przechodzony w BFSie tylko raz i każdy wierzchołek w głównej pętli for jest sprawdzany tylko raz. Więc jak nie masz dużo wierzchołków w tym grafie... :)

Ja bym powiedział raczej, że O(n*k), gdzie n - liczba wierzchołków, k - średni stopień wierzchołków dlatego, że n razy rozwijasz wieżchołek i sprawdzasz czy jeden z k następników był już sprawdzony