zastanawiam się, czy są jakieś podejścia do formułowania problemu trasy pojazdu z systemem Windows-Time ( VRPTW ) (jako problemem decyzyjnym) jako instancji SAT / SMT? (alternatywnie: TSP) Na przykład: „Czy istnieje prawidłowe rozwiązanie odwiedzające wszystkich klientów w ich ramach czasowych...
Kiedy przejrzałem „ Dynamiczne podejście programistyczne do problemów z sekwencjonowaniem ” autorstwa Michaela Helda i Richarda M. Karpa, wpadłem na następujące pytanie: dlaczego złożoność ich algorytmu dla TSP jest (s. 199), mam na myśli skąd biorą współczynnik ? Jeśli dobrze zrozumiałem, k-1...
W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości. Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją. 1) Zaczynając od minimalnego drzewa...
Miałem trudności ze znalezieniem algorytmu lub opublikowaniem artykułów na temat triangulacji samoblokującego się wielokąta (również wielokąta o strukturze dziury). Czy ktoś może poprowadzić mnie do znalezienia opublikowanej pracy / algorytmu, proszę? PS: proszę odpowiednio oznaczyć to pytanie,...
Odnoszę się tutaj do pytania: potężne algorytmy zbyt złożone, aby je zaimplementować . Jeśli algorytm jest potężny, ale zbyt skomplikowany, aby go wdrożyć, skąd możesz mieć pewność, że algorytm jest poprawny? Bez implementacji nie będzie można przetestować algorytmu w scenariuszu ze świata...
Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - a?...
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...
Mamy zestaw, LLL, list elementów z zestawu N= { 1 , 2 , 3 , . . . ,n}N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n \}. Każdy element zNNN pojawia się na jednej liście w LLL. Szukam struktury danych, która może wykonać następujące aktualizacje: c o n c at(x,y)concat(x,y)concat(x, y) : konkatenuje listę...
Zdefiniuj siatkę w 3D jako połączoną kolekcję czworościanów z rozłącznymi wnętrzami (więc czworościany mają tylko k-face, k ≤ 2k≤2)k \le 2). Czy na podstawie dowolnego wykresu istnieje skuteczna procedura sprawdzania, czy można go osadzić jako siatkę? Osadzanie polega na odwzorowaniu wierzchołków...
Byłbym wdzięczny za wszelkie wskazówki lub warunki, które mogłyby doprowadzić mnie do właściwego kierunku. Mamy ukierunkowany wykres G = ( V, E)G=(V,E)G=(V,E) i długości lI jlijl_{ij} dla każdej krawędzi I jijijktóre można uznać za pozytywne. Istnieje specjalny węzeł początkowysss i węzeł końcowy...
W instrumentu Capacitated Lokalizacja problem (CFLP) , daje nam szereg klientów oraz zestaw potencjalnych obiektów . Każdy klient ma żądanie które musi być obsługiwane przez jedno lub więcej otwartych obiektów. Każdy obiekt ma koszt otwarcia i ma pojemność , które jest popyt, że maksymalny zakład...
Interesuję się, gdy dowiaduję się więcej o algorytmach i strukturach danych nieobsługiwanych przez pamięć podręczną, ale jest tak wiele dokumentów, że tak naprawdę nie wiem od czego zacząć. Znalazłem oryginalną tezę Prokupa na ten temat, co wydaje się dobrym punktem wyjścia, ale jeśli istnieje...
Zastanawiam się, czy istnieją systematyczne badania sum kwadratowych form kwadratowych, podobnych do form kwadratowych, co praktycznie znajduje odzwierciedlenie w rozkładzie wartości własnych (co ma ogromne praktyczne implikacje). Kilka przykładów związanych ze znaczeniem pytania. Analizy...
Mam rodzinę problemów z programowaniem liniowym: maksymalizuj c′xdo′xc' x z zastrzeżeniem Ax≤bZAx≤bA x\le b, x≥0x≥0x\ge0. ElementyAZAA, bbb, i cdoc są liczbami całkowitymi nieujemnymi, cdocściśle pozytywne. (xxx powinien być również integralny, ale będę się tym martwić później). W mojej aplikacji...
Biorąc podmodular funkcji faff na Ω =X1∪X2)Ω=X1∪X2\Omega=X_1\cup X_2 gdzie X1X1X_1 i X2)X2X_2 są rozłączni i fa( S) =fa1( S∩X1) +fa2)( S∩X2))f(S)=f1(S∩X1)+f2(S∩X2)f(S)=f_1(S\cap X_1)+f_2(S\cap X_2). Tutajfa1f1f_1 i fa2)f2f_2 są podmodularne X1X1X_1 i X2)X2X_2 odpowiednio. Tutaj...
Czytam stary artykuł MC Golumbica na temat wykresów EPT (przecięcie krawędzi ścieżek na drzewie). W artykule pokazano, że liczba maksymalnych klików wystąpienia wykresu EPT jest wielomianowa. Stwierdza, że jeśli wyrocznia zgłasza, że wykressolsolG jest wykresem EPT, możliwe jest znalezienie...
(Przepraszamy, jeśli jest to źle umieszczone lub zbyt szerokie. Jestem otwarty na sugestie, jak to przeformułować). Interesuje mnie prześledzenie „starożytnej” historii algorytmów maksymalnego przepływu i ogólnie dyskretnych algorytmów optymalizacji. Ford-Fulkerson jest moim słomkowym punktem...
Załóżmy, że mam listę XX\cal X podzbiorów {1,...,n}{1,...,n}\{1, ..., n\}. W razie potrzeby mogę wykonać wstępne przetwarzanie na tej liście. Po tym wstępnym przetwarzaniu otrzymuję kolejny zestawA⊆{1,...,n}A⊆{1,...,n}A \subseteq \{1, ..., n \}. Chcę zidentyfikować żadnych zestawów z .B∈XB∈XB \in...
Wyszukiwarki coraz częściej polegają na zbieraczach informacji, jednak kryteria stosowane przez wyszukiwarki do oceniania wyników są niejasne dla użytkowników. W jaki sposób użytkownicy mogą być pewni, że ich wyniki nie są stronnicze lub w jakikolwiek sposób modyfikowane, aby zwiększyć...
Moje pytanie jest trochę niejasne. Zastanawiam się, czy (i jak) możemy zastosować pojęcie szerokości do problemów z upakowaniem na wykresach. Byłbym zadowolony z wszelkich spostrzeżeń lub odniesień do wcześniejszych prac badawczych na ten temat (zakładając, że jest to jakaś relacja)....