Pytania otagowane jako optimization

Pytania dotyczące problemów, które wiążą się z wyborem najlepszego elementu z pewnego zestawu dostępnych alternatyw oraz metod ich rozwiązywania.

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 
2
Sprzedawanie bloków czasu
Biorąc pod uwagę nnn przedziałów czasowych, które kkk ludzie chcą kupić. Osoba iii ma wartość h ( i , j ) ≥ 0h(i,j)≥0h(i,j)\geq 0 dla każdej szczeliny czasowej jjj . Każda osoba może kupić tylko jeden kolejny blok czasu, który może być pusty. Czy istnieje algorytm wielomianowy do obliczania maksymalnej …
2
Wersja optymalizacyjna problemów decyzyjnych
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Wiadomo, że każdy problem optymalizacji / wyszukiwania ma równoważny problem decyzyjny. Na przykład problem najkrótszej ścieżki Optymalizacja / Wersja: Biorąc pod uwagę nieukierunkowane nieważony wykres a …
5
Dlaczego osoby o niskiej sprawności mają szansę przeżyć do następnego pokolenia?
Obecnie czytam i obserwuję algorytm genetyczny i uważam go za bardzo interesujący (nie miałem okazji go studiować, gdy byłem na uniwersytecie). Rozumiem, że mutacje oparte są na prawdopodobieństwie (losowość jest źródłem ewolucji), ale nie rozumiem, dlaczego przetrwanie. Z tego, co rozumiem, osoba która ma sprawność fizyczną tak jak dla innej …
2
Wydajny algorytm do „sumowania” zestawu sum
Biorąc pod uwagę zbiór wielu liczb naturalnych X, rozważ zestaw wszystkich możliwych sum: sums(X)={∑i∈Ai|A⊆X}sums(X)={∑i∈Ai|A⊆X}\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\} Na przykład podczas gdy .sumy ( { 1 , 1 } ) = { 0 , 1 , 2 }sums({1,5})={0,1,5,6}sums({1,5})={0,1,5,6}\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}sums({1,1})={0,1,2}sums({1,1})={0,1,2}\textrm{sums}(\left\{1,1\right\}) = …
2
Zbiorowy problem z rachunkiem
Przy stole jest nnn ludzi. iii th osoba musi zapłacić pipip_i dolarów. Niektórzy ludzie nie mają odpowiednich rachunków, aby zapłacić dokładnie , dlatego opracowali następujący algorytm.pipip_i Po pierwsze, wszyscy kładą na stole część swoich pieniędzy. Następnie każda osoba odbiera nadpłacone pieniądze. Rachunki mają ustalony zestaw nominałów (nie stanowi części danych …
1
Jak fundamentalne są matroidy i greedoidy w projektowaniu algorytmów?
Początkowo wprowadzono matroidy , aby uogólnić pojęcia liniowej niezależności zbioru podzbiorów stosunku do zbioru I podłoża . Niektóre problemy, które zawierają tę strukturę, pozwalają chciwym algorytmom znaleźć optymalne rozwiązania. Koncepcja greedoidów została później wprowadzona w celu uogólnienia tej struktury, aby uchwycić więcej problemów, które pozwalają na znalezienie optymalnych rozwiązań za …
3
Algorytm minimalizujący pole powierzchni, przy danej objętości
Rozważ następujące zadanie algorytmiczne: Dane wejściowe: dodatnia liczba całkowita wraz z podstawową faktoryzacją Znajdź: dodatnie liczby całkowite które minimalizują , z zastrzeżeniem ograniczenia, żennnx,y,zx,y,zx,y,zxy+yz+xzxy+yz+xzxy+yz+xzxyz=nxyz=nxyz=n Jaka jest złożoność tego problemu? Czy istnieje algorytm czasu wielomianowego? Czy to trudne NP? Ten problem zasadniczo pyta: ze wszystkich prostokątnych brył, których objętość wynosi i …
3
Dlaczego problemy związane z NP są tak różne pod względem ich przybliżenia?
Chciałbym rozpocząć pytanie od stwierdzenia, że ​​jestem programistą i nie mam dużego doświadczenia w teorii złożoności. Jedną z rzeczy, które zauważyłem, jest to, że o ile wiele problemów jest NP-zupełnych, o tyle w przypadku problemów z optymalizacją niektóre są znacznie trudniejsze do oszacowania niż inne. Dobrym przykładem jest TSP. Chociaż …
1
Jak spakować wielokąty wewnątrz innego wielokąta?
Zamówiłem kilka skórzanych prześcieradeł, z których chciałbym budować kuglarskie piłki, łącząc ze sobą krawędzie. Używam brył platońskich do kształtowania kulek. Mogę zeskanować skórzane prześcieradła i wygenerować wielokąt zbliżony do kształtu skórzanego prześcieradła (jak wiecie, jest to skóra zwierzęca i nie ma prostokątów). Chciałbym teraz zmaksymalizować rozmiar mojej żonglującej piłki. W …
4
Jak użyć chciwego algorytmu, aby znaleźć malejącą sekwencję najbliższą podanej?
Otrzymujesz n liczb całkowitych wszystkie od do . Pod każdą liczbą całkowitą należy wpisać liczbę całkowitą między a z warunkiem, że tworzą ciąg nie malejący. Zdefiniuj odchylenie takiej sekwencji na . Zaprojektuj algorytm, który znajdzie b_i z minimalnym odchyleniem w czasie wykonywania O (n \ sqrt [4] {l}) .a1,…,ana1,…,ana_1, \ldots, …
6
Czym różni się programowanie dynamiczne od siły Brute?
Czytałem o Programowaniu dynamicznym, kiedy natknąłem się na następujący cytat Algorytm programowania dynamicznego zbada wszystkie możliwe sposoby rozwiązania problemu i wybierze najlepsze rozwiązanie. Dlatego z grubsza możemy myśleć o programowaniu dynamicznym jako inteligentnej metodzie brutalnej siły, która pozwala nam przejść przez wszystkie możliwe rozwiązania, aby wybrać najlepsze . Jeśli zakres …
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.