Pytania otagowane jako ds.algorithms

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

2
Jak tasować kolorowe kulki?
Mam 400 piłek, w których 100 to czerwone, 40 to żółte, 50 to zielone, 60 to niebieskie, 70 to fioletowe, 80 to czarne. (kule tego samego koloru są identyczne) Potrzebuję wydajnego algorytmu tasowania, aby po tasowaniu kulki znalazły się na liście i 3 kolejne kule nie są tego samego koloru. …
1
Znalezienie płaszczyzny cięcia, która równomiernie dzieli wielościan
Powiedzmy, że mamy wielościan w standardowej formie: A x = bx ≥ 0ZAx=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba wierzchołków po każdej stronie hiperpłaszczyzny jest w przybliżeniu taka sama? (tj. algorytm minimalizujący …
2
Problemy z kratą
Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.). Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat. W szczególności jestem zainteresowany tym, czy zbadano następujące problemy z siecią: Rozpoznawanie krat: czy przy danym DAG czy …
4
Koszty wykonania ok. szukaj najbliższego sąsiada w pomijanym quadtree
UWAGA : Pytanie zostało ponownie sformułowane w moich odpowiedziach: Zakładając, że możemy znaleźć najniższych przodków rodzeństwa w czasie , czy ANN można naprawdę wykonać w ?O ( 1 )O(1)O(1)O ( logn )O(log⁡n)O(\log n) Czworoboki są wydajnymi wskaźnikami przestrzennymi. Mam łamigłówkę z implementacją wyszukiwania najbliższego sąsiada w skompresowanej strukturze quadtree, jak …
1
Czy istnieje algorytm wielomianowy do rozwiązywania izomorfizmu grafów dla grafów Delaunaya (skończonych) heksagonalnych teselacji?
Biorąc pod uwagę skończoną płaszczyznę, mam sześciokątną teselację tej płaszczyzny z regularnym sześciokątem o stałej wielkości. Następnie obliczam wykres G Delaunaya dla teselacji. Biorąc pod uwagę taki wykres G, usuwam określone zestawy węzłów na tym wykresie, aby uzyskać wiele podgraphów G. Muszę ustalić, czy podgrupy te są izomorficzne (względem siebie). …
1
Relaks
Mam pytanie wykonalności, które można sformułować w następujący sposób. Ja dany punkt w -wymiarowej przestrzeni wektorowej i chcę, aby znaleźć najbliższy punkt do że spełnia zestaw „ ograniczeń” formularzadpppreddp ℓ 0qqqpppℓ0ℓ0\ell_0 Biorąc pod uwagę zestaw , co najwyżej jeden z może być niezerowy.S.∈ [ 1 … d]S∈[1…d]S \in [1\ldots d]{ …
1
Jakie algorytmy / dane do czytania poleciłbyś przy rozwiązywaniu transakcji / blokad odczytu i zapisu?
Uproszczoną klasyczną transakcję bazy danych można wyświetlić jako: czytanie M. pozycji wykonanie pewnych obliczeń na podstawie tych odczytów zapisywanie niektórych wyników N na podstawie tych obliczeń, które mogą obejmować pierwotnie odczytane elementy. Podczas wykonywania tych transakcji (jednocześnie) należy zachować właściwości ACID . Dokładnie takie same wymagania (N aktualizacji na podstawie …
1
Przycinanie silnie połączonego digrafa
Biorąc pod uwagę silnie połączony wykres G z ważonymi krawędziami, chciałbym zidentyfikować krawędzie, które prawdopodobnie nie są częścią żadnego minimalnie silnie połączonego podgrupy (MSCS) G. Jedną z metod znajdowania takich krawędzi jest zmodyfikowany algorytm Floyda-Warshalla. Korzystając z algorytmu Floyda-Warshalla, można określić, które krawędzie nigdy nie są najlepszą opcją przejścia od …
1
Znalezienie krótkich i grubych ścieżek
Motywacja: W standardowych algorytmach maksymalnego przepływu ścieżki augmentacyjnej wewnętrzna pętla wymaga znalezienia ścieżek od źródła do zatonięcia na ukierunkowanym, ważonym wykresie. Teoretycznie dobrze wiadomo, że aby algorytm nawet zakończył działanie, gdy istnieją nieracjonalne pojemności krawędzi, musimy nałożyć ograniczenia na ścieżki, które znajdziemy. Na przykład algorytm Edmondsa-Karpa mówi nam, aby znaleźć …
3
Algorytmy obliczania równowagi Nasha.
Przeszukałem forum, aby sprawdzić, czy zostało to już zadane, i chociaż omawiamy teorię gier algorytmicznych, nie mogłem znaleźć rozwiązania tego konkretnego problemu. Próbuję dowiedzieć się, jaki jest najbardziej znany algorytm obliczania przybliżonej (mieszanej strategii) równowagi Nasha w skończonej grze n-person. Oczywiście algorytmem tym byłby PPAD. Bardziej interesuje mnie szybkość / …
4
Interesujące funkcje na wykresach, które można skutecznie zmaksymalizować.
Powiedz, że mam wykres ważony G=(V,E,w)G=(V,E,w)G = (V,E,w) taki, że w:E→[−1,1]w:E→[−1,1]w:E\rightarrow [-1,1] jest funkcją ważenia - zwróć uwagę, że dopuszczalne są wagi ujemne. Powiedzieć, że f:2V→Rf:2V→Rf:2^V\rightarrow \mathbb{R} definiuje właściwość każdego podzbioru wierzchołków S⊂VS⊂VS \subset V . fffargmaxS⊆Vf(S)arg⁡maxS⊆Vf(S)\arg\max_{S \subseteq V}f(S) Na przykład funkcja cięcia wykresu jest interesującą właściwością podzbiorów wierzchołków, ale …
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.