Pytania otagowane jako graph-algorithms

Algorytmy na wykresach, z wyłączeniem heurystyki.

4
Algorytmy aproksymacyjne dla metrycznego TSP
Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż 1231.51.51.5 w czasie wielomianowym. Czy coś wiadomo na temat znajdowania rozwiązań aproksymacyjnych w czasie wykładniczym (na przykład mniej niż2nkroków z tylko przestrzenią wielomianową)? Np. W jakim czasie i przestrzeni możemy znaleźć trasę, której odległość …
4
Przykłady, w których wyjątkowość rozwiązania ułatwia znalezienie
Klasa złożoności składa się z tych N P -Problemy że może być określana przez wielomian czasu niedeterministycznych maszynie Turinga, który ma co najwyżej jedną ścieżkę akceptacji obliczeniowej. Oznacza to, że rozwiązanie, jeśli w ogóle, jest wyjątkowe w tym sensie. Uważa się wysoce nieprawdopodobne, że wszystkie U P -Problemy są P …
3
Czy któryś z najnowszych algorytmów maksymalnego przepływu jest praktyczny?
W przypadku problemu maksymalnego przepływu wydaje się, że istnieje wiele bardzo wyrafinowanych algorytmów, przy czym co najmniej jeden opracowano dopiero w zeszłym roku. Max przepływy Orlina w czasie O (mn) lub lepiej daje algorytm działający w O (VE). Z drugiej strony algorytmy, które najczęściej widzę, są zaimplementowane (nie twierdzę, że …
16
Trudno wyglądające problemy algorytmiczne ułatwiane przez twierdzenia
Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe) twierdzenia. Ma to na celu zilustrowanie uczniom, że uczenie się większej …
4
Jak znaleźć cykle, które razem obejmują największą liczbę nieudostępnionych krawędzi na ukierunkowanym wykresie?
Nie jestem teoretykiem informatyki, ale myślę, że ten problem ze światem rzeczywistym należy tutaj. Problem Moja firma ma kilka jednostek w całym kraju. Zaoferowaliśmy pracownikom możliwość pracy na innej jednostce. Ale jest warunek: łączna liczba pracowników w jednostce nie może się zmienić. Oznacza to: Pozwolimy pracownikowi opuścić jego jednostkę, jeśli …
3
Złożoność „jest wykresem produkt”
To pytanie powstaje z czystej ciekawości (pojawiło się podczas myślenia o odtasowaniu łańcucha , ale nie jestem pewien, czy jest rzeczywiście powiązane), więc mam nadzieję, że jest odpowiednie. Istnieje wiele produktów graficznych i interesuje mnie którykolwiek z nich. Jaka jest złożoność ustalenia, czy wykres jest izomorficzny w stosunku do nietrywialnego …
2
Złożoność ustalenia, czy ustalony wykres jest niewielki w stosunku do innego
W rezultacie przez Robertson Seymour wykazuje algorytm do testowania, czy stałej wykres jest minor . Mam dwa i pół pytania na ten temat:O ( n3))O(n3))O(n^3)solsolGH.H.H 1) Wygląda na to, że od tego czasu wprowadzono ulepszenia tego algorytmu. Jaki jest obecnie najbardziej znany algorytm? 2a) Co ludzie przypuszczają, że są optymalnym …
5
Problem z minimalną łącznością z klapką
Podczas gry z moim GPS sformułowałem następujący problem. Oto on: Niech będzie grafem ukierunkowanym, tak że jeśli to , tj. jest orientacją leżącego u jego podstaw wykresu niekierowanego. Rozważ następujące operacje:e = ( u , v ) ∈ E ( v , u ) ∉ E GG ( V, E)G(V,E)G(V,E)e …
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
1
Losowa złożoność zapytań problemu drzew połączonych
Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej, który składa się z dwóch kompletnych dwójkowych drzewek głębokości n, których …
3
Problemy z optymalizacją przy dobrej charakterystyce, ale bez algorytmu czasu wielomianowego
Rozważ problemy z optymalizacją w poniższym formularzu. Niech f(x)f(x)f(x) będzie funkcją obliczalną w czasie wielomianowym, która odwzorowuje ciąg xxx na liczbę wymierną. Problem optymalizacji jest następujący: jaka jest maksymalna wartość f(x)f(x)f(x) ponad nnn bitowych ciągów xxx ? gggmaxxf(x)=minyg(y)maxxf(x)=minyg(y)\max_x f(x) = \min_y g(y)xxxnnnyyymmmnnnmmm Wiele naturalnych i ważnych problemów związanych z 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.