Pytania otagowane jako trees

Pytania dotyczące specjalnego rodzaju wykresów, a mianowicie wykresów połączonych i bez cykli.

3
Najdłuższa ścieżka w niekierowanym drzewie z tylko jednym przejściem
Istnieje standardowy algorytm znajdowania najdłuższej ścieżki w nieukierunkowanych drzewach przy użyciu dwóch wyszukiwań w pierwszej kolejności: Uruchom DFS od losowego wierzchołka i znajdź od niego najdalszy wierzchołek; powiedzmy, że to v ′ .vvvv′v′v' Teraz uruchom DFS od aby znaleźć wierzchołek najdalej od niego. Ta ścieżka jest najdłuższą ścieżką na wykresie.v′v′v' …
2
Jaka jest różnica między drzewami radix a próbami Patricii?
Uczę się o drzewach Radix (inaczej skompresowanych próbach) i Patricii, ale znajduję sprzeczne informacje na temat tego, czy faktycznie są one takie same. Drzewo radix można uzyskać z normalnej (nieskompresowanej) trie, łącząc węzły z ich rodzicami, gdy węzły są jedynym dzieckiem. Dotyczy to również prób Patricii. W jaki sposób dwie …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
7
Algorytm znajdowania średnicy drzewa za pomocą BFS / DFS. Dlaczego to działa?
To łącze zapewnia algorytm znajdowania średnicy drzewa bezkierunkowego za pomocą BFS / DFS . Zreasumowanie: Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa. Dlaczego to działa? Strona 2 tego zawiera uzasadnienie, ale jest …
5
Skuteczna kompresja nieoznakowanych drzew
Rozważ nieoznakowane, ukorzenione drzewa binarne. Możemy skompresować takich drzew: gdy istnieją wskaźniki do poddrzew i T ' z T = T ' (ustne = jak równość strukturalne), możemy zapisać (wlog) T i zastąpić wszystkie wskaźniki do T ' z wskazówki dla T . Zobacz odpowiedź uli na przykład.T.TTT.′T′T'T.= T′T=T′T = …
1
Dlaczego programowanie funkcjonalne nie badało dynamicznych drzew?
Drzewa dynamiczne odgrywają ważną rolę w rozwiązywaniu problemów, takich jak przepływy sieciowe, wykresy dynamiczne, problemy kombinatoryczne („Drzewa dynamiczne w praktyce” Tarjana i Wernecka) oraz ostatnio łączone słowniki („Prosty słownik łączący” Adama Karczmarza), Przez drzewa dynamiczne odwołuję się do definicji podanej w dokumencie Sleator & Tarjan zatytułowanym „Struktura danych dla drzew …
1
O „Średniej wysokości posadzonych platanów” Knuth, de Bruijn i Rice (1972)
Staram się czerpać z klasycznej pracy tytułowej tylko elementarne środki (bez funkcji generujących, bez złożonej analizy, bez analizy Fouriera), choć ze znacznie mniejszą precyzją. Krótko mówiąc, „tylko” chcę udowodnić, że średnia wysokość drzewa z węzłami (to znaczy maksymalną liczbą węzłów od korzenia do liścia) spełnia .hnhnh_nnnnhn∼πn−−−√hn∼πnh_n \sim \sqrt{\pi n} Zarys …
3
Czy drzewo można przemierzać bez rekurencji, stosu lub kolejki, a jedynie garść wskazówek?
Pół dekady temu siedziałem w klasie struktur danych, w której profesor oferował dodatkowy kredyt, jeśli ktokolwiek mógł przemierzać drzewo bez użycia rekurencji, stosu, kolejki itp. (Lub innych podobnych struktur danych) i tylko kilka wskazówek. Wpadłem na to, co uważałem za oczywistą odpowiedź na to pytanie, które ostatecznie zostało zaakceptowane przez …
2
Dowód poprawności algorytmu zachłannego dla minimalnego pokrycia wierzchołka drzewa
Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS. Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków). Dla każdego węzła wewnętrznego: jeśli nie zostanie wybrane żadne z jego elementów podrzędnych, wybierz ten węzeł. Jak udowodnić, że …
2
Algorytm liniowego oznaczania czasu dla drzewa?
Mam drzewo bezkierunkowe, którego wierzchołki chcę opisać. Węzły liści powinny być oznaczone jako jeden. Następnie załóżmy, że liście zostały usunięte. W drzewie, które pozostaje, liście powinny być oznaczone jako dwa. Proces ten trwa w oczywisty sposób, dopóki wszystkie wierzchołki nie będą miały etykiety. Powodem tego jest to, że chcę przechowywać …
12 algorithms  trees 
1
Struktura danych dla mapy w odstępach czasu
Niech będzie liczbą całkowitą, a oznacza zbiór wszystkich liczb całkowitych. Niech oznacza przedział liczb całkowitych .nnnZZ\mathbb{Z}[a,b][a,b][a,b]{a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} Szukam struktury danych do reprezentowania mapy . Chcę, aby struktura danych obsługiwała następujące operacje:f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} get(i)get(i)\text{get}(i) should return f(i)f(i)f(i). set([a,b],y)set([a,b],y)\text{set}([a,b],y) should update fff so that f(a)=f(a+1)=⋯=f(b)=yf(a)=f(a+1)=⋯=f(b)=yf(a)=f(a+1)=\cdots=f(b)=y, i.e., update fff to a new map …
1
Jaka jest szansa, że ​​ten kod się zakończy?
Napisałem ten kod w Pythonie i zastanawiałem się, czy czasami po prostu się nie kończy (zakładając, że mamy nieskończoną pamięć / czas i nie ma ograniczenia głębokości rekurencji). Intuicyjnie myślisz, że kończy się, ponieważ w pewnym momencie musisz mieć szczęście , a jeśli się nie skończy, masz nieskończoną ilość czasu …
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.