szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 10:43 
Użytkownik

Posty: 90
Lokalizacja: wawa
Witam,

Poszukuję algorytmów znajdowania dowolnej (znanej) ścieżki w grafie skierowanym (drzewie). Nie chodzi o znalezienie najkrótszej, najdłuższej,itp. ścieżki, a sprawdzenie czy dana ścieżka w grafie istnieje. Np. Załóżmy że mamy dwa ciągi początkowe: A=1-2-4-6 i B=1-2-4-7 i chcemy sprawdzić czy ścieżka utworzona przez takie wartości istnieje, przy czym sprawdzamy węzły drzewa tylko do momentu odnalezienia konkretnej wartości, reszty już nie.
Rysunki poniżej przedstawiają sytuację odnalezienia ścieżki (rys1), i nie odnalezienia ścieżki (rys2).

rys1:
Obrazek

rys2:
Obrazek
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 11:01 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Czyli numery wierzchołków drzewa mogą się w nim powtarzać? To są bardziej takie kolory wierzchołków? I chcemy znaleźć ścieżkę o wierzchołkach w k kolejnych kolorach?
Jaki jest oczekiwany pesymistyczny czas działania algorytmu (ze względu na liczbę wierzchołków)?

-- 28 sierpnia 2016, 11:23 --

Prawdopodobnie mam rozwiązanie wielomianowe, już piszę.

Niech n to liczba wierzchołków grafu, a k to długość szukanej ścieżki.
Przeróbmy ten graf na inny graf skierowany. Ale najpierw ponumerujmy jeszcze dodatkowo wszystkie wierzchołki naszego grafu tak aby numery się nie powtarzały (nowe numery). Każdy wierzchołek starego grafu przerabiam na tyle wierzchołków w nowym grafie ile razy może występować na szukanej ścieżce.
W nowym grafie każdy wierzchołek jest identyfikowany przez dwa numery - nowy numer (którym przed chwilą ponumerowałem stare drzewo) i pozycję (licząc od początku ścieżki) na której ten kolor występuje na ścieżce.
Krawędzie prowadzę tylko od wierzchołka o pozycji x do pozycji x + 1. Wierzchołek łączę ze wszystkimi wierzchołkami z którymi sąsiadował w starym grafie pod warunkiem, że pozycja jest o jeden większa - dlatego nowy graf jest acyklicznym grafem skierowanym (DAG).
W nowym grafie szukam ścieżki od jakiegoś wierzchołka o pozycji 1, do jakiegoś wierzchołka o pozycji równej długości ścieżki, czyli k. Zrobię to tak - dodaję tzw. superwierzchołek z którego kieruję krawędzie do wszystkich wierzchołków o pozycji 1. Następnie puszczam algorytm na przeszukiwanie grafu, może to być bfs lub dfs z tego superwierzchołka. Aby móc odtworzyć ścieżkę w tym przeszukiwaniu w każdym wierzchołku zapisuję numer wierzchołka z którego do niego przyszedłem - wtedy mogę odtworzyć ścieżkę idąc od wierzchołka ostatniej warstwy - o największej pozycji.

Czas: W nowym grafie mam maksymalnie nk wierzchołków (dla każdego wierzchołka maksymalnie k kopii) i n^{2}k krawędzi (każdy wierzchołek połączony z maksymalnie n wierzchołkami w nowym grafie o stopniu wyższym o 1), czyli czas równy pesymistycznie liczbie krawędzi, ale może można to lepiej oszacować.
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 11:43 
Użytkownik

Posty: 90
Lokalizacja: wawa
Generalnie chodzi o takie kolorowanie wierzchołków - główny aspekt zagadnienia dotyczy sytuacji kiedy mamy graf, mamy przykładową ścieżkę z wierzchołkami i chcemy sprawdzić w szybki sposób czy taka ścieżka w grafie istnieje czy nie. A co w sytuacji kiedy zamiast cyfr byłyby dane i to niepowtarzające się np. znalezienie czy w grafie znajdują się dane: dom- kot- obiad - wypłata?
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 12:39 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
To nie ma znaczenia czy kolory są cyframi czy jakimiś danymi - możemy przecież każdą daną ponumerować. Np. wziąć wszystkie dane do zbioru, posortować jakoś i usunąć duplikaty, potem ponumerować i przenumerować graf.
To że dane nie powtarzają się na ścieżce upraszcza sprawę - dla każdego wierzchołka starego grafu będzie tylko jeden jego odpowiednik w nowym grafie.

-- 28 sierpnia 2016, 13:40 --

Utworzony graf nazywa się grafem warstwowym - każdemu wierzchołkowi ścieżki odpowiada warstwa wierzchołków jego koloru, a krawędzie są tylko między sąsiednimi warstwami.

Te nowe numery są po to, aby dla każdego wierzchołka z nowego grafu znać odpowiadający mu wierzchołek starego grafu.
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 14:48 
Użytkownik

Posty: 90
Lokalizacja: wawa
Dzięki. A mógłbyś dla lepszego zrozumienia zobrazować to jakimś przykładem (tak żebym miał pewność że wszystko rozumiem).
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 17:03 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Zrobiłem poprawki w ostatniej fazie algorytmu - przeszukiwanie z dowolnego wierzchołka to jednak trochę za mało - dodałem superwierzchołek.

Mam nadzieję, że wiesz co to jest bfs/dfs i tego nie muszę tłumaczyć.

Zobrazujmy to na Twoim pierwszym przykładzie.
Ponumerujmy wierzchołki (to są te nowe numery) od 1 do 11, bo tyle jest wierzchołków (numeruję wierzchołki od kolumny lewej, kolejno od góry).
Kolory wierzchołków (o nowych numerach od 1 do 11): 1 1 2 3 1 2 3 4 3 6 9.
Krawędzie (wyrażone za pomocą nowych numerów):
1 -> 2, 1 -> 3, 1 -> 4 , 3 -> 5, 3 -> 6, 3 -> 7, 3 -> 8, 8 -> 9, 8 -> 10, 8 -> 11.

