Mam problem i myślę, że jest to trudny NP, ale nie mogę tego udowodnić. Oto wykres warstw, w którym warstwa 0 jest najwyższą warstwą, a warstwa L najniższą. istnieje pewna ukierunkowana krawędź między warstwami, gdzie krawędź (A, B) wskazuje, że węzeł A może [pokrywać] węzeł B. A kiedy A może...
W przypadku niektórych wykresów algorytmy wyszukiwania DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności, pod warunkiem, że oba rozpoczynają się w tym samym węźle. Dwa przykłady to wykresy będące ścieżkami i wykresy w kształcie gwiazdy (drzewa o głębokości z dowolną liczbą dzieci). Czy...
W przypadku problemu ze stacją benzynową podajemy miast i drogi między nimi. Każda droga ma długość, a każde miasto określa cenę paliwa. Jedna jednostka drogi kosztuje jedną jednostkę paliwa. Naszym celem jest przejście ze źródła do miejsca docelowego w najtańszy możliwy sposób. Nasz czołg jest...
Załóżmy, że mam ukierunkowany wykres z wagami krawędzi narysowanymi z zakresu [1,…,K][1,…,K][1,\dots, K] gdzie KKK jest stałe. Jeśli próbuję znaleźć najkrótszą ścieżkę za pomocą algorytmu Dijkstry , jak mogę zmodyfikować strukturę algorytmu / danych i poprawić złożoność czasu do...
Oto problem: Jest połączony wykres z węzłami reprezentującymi wiele osób. Każdy węzeł / osoba ma opinię na dany temat, np. Atut vs clinton, papierowe książki kontra kindle itp Celem jest, aby każdy węzeł na wykresie podzielał tę samą opinię, wybierając konkretny podzbiór węzłów, w określonej...
Binarnej sekwencji o długości nnn właśnie uporządkowaną sekwencję x1,…,xnx1,…,xnx_1,\ldots,x_n , tak że każdy xjxjx_j oznacza albo 000 lub 111 . Aby wygenerować wszystkie takie sekwencje binarne, można użyć oczywistej struktury drzewa binarnego w następujący sposób: katalog główny jest „pusty”, ale...
Z grubsza, wykres bezkierunkowy jest bardzo podobny do wykresu skierowanego, gdzie dla każdej krawędzi (v, w) zawsze jest krawędź (w, v). To sugeruje, że akceptowalne może być wyświetlanie nieukierunkowanych wykresów jako podzestawu kierowanych wykresów (być może z dodatkowym ograniczeniem, że...
Czy algorytm Dijkstry jest wykorzystywany w nowoczesnych systemach wyszukiwania tras, takich jak mapy Google czy satnav w samochodzie? Jeśli nie, to czym
Szukam algorytmu do konwersji digrafu (grafu kierunkowego) na graf niekierowany w sposób odwracalny, tzn. Digraf powinien być odtwarzalny, jeśli otrzymamy wykres niekierowany. Rozumiem, że przyjdzie to kosztem niekierowanego wykresu mającego więcej wierzchołków, ale nie mam nic przeciwko. Czy ktoś...
Alternatywne sformułowanie Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do...
Wystąpił następujący problem: Biorąc pod uwagę ukierunkowany wykres acykliczny z rzeczywistymi wartościami grubości krawędzi oraz dwoma wierzchołkami s i t, oblicz minimalny st st cut. Dla ogólnych wykresów jest to trudne NP, ponieważ można w prosty sposób zredukować maksymalne cięcie, po prostu...
Czy w mojej obserwacji mam rację, że liczność maksymalnego dopasowania MMM wykresu dwudzielnego G(U,V,E)G(U,V,E)G(U, V, E) jest zawsze równy min(|U|,|V|)min(|U|,|V|)\min(|U|,
Piszę program, rozwiązując problem chińskiego listonosza (znany również jako problem z inspekcją trasy) w niedokierowanym drafcie i obecnie napotykam problem, aby znaleźć najlepsze dodatkowe krawędzie do łączenia węzłów o dziwnym stopniu, dzięki czemu mogę obliczyć obwód Eulera. Może istnieć...
Generuję losowe DFA, aby przetestować na nich algorytm redukcji DFA. Algorytm, którego teraz używam, jest następujący: dla każdego stanu , dla każdego symbolu w alfabecie dodaj do jakiegoś losowego stanu. Każde państwo ma takie samo prawdopodobieństwo, że stanie się stanem końcowym.qqqdodocδ( q, c...
Tło. Piszę kod do półautomatycznej gradacji, używając gradacji rówieśniczej jako części procesu gradacji. Uczniowie otrzymują pary esejów na raz, a uczniowie mają suwak do wyboru, który jest lepszy io ile lepszy. np. suwak może wyglądać mniej więcej tak: A---X-B Na podstawie wyników oceny...
Czy istnieje charakterystyka wykresów, których zestaw krawędzi rozkłada się w rozłączny związek idealnych dopasowań? Jedną trywialną klasą takich grafów są ddd-nieregularne -obustronne wykresy. Ich zestaw krawędzi rozpadnie się na rozłączne idealne dopasowania....
Biorąc pod uwagę ważony digraf G=V,EG=V,EG=V,Ei funkcja wagi, d(u,v)d(u,v)d(u,v), zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać2nd2nd2^{nd}- najkrótsza ścieżka, 3rd3rd3^{rd}-krótko i tak dalej. Pytania: Czy istnieje skuteczny algorytm do...
Obecnie czytam kilka artykułów na temat wypychania łańcucha Markowa i nie dostrzegam różnicy między łańcuchem Markowa a zwykłym, ważonym wykresem. Na przykład w artykule Optymalne zbieranie przestrzeni stanu w łańcuchach Markowa podają następującą definicję CTMC (ciągły łańcuch Markowa w...
Powiedzmy, że mam niedokierowany skończony wykres rzadki i muszę być w stanie efektywnie uruchamiać następujące zapytania: IsConnected(N1,N2)IsConnected(N1,N2)IsConnected(N_1, N_2) - zwraca jeśli istnieje ścieżka między i , w przeciwnym
Zastanawiałem się, czy ten problem ma nazwę: Biorąc pod uwagę prosty wykres, którego krawędzie są w kolorze czerwonym, niebieskim i zielonym, G = ( V, B ∪ R ∪ G )G=(V,B∪R∪G)G=(V,B\cup R\cup G), czy jest kolorowanie wierzchołków c : V→ { B , R , G }c:V→{B,R,G}c:V\to \{B,R,G\} tak, że każda krawędź...