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.

3
Największa suma podzielna przez n
Zadałem to pytanie na StackOverflow , ale myślę, że tutaj jest bardziej odpowiednie miejsce. Jest to problem od kursu Wprowadzenie do algorytmów : Musisz tablicę aaa z liczb całkowitych dodatnich (tablica nie muszą być sortowane lub elementów unikalnych). Zaproponuj algorytm , aby znaleźć największą sumę elementów, która jest podzielna przez …
4
Biorąc pod uwagę zestaw zestawów, znajdź najmniejsze zestawy zawierające co najmniej jeden element z każdego zestawu
Biorąc pod uwagę zestaw zestawów, chciałbym znaleźć zestaw takie, że każdy zbiór w zawiera co najmniej jeden element . Chciałbym również, aby zawierał jak najmniej elementów, jednocześnie spełniając to kryterium, chociaż może istnieć więcej niż jeden najmniejszy z tą właściwością (rozwiązanie niekoniecznie jest unikalne).S.S.\mathbf{S}M.M.MS.S.SS.S.\mathbf{S}M.M.MM.M.MM.M.M Jako konkretny przykład, załóżmy, że zestaw …
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …
1
Jakie jest optymalne rozwiązanie konkursu TSP Procter and Gamble z 1962 roku?
W 1962 r. Możesz wygrać nagrodę w wysokości 10 000 USD (około 80 000 USD w dzisiejszych pieniądzach), jeśli znajdziesz rozwiązanie problemu euklidesowego sprzedawcy podróżującego zdefiniowanego w 33 miastach. http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html Patrząc na zdjęcie, problem wydaje się dość łatwy. Nie udało mi się jednak znaleźć bardziej szczegółowych zasobów na temat problemu. …
1
Znalezienie maksymalnej faktoryzacji zwykłych języków
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 = \{xyx∈X,y∈Y}x∈X,y∈Y}x \in X, y \in Y\} …
1
Analiza zmodyfikowanej wersji gry karcianej „War”
Prostą grą, w którą zwykle bawią się dzieci, w grę wojenną grają dwie osoby korzystające ze standardowej talii 52 kart do gry. Początkowo talia jest tasowana i wszystkie karty rozdawane są dwóm graczom, dzięki czemu każda z nich ma 26 losowych kart w losowej kolejności. Zakładamy, że gracze mogą badać …
2
MIN-2-XOR-SAT i MAX-2-XOR-SAT: czy są NP-twarde?
Jaka jest złożoność MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} i MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Czy są w P? Czy są twarde NP? Aby sformalizować to dokładniej, pozwól Φ(x)=∧niCi,Φ(x)=∧jandoja,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, gdzie x=(x1,…,xm)x=(x1,…,xm)\mathbf{x} = (x_1,\dots,x_m) a każda klauzula CiCiC_i ma postać (xi⊕xj)(xi⊕xj)(x_i \oplus x_j) lub (xi⊕¬xj)(xi⊕¬xj)(x_i \oplus \neg x_j) . Problem 2-XOR-SAT2-XOR-SAT\text{2-XOR-SAT} polega na znalezieniu przypisania do xx\mathbf{x} które …
1
Czy pakowanie torby prezentów jest łatwiejsze dla Ruperta niż Świętego Mikołaja?
Lub: Czy potrzebujemy Ruperta, aby w ogóle otrzymać prezenty? Pomijając problemy z routingiem, Święty Mikołaj napotyka następujący problem (wiele, wiele razy): Biorąc pod uwagę torbę o pojemności¹ i zestaw prezentów , każdy o rozmiarze , chce uszczęśliwić dzieci . Ze wszystkich list życzeń wie, że potomne wartości prezentują dokładnie bardzo …
3
Optymalna strategia dla abstrakcyjnej gry
W wywiadzie otrzymałem następujący problem (którego już nie udało mi się rozwiązać, nie próbując oszukać mojej przeszłości): Gra rozpoczyna się od dodatniej liczby całkowitej . (Np. ) Liczba ta jest konwertowana na reprezentację binarną, a jest liczbą bitów ustawioną na . (Np. , )A 0 = 1234 N 1 A …
2
Czy ten szczególny przypadek problemu z planowaniem można rozwiązać w czasie liniowym?
Alice, studentka, ma dużo pracy domowej w ciągu najbliższych tygodni. Każda praca domowa zabiera ją dokładnie jednego dnia. Każda pozycja ma również termin i negatywny wpływ na jej oceny (zakładamy liczbę rzeczywistą, punkty bonusowe za przyjęcie założenia porównywalności), jeśli nie dotrzyma terminu. Napisz funkcję, która podając listę (termin, wpływ na …
1
Wybór podzbioru w celu zmaksymalizowania minimalnej odległości między punktami
Mam zestaw punktów i mam odległość między każdym punktem . Odległości te są euklidesowe, ale punkty znajdują się w przestrzeni cech.CCCD(Pi,Pj)D(Pi,Pj)D(P_i,P_j) Z punktów chcę wybrać podzbiór punktów. Zadzwoń do tego podzbioru . Chcę wybrać ten podzbiór tak aby zmaksymalizować odległość minimalna między wszystkimi punktami w nowy zestaw .CCCnnnssssss maxs⊂C|s|=n⎛⎝⎜mini,j∈si≠jD(Pi,Pj)⎞⎠⎟maxs⊂C|s|=n(mini,j∈si≠jD(Pi,Pj)) \max_{\substack{s …
5
Nauka danych a badania operacyjne
Ogólne pytanie, jak sugeruje tytuł, brzmi: Jaka jest różnica między DS a optymalizacją / optymalizacją. Na poziomie koncepcyjnym rozumiem, że DS próbuje wydobywać wiedzę z dostępnych danych i wykorzystuje głównie techniki statystyczne, uczenie maszynowe. Z drugiej strony OR wykorzystuje dane do podejmowania decyzji na podstawie danych, na przykład poprzez optymalizację …
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.