Mam grupę n zestawów, dla których muszę obliczyć wartość „unikatowości” lub „podobieństwa”. Jako odpowiedni wskaźnik zdecydowałem się na indeks Jaccard . Niestety indeks Jaccard działa tylko na dwóch zestawach na raz. Aby obliczyć podobieństwo między wszystkimi zbiorami, będzie to wymagało w...
To pojawiło się, gdy próbowałem odpowiedzieć na to pytanie dotyczące minimalizacji długości przewodów . Miałem to nazwać problemem „poligamicznego małżeństwa”, ale internet, tak kocięta. Tak! Załóżmy, że mamy kociąt, które muszą być przyjęte przez ludzi, . Dla każdego kociaka, i każdej osoby...
Algorytm Bellmana-Ford, określa najkrótszą ścieżkę ze źródła, do pozostałych wierzchołków. Początkowo odległość między a wszystkimi innymi wierzchołkami jest ustawiona na . Następnie obliczana jest najkrótsza ścieżka od do każdego wierzchołka; dzieje się tak w przypadku iteracji . Moje pytania...
Próbuję rozwiązać problem z grafem (nie jest to praca domowa, tylko po to, aby ćwiczyć swoje umiejętności). Podaje się DAG , gdzie jest zbiorem wierzchołków, a krawędziami. Wykres jest reprezentowany jako lista przylegania, więc jest zbiorem zawierającym wszystkie połączenia . Moim zadaniem jest...
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu...
Załóżmy, że podano różnych liczb całkowitych , takich, że dla pewnej stałej i dla wszystkich .nnna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iii Interesuje nas znalezienie zliczeń wszystkich możliwych sum . ( jest dozwolone).Sij=ai+ajSij=ai+ajS_{ij} =...
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...
Czytałem tę książkę dla mojej klasy, Randomized Algorytmy. W tej książce znajduje się cała sekcja poświęcona znalezieniu mediany tablicy za pomocą losowego wyboru, co prowadzi do bardziej wydajnego algorytmu. Teraz chciałem wiedzieć, czy istnieją jakieś praktyczne zastosowania tego algorytmu w...
Załóżmy, że mam gdzieś na fiordach Norwegii autonomiczny statek powierzchniowy zasilany energią słoneczną, wyposażony w całkiem nowy zestaw map, odbiornik GPS i nie ma możliwości przesyłania szczegółowych poleceń ode mnie. Statek ten musi dotrzeć na wyspę Hainan w najwcześniejszym możliwym...
Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .kkkQ={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k...
Programowanie dynamiczne może skrócić czas potrzebny do wykonania algorytmu rekurencyjnego. Wiem, że programowanie dynamiczne może pomóc w zmniejszeniu złożoności czasowej algorytmów. Czy ogólne warunki są takie, że spełnienie algorytmu rekurencyjnego oznaczałoby, że zastosowanie programowania...
Zaimplementowałem sortowanie topologiczne na podstawie artykułu z Wikipedii, którego używam do rozwiązywania zależności, ale zwraca ono listę liniową. Jakiego algorytmu mogę użyć do znalezienia niezależnych
Z tego, co przeczytałem w preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Oto definicja PTAS : Wielomianowy schemat aproksymacji czasu ( PTAS ) dla problemu jest...
Strona wikipedii na temat algorytmów mnożenia wspomina o interesującym autorstwa Donalda Knutha . Zasadniczo polega na połączeniu mnożenia transformacji Fouriera ze wstępnie obliczoną tabelą mnożenia wielkości logarytmicznych. Działa w czasie liniowym. Artykuł działa tak, jakby ten algorytm jakoś...
Załóżmy, że ma wykres o M ( G ) do (brak danych) zestawu doskonałych skojarzeń z G . Załóżmy, że ten zestaw nie jest pusty, to jak trudne jest jednorodne losowe pobieranie próbek z M ( G ) ? Co się stanie, jeśli nie mam nic przeciwko rozkładowi zbliżonemu do jednorodnego, ale niezupełnie...
Więc scalanie to algorytm dzielenia i zdobywania. Kiedy patrzyłem na powyższy schemat, zastanawiałem się, czy można w zasadzie ominąć wszystkie kroki podziału. Jeśli iterowałeś po oryginalnej tablicy podczas przeskakiwania o dwa, możesz uzyskać elementy o indeksie i i i + 1 i umieścić je w ich...
Biorąc pod uwagę dwa ciągi, jak możesz sprawdzić, czy są one wzajemną permutacją za pomocą spacji O (1)? Modyfikowanie ciągów znaków nie jest w żaden sposób dozwolone. Uwaga: odstęp O (1) w stosunku do długości łańcucha ORAZ wielkości
Właśnie znalazłem to zdanie na stronie 6 „Komputerów i nienaruszalności” Garey i Johnsona. Każdy algorytm, którego funkcja złożoności czasowej nie może być tak ograniczona, nazywa się algorytmem wykładniczym w czasie (chociaż należy zauważyć, że ta definicja obejmuje pewne funkcje nieliniowej...
Istnieje kosze The th bin zawierać kulki. Kulki ma kolory istnieją kulki koloru . Niech .i a i n a i i m = ∑ n i = 1 a innniiiaiaia_innnaiaia_iiiim=∑ni=1aim=∑i=1naim=\sum_{i=1}^n a_i Zamiana polega na wzięciu piłki z jednego kosza i zamianie z piłką z innego kosza. Chcemy minimalnej liczby zamian,...
Niech język będzie regularny.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y )LL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , gdzie | .x ∈ X , y ∈ Y }X⋅Y={xyX⋅Y={xyX \cdot Y =...