Pytania otagowane jako heuristics

Heurystyka to procedura, która może być stosowana ogólnie do wielu problemów (na przykład zstępowanie gradientowe, optymalizacja naprzemienna, symulowane wyżarzanie), ale zazwyczaj nie ma formalnych gwarancji związanych z jej użyciem.

5
Jaka jest maksymalna liczba trwałych małżeństw w przypadku problemu stabilnego małżeństwa?
Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy możemy stworzyć listę preferencji, która daje maksymalną liczbę trwałych małżeństw? Jaka jest górna granica takiej liczby?nnn
5
Algorytmy szybkiej prędkości
Chciałbym obliczyć szerokość wykresu. Istnieją naprawdę dobre heurystyki dla innych problemów związanych z grafem NP-twardym, takich jak VF2 dla izomorfizmu podgraficznego , z kodem dostępnym na przykład w igraph . Wypróbowałem je na moich wykresach i okazało się, że działają bardzo szybko dla moich danych. Czy są jakieś szybkie algorytmy …
4
Teoretyczne badanie metod zejścia ze współrzędnymi
Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście współrzędnych odbywa się cyklicznie przez współrzędne, ustalając wszystko oprócz wybranego i minimalizując wzdłuż …
2
Zdecentralizowany algorytm do określania wpływowych węzłów w sieciach społecznościowych
W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.kkk Zasadniczo algorytm wygląda następująco: S=empty setS=empty setS = {\rm empty~set} wybierz węzeł o najwyższym indywidualnym wpływie, nazwij go ; S = S ∪ v 1v1v1v_1S=S∪v1S=S∪v1S …
3
Skuteczne zastosowanie metod rozgałęzionych i związanych z problemami trudnymi dla NP
Rozgałęzienie i powiązanie to skuteczna heurystyka dla problemów wyszukiwania, a Wikipedia wymienia wiele trudnych problemów, w których zastosowano rozgałęzienie i powiązanie. Jednak nie udało mi się znaleźć referencji sugerujących, że jest to więcej niż „jedna metoda” rozwiązania tych problemów. Anegdotycznie słyszałem, że jedne z najlepszych heurystyki dla programowania SAT i …
1
Zrozumienie wydajności solverów QFBV SMT
Solwery SMT, takie jak Z3 lub Boolector, wykorzystują złożony zestaw heurystyk do rozwiązywania problemów. Jednak bardzo utrudnia to przewidywanie wydajności takiego rozwiązania. Moje pytanie brzmi zatem: Pytanie Czy istnieje sposób na zrozumienie lub uzyskanie wglądu w wydajność solvera SMT dla konkretnego w teorii bitwektorów bez kwantyfikatora (QFBV)? Obejmuje to także …
2
Lista problemów trudnych dla NP, w których prowadzone są aktywne badania w zakresie praktycznej heurystyki
Szukam listy problemów związanych z optymalizacją trudnych NP, gdzie są aktywne badania w praktycznej heurystyce w celu ich rozwiązania i istnieją wspólne testy porównawcze, które ludzie próbują pokonać. Przykłady obejmują: rekonstrukcja drzewa filogenetycznego (heurystyczny na przykład tutaj ) komiwojażera (nie tak aktywny, ale LKH jest dość dobrze znana) Mówiąc dokładniej, …
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
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.