Pytania otagowane jako algorithms

Algorytm jest sekwencją dobrze zdefiniowanych kroków, które definiują abstrakcyjne rozwiązanie problemu. Użyj tego tagu, gdy Twój problem dotyczy projektowania i analizy algorytmów.

2
Kiedy połączenie dwóch regularnych języków jest jednoznaczne?
Biorąc pod uwagę języki i , powiedzmy, że ich konkatenacja jest jednoznaczna, jeśli dla wszystkich słów istnieje dokładnie jeden rozkład z i , a niejednoznaczny inaczej. (Nie wiem, czy istnieje ustalony termin dla tej właściwości - trudna rzecz do wyszukania!) Jako trywialny przykład konkatenacja z samym sobą jest niejednoznaczna ( …
1
Zagubiony w „jednokierunkowym” koncercie
Ty i przyjaciel zgubiliście się na linii na koncercie, i żaden nie jest pewien, który z was jest dalej. Formalnie każda z nich ma jakąś całkowitą współrzędną i może podążać w kierunku wyższej współrzędnej lub pozostać na miejscu. Zakładając, że ty i twój przyjaciel przestrzegacie dokładnie tego samego algorytmu (i …
2
Podejście punktowe do komputerowych przeciwników, którzy potrzebują równowagi
To pytanie dotyczy podejścia do przeciwników komputerowych, które stworzyłem i albo są obecnie używane, albo planuje się ich użycie w kilku grach komputerowych. tło W ubiegłym roku, kiedy próbowałem ulepszyć komputerowego przeciwnika w grze o nazwie „Saper Flagi” (krótki opis: Turowa wersja Saper dla wielu graczy, w której musisz wziąć …
2
W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie?
Używając A * (lub innego algorytmu znajdowania najlepszej ścieżki), mówimy, że zastosowana heurystyka powinna być dopuszczalna , to znaczy nigdy nie powinna przeceniać faktycznej długości ścieżki rozwiązania (lub ruchów). W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie? Najlepiej szukam intuicyjnego wyjaśnienia. Jeśli chcesz, możesz wyjaśnić za pomocą heurystycznej odległości 8-puzzle …
1
Przekształcanie arbitralnej osłony w osłonę wierzchołków
Podano wykres płaski G=(V,E)G=(V,E)G=(V,E) i niech oznacza jego osadzenie w płaszczyźnie st, każda krawędź ma długość . Mam ponadto zestaw punktów, w których każdy punkt jest zawarty w . Ponadto, dla dowolnego punktu w istnieje z odległością geodezyjną do co najwyżej jeden. (Odległość jest mierzona jako najkrótsza odległość w obrębie …
2
Pokoloruj drzewo binarne, aby było czerwono-czarnym drzewem
Częstym pytaniem w rozmowie kwalifikacyjnej jest podanie algorytmu określającego, czy dane drzewo binarne ma zrównoważoną wysokość (definicja drzewa AVL). Zastanawiałem się, czy możemy zrobić coś podobnego z czerwono-czarnymi drzewami. Biorąc pod uwagę dowolne bezbarwne drzewo binarne (z węzłami NULL), czy istnieje „szybki” algorytm, który może określić, czy możemy pokolorować (i …
1
Brutalna siła złożoności algorytmu triangulacji Delaunaya
W książce „Geometria obliczeniowa: algorytmy i zastosowania” autorstwa Mark de Berg i wsp. Istnieje bardzo prosty algorytm brutalnej siły do ​​obliczania triangulacji Delaunaya. Algorytm wykorzystuje pojęcie niedozwolonych krawędzi - krawędzi, które mogą nie pojawić się w prawidłowej triangulacji Delaunaya i muszą zostać zastąpione innymi krawędziami. Na każdym kroku algorytm po …
1
Algorytm politime i polyspace do wyznaczania wiodącego przecięcia n dyskretnych funkcji monotonicznych
Some frontmatter: Jestem informatykiem rekreacyjnym i zatrudnionym inżynierem oprogramowania. Więc przepraszam, jeśli to podpowiedź wydaje się być trochę poza lewym polem - rutynowo gram z matematycznymi symulacjami i otwieram problemy, gdy nie mam nic lepszego do roboty. Podczas zabawy hipotezą Riemanna ustaliłem, że pierwszą lukę można zredukować do relacji powtarzalności …
2
Środowisko uruchomieniowe optymalnego algorytmu chciwości
|P|=n|P|=n|P| = nkkkkkknnnC={c1,c2,…,ck}C={c1,c2,…,ck}C = \{ c_1,c_2,\ldots,c_k\}kkkDcost(C)=maximinjD(pi,cj)cost(C)=maximinjD(pi,cj)\text{cost}(C) = \max_i \min_j D(p_i, c_j)DDDoznacza odległość euklidesową między punktem wejściowym a punktem środkowym . Każdy punkt przypisuje się do najbliższego centrum gromady grupującego wierzchołki w różnych skupisk.c j kpipip_icjcjc_jkkk Problem znany jest jako (dyskretny) problem klastrowania i jest to -hard. Można to pokazać z …
2
Jak wdrożyć algorytm AO *?
Zauważyłem, że podczas implementacji algorytmów wyszukiwania stosowane są różne struktury danych. Na przykład używamy kolejek do implementacji pierwszego wyszukiwania szerokości, stosów do implementacji wyszukiwania z głębokości pierwszej i stosów min do implementacji algorytmu A * . W takich przypadkach nie musimy jawnie budować drzewa wyszukiwania. Ale nie mogę znaleźć prostej …
1
Metody oceny systemu pisemnych reguł
Próbowałem wymyślić system, który oceniałby regulaminy organizacji w celu ustalenia ich podstawowej logiki. Myślę, że system predykatów pierwszego rzędu działałby w celu reprezentowania reguł, które mogłyby być przetłumaczone z tekstu za pomocą tagowania części mowy i innych technik NLP. Czy istnieje systematyczny sposób interpretacji reguł logicznych pierwszego rzędu jako całości …
2
Oblicz maksymalny przepływ z minimalnego cięcia
Wiemy, że obliczenie maksymalnego przepływu lub. minimalne ograniczenie sieci o przepustowości jest równoważne; por. twierdzenie o maksymalnym przepływie min. cięcie . Mamy (mniej lub bardziej wydajne) algorytmy obliczania maksymalnych przepływów, a obliczanie minimalnego cięcia przy maksymalnym przepływie nie jest ani trudne, ani drogie. Ale co na odwrót? Biorąc pod uwagę …
1
Obliczenia kwantowe - związek między modelem Hamiltonian a modelem Unitary
Podczas opracowywania algorytmów obliczeń kwantowych zauważyłem, że istnieją dwa podstawowe modele, w których odbywa się to. Niektóre algorytmy - takie jak problem drzewa Hamiltonian NAND (Farhi, Goldstone, Guttman) - działają poprzez zaprojektowanie stanu hamiltonowskiego i pewnego stanu początkowego, a następnie umożliwienie ewolucji systemu zgodnie z równaniem Schrödingera przez pewien czas …
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.