Nowy graf warstwowy wygląda tak (s to superwierzchołek) (w każdej warstwie wierzchołki są tego samego koloru):
Wierzchołki [pozycja(warstwa), nowy numer]:
warstwa 0: [0, s],
warstwa 1: [1, 1], [1, 2], [1, 5],
warstwa 2: [2, 3], [2, 6],
warstwa 3: [3, 8],
warstwa 4: [4, 10].
Kolejne warstwy możemy rysować od lewej do prawej, a wierzchołki w danej warstwie od góry do dołu.

Krawędzie:
[0, s] -> [1, 1], [0, s] -> [1, 2], [0, s] -> [1, 5], [1,1] -> [2, 3], [2, 3] -> [3, 8], [3, 8] -> [4, 10]

Puszczamy np. bfs z wierzchołka [0, s].
Szukana ścieżka to [0, s] -> [1, 1] -> [2, 3] -> [3, 8] -> [4, 10], czyli 1 -> 3 -> 8 -> 10.

-- 28 sierpnia 2016, 17:55 --

mariusz198787, zauważ, że początkowy graf nie musi być drzewem, nie musi być nawet skierowany - graf warstwowy tworzymy wtedy podobnie.
Można też tak rozwiązać podobne zadanie, gdzie ścieżka miałaby być najkrótsza. Krawędzie naszego nowego grafu są krawędziami z grafu początkowego (być może wielokrotnie skopiowanymi), dlatego gdyby nasz początkowy graf miał wagi (np. długości) na krawędziach, to moglibyśmy wagi te przełożyć na nowy graf i szukać w nim kolorowej ścieżki o najkrótszej długości np. algorytmem Dijkstry, albo poprzez programowanie dynamiczne (bo nasz graf jest DAGiem).
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 19:00 
Użytkownik

Posty: 90
Lokalizacja: wawa
OK, nawet łapie. Tylko jedna kwestia, dlaczego w warstwie 3 jest 8, a nie 4 i 7 (zgodnie z numeracją kolorów)? Niby widzę, że warstwa oznacza przejście i faktycznie tam powinien być wierzchołek 8.
Góra
Mężczyzna Offline
PostNapisane: 28 sie 2016, o 21:38 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Każda warstwa (poza zerową, dodatkową) odpowiada kolejnemu kolorowi wierzchołka szukanej ścieżki (kolejnej pozycji). Warstwa 3 odpowiada kolorowi 4 - jest jeden wierzchołek o kolorze 4, ma on numer 8.
Góra
Mężczyzna Offline
PostNapisane: 29 sie 2016, o 19:28 
Użytkownik

Posty: 90
Lokalizacja: wawa
Ale zauważ:

wierzchołek:-1|1|2|3|1|2|3|4|3|6|9|
nr indeksu:--1|2|3|4|5|6|7|8|9|10|11|
kolor:--------1|1|2|3|1|2|3|4|3|6|9|

Skoro warstwie odpowiada ten sam kolor no w z tego wynika, że w trzeciej są wierzchołki o indeksie 4 i 7 a dopiero w 4 warstwie 8 w piątej warstwie jest 6 i w szóstej 9. Ja tak to rozumiem i dlatego coś mi się nie zgadza
Góra
Mężczyzna Offline
PostNapisane: 29 sie 2016, o 19:58 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Warstw jest łącznie 5 - od warstwy nr 0 do warstwy nr 4 - jest ich tyle co długość szukanej ścieżki + warstwa z superwierzchołkiem. Nie rozumiem skąd u Ciebie tak dużo warstw....
Kolor i-tej warstwy to kolor i-tego wierzchołka szukanej ścieżki.

Już ok?
Góra
Mężczyzna Offline
PostNapisane: 29 sie 2016, o 20:37 
Użytkownik

Posty: 90
Lokalizacja: wawa
OK, po prostu kolor każdej warstwy to kolor wierzchołka z szukanej ścieżki, a nie wszystkich wierzchołków i ich kolorów. W zasadzie to już samo tworzenie grafu warstwowego powie nam czy dana ścieżka istnieje czy nie (w sytuacji ścieżki:1-2-4-6 istnieje graf, a w sytuacji ścieżki: 1-2-4-7 taki graf nie istnieje bo nie mamy czwartej warstwy, która jest pusta)
Góra
Mężczyzna Offline
PostNapisane: 31 sie 2016, o 00:29 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Samo tworzenie grafu warstwowego rzeczywiście powie nam, czy dana ścieżka istnieje czy nie, ale z trochę innego powodu. Ścieżka może nie istnieć nie tylko w przypadku, gdy któraś z warstw jest pusta, ale np. wtedy gdy jedna ścieżka biegnąca od pierwszej warstwy kończy się w środkowej warstwie, a druga w niej zaczyna, i biegnie do końca, ale nie mają one wspólnych wierzchołków.
Można budować ten graf warstwowy np. idąc po kolejnych wierzchołkach szukanej ścieżki od jej pierwszego wierzchołka i dokładając nową warstwę pozostawiać w niej tylko te wierzchołki, które są połączone z jakimś wierzchołkiem z poprzedniej warstwy - to zapewni istnienie szukanej ścieżki.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Istnienie cyklu w grafie  Majeskas  8
 składowa w grafie  tukanik  1
 Ilość cykli hamiltona w grafie kostki Q4 ?  luki1423  1
 Ścieżka hamiltona w grafie  kylercopeland  1
 Dowód nierówności w grafie  Fray  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl