Pytania otagowane jako tree

Drzewo to specjalny typ wykresu, który pozwala tylko na hierarchiczny zestaw krawędzi, podobny do drzewa. Matematycznie jest to właściwie arborescence. Drzewa mają węzeł główny i węzły potomne. W kategoriach formalnych jest opisany jako acyklicznie połączony graf.

20
Trudne problemy z NP na drzewach
Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw, izomorfizm subgrafu. Wymień niektóre naturalne problemy z optymalizacją, które na …
4
Dlaczego ktoś miałby używać Octree zamiast drzewa KD?
Mam pewne doświadczenie w obliczeniach naukowych i intensywnie korzystałem z drzewek kd do aplikacji BSP (partycjonowanie przestrzeni binarnej). Niedawno zapoznałem się raczej z oktatami, podobną strukturą danych do partycjonowania trójwymiarowych przestrzeni euklidesowych, ale taką, która działa w ustalonych regularnych odstępach czasu, z tego, co zbieram. Trochę badań dotyczących niezależności wydaje …
1
Czy istnieje zwykły język drzewa, w którym średnia wysokość drzewa o rozmiarze nie jest ani ani ?
Definiujemy zwykły język drzewa, tak jak w książce TATA : Jest to zestaw drzew akceptowany przez niedeterministyczny automat skończonego drzewa (rozdział 1) lub, równoważnie, zbiór drzew wygenerowany przez zwykłą gramatykę drzewa (rozdział 2). Oba formalizmy są bardzo podobne do znanych analogów strunowych. Czy istnieje zwykły język drzewa, w którym średnia …
2
wydajny algorytm różnicowy dla drzew i odległości Levenshteina
Niedawno przeczytałem to podsumowanie zagadnień związanych z różnicowaniem między drzewami i zainteresowało mnie poznanie najnowocześniejszych rozwiązań tego problemu. Załóżmy również, że między dozwolonymi operacjami edycji jest tradycyjny węzeł dodawania / usuwania, edytuj zawartość, którą dodajesz rozszerzonymi operacjami poddrzewa kopiuj / przenieś, czy to sprawia, że ​​problem (znalezienie optymalnej różnicy) jest …
1
Znajdowanie odległości między dwoma wielomianami (przedstawionymi jako drzewa)
Kolega pracujący nad programowaniem genetycznym zadał mi następujące pytanie. Najpierw próbowałem go rozwiązać w oparciu o chciwe podejście, ale po drugiej myśli znalazłem kontrprzykład na algorytm chciwy. Pomyślałem więc, że warto tu wspomnieć. Rozważ dwa wielomiany reprezentowane przez drzewa wyrażeń. Na przykład x3)- 2 x + 1x3)-2)x+1x^3-2x+1 i x2)+ 4x2)+4x^2 …
2
utrzymywanie zrównoważonego drzewa opinającego rosnącego niekierowanego wykresu
Poszukuję sposobów na utrzymanie względnie zrównoważonego drzewa opinającego wykresu, gdy dodam do niego nowe węzły / krawędzie. Mam nieukierunkowany wykres, który zaczyna się jako pojedynczy węzeł, „root”. Na każdym kroku dodaję do wykresu albo nowy węzeł i krawędź łączącą go z wykresem, albo tylko nową krawędź łączącą dwa stare węzły. …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
3
Scalenie dwóch drzew wyszukiwania binarnego
Szukam algorytmu do połączenia dwóch drzew wyszukiwania binarnego o dowolnej wielkości i zakresie. Oczywisty sposób byłoby przejść o wdrażaniu tego byłoby znaleźć całe poddrzewa, których zakres można dopasować do dowolnego węzła zewnętrznego w drugim drzewie. Jednak najgorszy czas działania tego typu algorytmu wydaje się być w kolejności, O(n+m)gdzie ni msą …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
3
Wyprzedaż Boba (zmiana kolejności par z ograniczeniami w celu zminimalizowania sumy produktów)
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto również przyjrzeć …
4
Podzakres drzewa czerwonego i czarnego
Próbując naprawić błąd w bibliotece, bezskutecznie szukałem artykułów na temat znajdowania podzakresów na czerwonych i czarnych drzewach. Zastanawiam się nad rozwiązaniem wykorzystującym zamki błyskawiczne i czymś podobnym do zwykłej operacji dołączania stosowanej w algorytmach usuwania niezmiennych struktur danych, ale wciąż zastanawiam się, czy istnieje lepsze podejście, którego nie udało mi …
2
Dokładna formuła dla liczby drzew rozpinających prostokąta
Ten blog mówi o generowaniu „krętych małych labiryntów” za pomocą komputera i ich liczeniu. Wyliczenia można dokonać za pomocą algorytmu Wilsona, aby uzyskać UST , ale nie pamiętam wzoru na ich liczbę. http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike Zasadniczo Twierdzenie o Drzewie Matrycowym stwierdza, że ​​liczba drzew spinających na wykresie jest równa wyznacznikowi macierzy Laplaciana …
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.