Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

1
Jaki jest najszybszy algorytm deterministyczny dla dynamicznej osiągalności digrafu bez usuwania krawędzi?
Jaki jest najlepszy wynik deterministyczny dla utrzymania dynamicznego zamknięcia przechodniego na ukierunkowanym wykresie z tylko wstawieniem krawędzi? Przeczytałem kilka artykułów na temat problemu dynamicznego zamykania przechodniego zarówno przy wstawianiu, jak i usuwaniu krawędzi. Czy są jednak lepsze algorytmy z tylko wstawianiem krawędzi?
3
Najmniejszy zbiór, który przecina niektóre podane zbiory
Niech będą zestawami, które mogą mieć wspólne elementy. Szukam najmniejszego zestawu takiego, że .S1,S2,…,SnS1,S2,…,SnS_1,S_2,\ldots,S_nXXX∀i,X∩Si≠∅∀i,X∩Si≠∅\forall i,\,X\cap S_i \ne \emptyset Czy ten problem ma nazwę? Czy może sprowadza się to do znanego problemu? W moim kontekście opisują elementarne cykle silnie połączonego komponentu i szukam najmniejszego zestawu wierzchołków który przecina wszystkie cykle.S1,…,SnS1,…,SnS_1,\ldots,S_nXXX
2
podobne matryce
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że są permutacją, które wiążą ten problem z …
1
Jak obliczyć moc macierzy kwadratowych?
Załóżmy, że otrzymujemy macierz i pozwólmy . Jak szybko możemy obliczyć moc A ^ m tej macierzy? m ∈ N 0 A mA ∈ RN.× N.ZA∈RN.×N.A \in \mathbb R^{N\times N}m ∈ N0m∈N.0m \in \mathbb N_0ZAmZAmA^m Kolejną najlepszą rzeczą w porównaniu do obliczania produktów jest zastosowanie szybkiego potęgowania, które wymaga produktów …
4
Sparametryzowany algorytm znajdowania biklików
Biorąc pod uwagę nieukierowany wykres nnn wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową k × kk×kk\times k ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i sprawdzanie, czy występuje co najmniej k innych wierzchołków przypadających na wszystkie z …
2
Charakterystyka problemów, dla których istnieją algorytmy czasu podliniowego
Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń podliniowa (np. Algorytmy szkicowania / przesyłania strumieniowego, w których maszyna Turinga ma taśmę tylko do odczytu, podliniową przestrzeń …
6
Kiedy mówi się, że dwa algorytmy są „podobne”?
Nie pracuję w teorii, ale moja praca wymaga od czasu do czasu czytania (i rozumienia) prac teoretycznych. Kiedy zrozumiem (zestaw) wyników, omawiam je z ludźmi, z którymi pracuję, z których większość również nie działa w teorii. Podczas jednej z takich dyskusji pojawiło się następujące pytanie: Kiedy mówi się, że dwa …
2
Zwroty permutacyjne z analizą LR
Wyrażenie permutacji jest rozszerzeniem standardu (E) BNF wolne definicji kontekstu gramatyczne: frazę permutacji zawiera n produkcji (lub równoważnie nieterminale) A 1 przez A n . W miejscu wyrażenia permutacyjnego chcielibyśmy zobaczyć każdą z tych produkcji dokładnie raz, ale nie jesteśmy zainteresowani kolejnością tych nieterminali.{ A1, … , An}{ZA1,…,ZAn}\{ A_1, \dots, …
2
Znajdowanie k najkrótszych ścieżek za pomocą algorytmu Eppsteina
Próbuję dowiedzieć się, jak działa wykres ścieżki według algorytmu Eppsteina w tym artykule i jak mogę zrekonstruować najkrótszych ścieżek od do z odpowiednią konstrukcją stosu .k s t H ( G )P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Jak dotąd: out(v)out(v)out(v) zawiera wszystkie krawędzie opuszczające wierzchołek na wykresie , które nie są częścią najkrótszej ścieżce . …
1
Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym
Jak dobrze wiadomo, rozkład drzewa wykresu składa się z drzewa ze skojarzoną torbą dla każdego wierzchołka , który spełnia następujące warunki:T T v ⊆ V ( G ) v ∈GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Każdy wierzchołek występuje w jakimś workiem .TGGGTTT Dla każdej krawędzi znajduje się worek zawierający oba punkty …
1
Algorytm optymalizacji drzew decyzyjnych
tło Binarne drzewo decyzja TTT jest zakorzenione drzewo gdzie każdy węzeł wewnętrzny (i korzeń) jest oznaczony przez indeks w j∈{1,...,n}j∈{1,...,n}j \in \{1,..., n\} taki sposób, że żadna ścieżka od korzenia do liścia nie powtarza indeksu, liście są oznaczone wyjściami w {A,B}{A,B}\{A,B\} , a każda krawędź jest oznaczona przez 000 dla …
1
Jak nazywa się ten problem z grafem skierowanym?
Wykonaj ukierunkowany wykres gdzie krawędzie są ozdobione naturalną liczbą. Chcemy zestawu wszystkich ścieżek między dwoma wierzchołkami v 1 i tak aby każda kolejna krawędź ścieżki była ozdobiona liczbą naturalną, która jest większa niż liczba naturalna dekorująca poprzednią krawędź.GGGv 2P.P.Pv1v1v_1v2)v2)v_2 Przykładem może być rozkład jazdy autobusów lub pociągów. Jeśli próbujesz ustalić …
3
Dlaczego różnicowe współczynniki aproksymacji nie są dobrze zbadane w porównaniu ze standardowymi pomimo deklarowanych korzyści?
Istnieje standardowa teoria aproksymacji, w której stosunek aproksymacji wynosi supAOPTsupAOPT\sup\frac{A}{OPT} (dla problemów zcelamiMINMINMIN),AAA- wartość zwracana przez niektóre algorytmyAAAiOPTOPTOPT- wartość optymalna. I inna teoria, żeprzybliżenie różnicowe,gdzie stosunek przybliżenia wynosiinfΩ−AΩ−OPTinfΩ−AΩ−OPT\inf\frac{\Omega-A}{\Omega-OPT} ,ΩΩ\Omega- najgorsza wartość wykonalnego rozwiązania dla danego wystąpienia. Doautorówz tego twierdzenia teorii, że ma jakieś konkretne korzyści w stosunku do klasycznego jednego. …
2
Złożoność czasowa algorytmu Bellmana-Helda-Karpa dla TSP, weź 2
Ostatnie pytanie dotyczyło teraz klasycznego algorytmu programowania dynamicznego dla TSP, niezależnie od Bellmana i Held-Karpa . Algorytm jest powszechnie zgłaszany do działania w czasie . Jednak, jak niedawno zauważył jeden z moich studentów, ten czas działania może wymagać nieracjonalnie silnego modelu obliczeń.O(2nn2)O(2nn2)O(2^n n^2) Oto krótki opis algorytmu. Dane wejściowe składają …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.