Pytania otagowane jako optimization

ogólne pytania dotyczące wyboru najlepszego elementu z zestawu dostępnych alternatyw.

2
Algorytm czasu liniowego znajdowania przesuniętego maks
Załóżmy, że otrzymujemy tablicę A[1..n]A[1..n]A[1..n] zawierającą nieujemne liczby całkowite (niekoniecznie różne). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w najgorszym przypadku.AAAmmmO(nlgn)O(nlg⁡n)O(n \lg n) Czy można to zrobić lepiej? Czy możemy obliczyć czasie liniowym?mmm Moje główne pytanie to powyższe. …
2
Łatwy w optymalizacji, ale trudny do oceny
Czy są znane naturalne przykłady problemów z optymalizacją, dla których znacznie łatwiej jest stworzyć optymalne rozwiązanie niż ocenić jakość danego rozwiązania kandydującego? Ze względu na konkretność możemy rozważyć rozwiązania problemów optymalizacji w postaci wielomianowej w postaci: „biorąc x, zminimalizuj ”, gdzie f : { 0 , 1 } ∗ × …
1
Minimalizacja programu
Minimalizacja obwodu to problem polegający na zminimalizowaniu rozmiaru danego obwodu. Czy jest coś podobnego do programów ogólnych? W szczególności moje pytanie brzmi - Czy istnieją algorytmy minimalizujące liczbę instrukcji dla danego programu? Wiem, że to nierozstrzygalny problem, ale nie szukam rozwiązania, które zwróci coś optymalnego. Podczas gdy można zastosować wcześniej …
2
Sortowanie punktów, aby zminimalizować minimalną odległość euklidesową między kolejnymi punktami
Biorąc pod uwagę zestaw punktów w trójwymiarowej przestrzeni kartezjańskiej, szukam algorytmu, który posortuje te punkty, tak aby zminimalizować minimalną odległość euklidesową między dwoma kolejnymi punktami. Byłoby również korzystne, gdyby algorytm miał tendencję do wyższej średniej odległości euklidesowej między kolejnymi punktami.
3
Zastosowania MCTS / UCT
MCTS / UCT to metoda wyszukiwania drzewa gry, która wykorzystuje algorytm bandyty do wybierania obiecujących węzłów do eksploracji. Gry są rozgrywane losowo, a węzły prowadzące do większej liczby zwycięstw są eksplorowane bardziej intensywnie. Algorytm bandytów utrzymuje równowagę między eksploracją węzłów o wysokich wskaźnikach wygranych a eksploracją nieznanych węzłów (i w …
1
Czy znana jest złożoność tego problemu?
Niech będzie wykresem. Zestaw wierzchołek nazywa krytyczna jeśli i nie wierzchołek w przylega dokładnie jeden wierzchołek w . Problemem jest znalezienie zbiór wierzchołków z co najmniej taką wielkość, że każdego niezbędny zestaw .G = ( V, E)G=(V,E)G=(V,E)X⊆ V.X⊆VX\subseteq VX≠ ∅X≠∅X\neq\emptysetV.∖ XV∖XV\setminus XXXXS.⊆ V.S⊆VS\subseteq VS.∩ X≠ ∅S∩X≠∅S\cap X\neq\emptysetXXX Problem ma następującą …
2
Generowanie interesujących problemów optymalizacji kombinatorycznej
Prowadzę kurs meta-heurystyki i muszę wygenerować ciekawe przykłady klasycznych problemów kombinatorycznych dla projektu semestralnego. Skupmy się na TSP. Zajmujemy się wykresami wymiarów200200200i większe. Próbowałem oczywiście wygenerować wykres z macierzą kosztów z wartościami pobranymi z losowegoU( 0 , 1 )U(0,1)U(0,1)i odkrył, że (zgodnie z oczekiwaniami) histogram kosztu ścieżki (sporządzony przez próbkowanie …
1
Minimalne drzewo opinające dla wszystkich dopasowań wierzchołków
Natknąłem się na ten problem z dopasowaniem, dla którego nie jestem w stanie zapisać algorytmu czasu wielomianowego. Pozwolić P,QP,QP, Qbyć kompletnymi wykresami ważonymi z zestawami wierzchołków odpowiednio i , gdzie . Ponadto pozwalają i być funkcje ciężar na krawędziach i , odpowiednio.PVPVP_VQVQVQ_V|PV|=|QV|=n|PV|=|QV|=n|P_V| = |Q_V|=nwPwPw_PwQwQw_QPPPQQQ W przypadku modyfikujemy w następujący sposób: …
2
Jak / dlaczego systemy liniowe są tak ważne dla informatyki?
Zainteresowałem się optymalizacją matematyczną całkiem niedawno i bardzo mi się podoba. Wydaje się, że wiele problemów związanych z optymalizacją można łatwo wyrazić i rozwiązać jako programy liniowe (np. Przepływy sieciowe, pokrycie krawędzi / wierzchołków, podróżujący sprzedawca itp.) Wiem, że niektóre z nich są trudne do NP, ale chodzi o to, …
1
Heurystyka dla optymalizacji
Ponieważ jest piątek, czas na pytanie CW. Szukam heurystyki, która ma szerokie zastosowanie w problemach związanych z optymalizacją. Aby ograniczyć zakres do bardziej „przyjaznej teorii” heurystyki, oto zasady (niektóre arbitralne, niektóre nie) Powinna to być dobrze zdefiniowana metoda bez wielu parametrów i z konkretnym czasem pracy (może na iterację) Powinny …
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.