Pytania otagowane jako search-algorithms

Algorytmy wyszukiwania elementu w określonej strukturze danych (najczęściej w drzewie).

8
Przeszukiwanie wykresów: Najpierw szerokość kontra najpierw głębokość
Podczas poszukiwania wykresy istnieją dwa proste algorytmy: szerokość pierwszego i głębokość pierwszego (zazwyczaj przez dodanie wszystkich węzłów adjactent wykres w kolejce (wszerz) lub stosu (głębokość pierwszego)). Czy są jakieś zalety jednego nad drugim? Te, o których mogłem myśleć: Jeśli spodziewasz się, że Twoje dane będą znajdować się dość głęboko na …
3
Dlaczego wyszukiwanie binarne jest szybsze niż wyszukiwanie trójskładnikowe?
Przeszukiwanie tablicy elementów przy użyciu wyszukiwania binarnego zajmuje w najgorszym przypadku iteracje ponieważ na każdym kroku zmniejszamy połowę naszej przestrzeni wyszukiwania. Gdybyśmy zamiast tego użyli „wyszukiwania trójskładnikowego”, dwie trzecie naszej przestrzeni wyszukiwania przy każdej iteracji, więc najgorszy przypadek powinien zająć iteracji ...NNNlog2Nlog2⁡N\log_2 Nlog3N&lt;log2Nlog3⁡N&lt;log2⁡N\log_3 N < \log_2 N Wygląda na to, …
5
Znajdowanie interesujących anagramów
Powiedzieć, że 1 2 ... n i są dwa ciągi o tej samej długości. Anagramming dwóch ciągów bijective mapowania tak, że dla każdego .a1a2…ana1a2…ana_1a_2\ldots a_nb1b2…bnb1b2…bnb_1b_2\ldots b_np:[1…n]→[1…n]p:[1…n]→[1…n]p:[1\ldots n]\to[1\ldots n]ai=bp(i)ai=bp(i)a_i = b_{p(i)}iii Może być więcej niż jedno anagramowanie dla tej samej pary ciągów. Na przykład, jeśli `abcab` mamy i , między innymi.a=a=a=b=b=b=cababp1[1,2,3,4,5]→[4,5,1,2,3]p1[1,2,3,4,5]→[4,5,1,2,3]p_1[1,2,3,4,5]\to[4,5,1,2,3]p2[1,2,3,4,5]→[2,5,1,4,3]p2[1,2,3,4,5]→[2,5,1,4,3]p_2[1,2,3,4,5] …
7
Algorytm znajdowania średnicy drzewa za pomocą BFS / DFS. Dlaczego to działa?
To łącze zapewnia algorytm znajdowania średnicy drzewa bezkierunkowego za pomocą BFS / DFS . Zreasumowanie: Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa. Dlaczego to działa? Strona 2 tego zawiera uzasadnienie, ale jest …
2
Jak znaleźć żonę w supermarkecie?
Jeśli w labiryncie zagubiły się dwie osoby, czy istnieje algorytm, którego oboje mogą użyć do znalezienia siebie nawzajem bez uprzedniego uzgodnienia, jakiego algorytmu będą używać? Myślę, że ten algorytm ma pewne cechy: Każda osoba musi być w stanie wyprowadzić ją za pomocą logiki, która nie przyjmuje żadnych założeń na temat …
7
Jeden element, który różni się dwiema tablicami. Jak znaleźć to skutecznie?
Przygotowuję się do wywiadu na temat programowania i naprawdę nie mogę znaleźć najbardziej skutecznego sposobu rozwiązania tego problemu. Załóżmy, że mamy dwie tablice składające się z liczb nieposortowanych. Tablica 2 zawiera liczbę, której nie ma tablica 1. Obie tablice mają losowo rozmieszczone liczby, niekoniecznie w tej samej kolejności lub przy …
4
Cel szarego węzła w wyszukiwaniu na głębokości pierwszego wykresu
W wielu implementacjach pierwszego wyszukiwania głębokości, które widziałem (na przykład: tutaj ), kod rozróżnia szary wierzchołek (wykryty, ale nie odwiedzono wszystkich jego sąsiadów) i czarny wierzchołek (odkryty i odwiedzono wszystkich jego sąsiadów) . Jaki jest cel tego rozróżnienia? Wygląda na to, że algorytm DFS nigdy nie odwiedzi odwiedzonego wierzchołka, niezależnie …
4
Znajdowanie pary nie nakładających się wektorów bitowych
Daję ci listę wektorów bitowych o szerokości . Twoim celem jest zwrócenie dwóch wektorów bitowych z listy, które nie mają wspólnych 1, lub zgłoszenie, że taka para nie istnieje.n nnkkk Na przykład, jeśli dam ci wówczas jedynym rozwiązaniem jest . Alternatywnie, wejście nie ma rozwiązania. Każda lista zawierająca całkowicie zerowy …
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 …
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 …
2
Czy istnieje jakieś badanie lub teoria łącząca wyszukiwanie binarne i wyszukiwanie interpolacyjne?
Właśnie przeczytałem Czy ten algorytm nadal może być uważany za algorytm wyszukiwania binarnego? i przypomniałem sobie, że kilka lat temu napisałem indeksatora / wyszukaj pliki dziennika, aby znaleźć wpisy dziennika w dużych plikach tekstowych według okna daty / godziny. Robiąc to, postanowiłem spróbować poszukać interpolacji (nie wiedziałem, że tak to …
2
Jakie są najnowocześniejsze algorytmy wyszukiwania ścieżek na ciągłej mapie Ziemi?
Załóżmy, że mam gdzieś na fiordach Norwegii autonomiczny statek powierzchniowy zasilany energią słoneczną, wyposażony w całkiem nowy zestaw map, odbiornik GPS i nie ma możliwości przesyłania szczegółowych poleceń ode mnie. Statek ten musi dotrzeć na wyspę Hainan w najwcześniejszym możliwym momencie. Jakie są deterministyczne algorytmy wyszukiwania trasy morskiej na kuli …
3
Czy ten algorytm nadal można uznać za algorytm wyszukiwania binarnego?
Podczas wykonywania drugiego kata kodu (który prosi pięć razy o zaimplementowanie algorytmu wyszukiwania binarnego, za każdym razem inną metodą), wpadłem na nieco inne rozwiązanie, które działa w następujący sposób: Jeśli mam posortowaną tablicę o długości 100 i widzę, że jej pole początkowe zawiera liczbę 200, a pole końcowe zawiera liczbę …
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.