Pozwól mi wyjaśnić:

Biorąc pod uwagę wykres punktowy pewnej liczby punktów n, jeśli chcę znaleźć mentalnie najbliższy punkt do dowolnego punktu na wykresie, mogę natychmiast zignorować większość punktów na wykresie, zawężając moje wybory do niewielkiej, stałej liczby punktów w pobliżu .

Jednak przy programowaniu, biorąc pod uwagę zestaw punktów n, aby znaleźć punkt najbliższy dowolnemu, wymaga sprawdzenia każdego innego punktu, którym jest czas.${\cal O}(n)$

Zgaduję, że wizualny widok wykresu prawdopodobnie odpowiada pewnej strukturze danych, której nie jestem w stanie zrozumieć; ponieważ przy programowaniu, poprzez konwersję punktów na bardziej ustrukturyzowaną metodę, taką jak quadtree, można znaleźć najbliższe punkty do punktów za w czasie lub zamrożone czas.$k$$n$$k\cdot\log(n)$${\cal O}(\log n)$

Ale wciąż nie są znane zamortyzowane algorytmy (które mogę znaleźć) do wyszukiwania punktów po restrukturyzacji danych.${\cal O}(1)$

Dlaczego więc wydaje się to możliwe po zwykłej kontroli wizualnej?

Twój model tego, co robisz mentalnie, jest nieprawidłowy. W rzeczywistości działasz w dwóch etapach:

1. Wyeliminuj wszystkie punkty, które są za daleko, w czasie .$O(1)$
2. Zmierz punktów, które są mniej więcej tak blisko, w czasie Θ ( m ) .$m$$\Theta(m)$

Jeśli grałeś w gry takie jak bule (bule) lub curling, powinno to być znane - nie musisz badać obiektów, które znajdują się bardzo daleko od celu, ale możesz potrzebować zmierzyć najbliższych rywali.

Aby zilustrować ten punkt, która zielona kropka jest najbliższa czerwonej kropce? (Tylko o nieco ponad 1 piksel, ale jest jeden, który jest najbliższy.) Aby ułatwić, kropki zostały nawet oznaczone kolorami według odległości.

To zdjęcie zawiera punktów, które są prawie na okręgu, i n ≫ łącznie 10 zielonych punktów. Krok 1 pozwala wyeliminować wszystkie z wyjątkiem m punktów, ale krok 2 wymaga sprawdzenia każdego z m punktów. Nie ma a priori związanego dla m .$m=10$$n \gg 10$$m$$m$$m$

Obserwacja fizyczna pozwala zmniejszyć rozmiar problemu z całego zestawu punktów do ograniczonego zestawu kandydackiego m punktów. Ten krok nie jest krokiem obliczeniowym, jak powszechnie rozumiane, ponieważ opiera się na ciągłym procesie. Procesy ciągłe nie podlegają zwykłym intuicjom dotyczącym złożoności obliczeniowej, a w szczególności analizie asymptotycznej.$n$$m$

Teraz możesz zapytać, dlaczego ciągły proces nie może całkowicie rozwiązać problemu? Jak dochodzi do tych punktów, dlaczego nie możemy dopracować procesu, aby uzyskać m = 1 ?$m$$m=1$

Odpowiedź brzmi: oszukałem trochę: przedstawiłem zestaw punktów, który jest generowany, aby składał się z prawie najbliższych punktów i n - m punktów, które są dalej. Zasadniczo ustalenie, które punkty mieszczą się w precyzyjnej granicy, wymaga precyzyjnej obserwacji, którą należy wykonać punkt po punkcie. Zgrubny proces eliminacji pozwala wykluczyć wielu oczywistych kandydatów niebędących kandydatami, ale samo podjęcie decyzji, którzy pozostali kandydaci, wymaga ich wyliczenia.$m$$n-m$

Możesz modelować ten system w dyskretnym świecie obliczeniowym. Załóżmy, że punkty są reprezentowane w strukturze danych, która sortuje je do komórek na siatce, tzn. Punkt jest przechowywany na liście dla komórki ( ⌊ x ⌋ , ⌊ y ⌋ ) . Jeśli szukasz punktów najbliższych ( x 0 , y 0 ), a komórka zawierająca ten punkt zawiera co najwyżej jeden inny punkt, wystarczy sprawdzić komórkę zawierającą i 8 sąsiednich komórek. Całkowita liczba punktów w tych 9 komórkach wynosi $(x,y)$$(\lfloor x \rfloor, \lfloor y \rfloor)$$(x_0, y_0)$$m$. Ten model uwzględnia niektóre kluczowe właściwości modelu ludzkiego:

• jest potencjalnie nieograniczony - zdegenerowany gorszy przypadek np. punktów leżących prawie na okręgu jest zawsze możliwy.$m$
• Praktyczna wydajność zależy od wybrania skali odpowiadającej danym (np. Nic nie zaoszczędzisz, jeśli twoje kropki są na kawałku papieru, a komórki mają 1 km szerokości).

Powodem jest to, że dane zostały umieszczone w „strukturze danych” zoptymalizowanej dla tego zapytania i że czas przygotowania do przygotowania wykresu powinien zostać uwzględniony w zmierzonych czasach, który jest proporcjonalny do liczby kropek, dając O (n) złożoność właśnie tam.

Jeśli umieścisz współrzędne w tabeli zawierającej współrzędne X i Y każdego punktu, będziesz potrzebował znacznie większego wysiłku umysłowego, aby obliczyć odległości między punktami, posortuj listę odległości i wybierz najmniejszą.

Jako przykład zapytania, które nie działa dobrze wizualnie, mogłoby być spojrzenie na nocne niebo i - na podstawie wyłącznie twojego widoku i tabeli współrzędnych każdej gwiazdy - zlokalizowanie najbliższej gwiazdy na Ziemi lub który znak astrologiczny ma najmniejszą odległość między gwiazdy, z których się składa. Potrzebny byłby tutaj model 3D z możliwością powiększania i obracania, aby określić go wizualnie, przy czym komputer uznałby to za zasadniczo ten sam problem, co oryginał.

To pytanie zaczyna się od błędnego założenia. Po prostu myślisz, że możesz mentalnie znaleźć najbliższy punkt w punkcie , ale w rzeczywistości, jeśli nie możesz. Wydaje się, że tak jest, ponieważ przywykłeś do radzenia sobie z bardzo małymi grafami, ale małe przykłady mogą wprowadzać w błąd, gdy mamy do czynienia z asymptotyczną złożonością. Jeśli spróbujesz to zrobić za pomocą wykresu punktowego z miliardem punktów, szybko odkryjesz, że nie możesz tego zrobić w czasie O ( 1 ) .$O(1)$$O(1)$

Przewaga kontroli wzrokowej zależy od kluczowych pomieszczeń, których ogólnie nie można zagwarantować:

• skalowanie : skupiasz się na graficznej reprezentacji obszaru zainteresowania. oznacza to, że geometria została zmniejszona, aby pasowała do twojego pola widzenia. w ustawieniach ogólnych wymaga to już czasu na wstępne przetwarzanie.$O(n)$

• count : (por. komentarz Nicka Algera do odpowiedzi udzielonej przez DW) zakłada liczbę punktów przekraczającą liczbę komórek siatkówki - nawet nie zidentyfikujesz wszystkich zaangażowanych punktów.

• wariancja : (por. komentarz Nicka Algera do odpowiedzi udzielonej przez DW) zakłada, że ​​zbiór punktów na regularnej (np. heksagonalnej) siatce jest poddawany niewielkim przypadkowym zaburzeniom. jeśli te zaburzenia staną się niższe niż rozdzielczość twojej siatkówki (lub jakiejkolwiek innej nałożonej siatki), będziesz nie tylko trudny do wykrycia rzeczywistej minimalnej odległości, ale wybierzesz niewłaściwe pary punktów z dużym prawdopodobieństwem.

$O(n)$$O(1)$

1. Komputer rozwiązuje inny problem. Wymaga listy punktów, a nie zrasteryzowanego obrazu punktów. Konwersja listy na obraz, tj. „Wykreślanie” punktów, zajmuje dużo O(n)czasu.

   Szybki! Który jest najbliższy (1,2):

   • (9, 9)
   • (5, 2)
   • (3, -2)
   • (4, 3)
   • (0, 4)
   • (1, 9)

   O wiele trudniej, prawda? Założę się, że jeśli zrobię listę dwa razy dłużej, będziesz musiał wykonać dwa razy więcej pracy.

2. Nie zdajesz sobie sprawy, ile pracy wykonuje twój mózg. Nie „po prostu wiesz”, który punkt jest bliżej. Twój mózg wykonuje prace obliczeniowe, aby znaleźć tę odpowiedź i ją udostępnić. Mózg pracuje nad każdym punktem równolegle, więc czas na ukończenie pozostaje mniej więcej taki sam, ale ilość wymaganej pracy wciąż rośnie wraz z liczbą punktów.

Z tego samego powodu, kiedy patrzysz na trójkąt i wiesz, że jest to trójkąt, zapominasz o milionach obliczeń, które wykonujesz, nie zauważając go.

Sieci neuronowe

W efekcie jesteś siecią neuronową, która została przeszkolona i obciążona masą mas masowych danych.

Weźmy za przykład grę sortowania kształtów niemowląt:

Gdy dziecko po raz pierwszy wejdzie w interakcję z tym, prawdopodobnie spróbuje wstawić kształty do niewłaściwych otworów, ponieważ nie wyszkoliło jeszcze swojego mózgu lub nie napotkało wystarczającej ilości danych do zbudowania sieci. Nie mogą przyjmować założeń dotyczących krawędzi, rozmiaru itp., Aby określić, który kształt pasuje do otworu.

Wydaje ci się to oczywiste (mam nadzieję), ponieważ zbudowałeś te połączenia, możesz nawet pomyśleć, że jest intuicyjny i nie musisz go rozbijać, na przykład po prostu wiesz, że trójkąt pasuje do trójkąta i nie musisz przybliżać rozmiaru , policz krawędzie, .etc. To nie jest prawda, zrobiłeś to wszystko w swojej podświadomości, jedyną świadomą myślą, jaką miałeś, było to, że jest to trójkąt. Dokonano wielu milionów obliczeń, biorąc pod uwagę wizualną reprezentację, rozumiejąc, co to reprezentuje, rozumiejąc, jakie są poszczególne elementy, a następnie szacując ich odległości, a fakt, że dysponowałeś dużą bazą danych, z którą można było sondować, znacznie ułatwił.

Twój mózg nie jest binarny

Dane, na których pracuje Twój mózg, nie są binarne (o ile wiemy), nie są prawdziwe ani fałszywe, zawierają wiele stanów, których używamy do interpretacji danych, często również źle się miewamy, nawet jeśli postępujemy zgodnie z prawidłowymi proces, ponieważ dane często się zmieniają. Zaryzykowałbym przypuszczenie, że nasze mózgi funkcjonują bardziej jak komputer kwantowy, w którym bity są w przybliżonym stanie do momentu odczytania. Oznacza to, że jeśli nasz mózg w ogóle działa jak komputer, tak naprawdę nie jest znany.

Dlatego algorytm do pracy z danymi binarnymi nie będzie działał tak samo. Nie możesz ich porównać. W swojej głowie używasz pojęć do wykonywania, bogate typy danych, które przechowują znacznie więcej informacji, masz możliwość tworzenia łączy tam, gdzie nie są one wyraźnie zdefiniowane; po zobaczeniu trójkąta możesz pomyśleć o Ciemnej stronie osłony księżyca Pink Floyda.

Wracając do wykresu rozrzutu, nie ma powodu, dla którego nie można tego zrobić na komputerze za pomocą mapy bitowej i mierząc odległość od punktu w rosnących promieniach, aż do napotkania innego punktu. Jest to prawdopodobnie najbliższe przybliżenie człowieka. Prawdopodobnie będzie znacznie wolniej z powodu ograniczeń danych i ponieważ nasze mózgi niekoniecznie dbają o złożoność obliczeń i wybierają złożoną drogę do robienia rzeczy.

Nie byłoby O (1), a nawet O (n), jeśli n jest liczbą punktów, zamiast tego jego złożoność zależy teraz od maksymalnej liniowej odległości od wybranego punktu do granicy obrazu.

tl; dr

Twój mózg nie jest komputerem binarnym.

zapominasz o jednym ważnym kroku: wykreślając wszystkie punkty na wykresie, na który patrzysz.

jest to z konieczności operacja O (n).

po tym komputer może użyć oprogramowania do rozpoznawania obrazów, aby znaleźć przybliżone punkty najbliżej środka, w taki sam sposób, jak ludzkie oko. Jest to najgorszy przypadek operacji O (sizeOfImage).

aby człowiek zrobił to samo, co komputer, pamiętaj, że komputer otrzymuje listę współrzędnych i może przeglądać tylko jedną z nich naraz.

Moja interpretacja pytania:

Nie wierzę, że to pytanie należy traktować w uproszczeniu jako zagadnienie złożoności geometrii obliczeniowej. Powinno to być lepiej rozumiane jako powiedzenie: dostrzegamy zdolność do znalezienia odpowiedzi w stałym czasie, kiedy możemy. To, co wyjaśnia tę percepcję, aż do tego wyjaśnienia i ludzkich ograniczeń, może również zrobić komputer.

$O(1)$$O(log( n))$

Może to zostać wzmocnione przez prawa Webera-Fechnera , które mówią, że naszą percepcję należy mierzyć w skali logarytmicznej rzeczywistej miary fizycznej. Innymi słowy, postrzegamy raczej warianty względne niż absolutne. To jest na przykład, dlaczego natężenie dźwięku jest mierzone w decybelach.

$O(log (n))$$O_\psi(log (log (n)))$$O_\psi$

$O_\psi(log (log (n)))$ który ze wszystkich praktycznych celów jest prawdopodobnie percepcyjnie nierozróżnialny od stałej, i koniecznie trzeba dodać trochę stałego czasu, aby rozpocząć proces rozpoznawania i potwierdzić wynik.

Biorąc pod uwagę ograniczenia fizjologiczne

Powyższy wniosek został podtrzymany przy rozważaniu etapów akwizycji obrazu.

OP starał się oddzielić budowę odpowiedniej struktury danych, „takiej jak czterokrotnie”, która jest amortyzowana w kilku zapytaniach.

Nie działa to w przypadku większości osób, które nie zapamiętują obrazu. Myślę, że obraz jest skanowany dla każdego zapytania, ale nie oznacza to skanowania wszystkich punktów: nie za pierwszym razem i nie w przypadku późniejszych zapytań.

$T_{scan}$$T_{scan}$

$m$$O_\psi(log (log (m)))$

$2^{27}$$log_2(27)$

Bez znajomości rzeczywistych jednostek, które mają być użyte, pokazuje to po prostu, że najgorsza odmiana przetwarzania jest w tej samej kolejności, co inne operacje o stałym czasie. Dlatego całkiem naturalne jest, że postrzegany czas na znalezienie najbliższego punktu wydaje się stały. . . czy określamy najbliższy punkt, czy tylko zbiór najbliższych punktów.

O kontrprzykładach i możliwym rozwiązaniu

Oczywiście łatwo jest budować kontrprzykłady, które bardzo utrudniają określenie najbliższego punktu w oczach wśród niewielkiej grupy bliższych punktów. Właśnie dlatego OP prosi o algorytm, który szybko eliminuje większość punktów, z wyjątkiem tych najbliższych. Kwestia możliwej trudności wyboru między kilkoma bliskimi punktami jest poruszana w wielu odpowiedziach, przy czym paradygmatyczny przykład najbliższych punktów znajduje się prawie na okręgu wokół punktu odniesienia. Zazwyczaj prawa Webera-Fechnera wykluczają możliwość rozróżnienia niewielkich zmian odległości na wystarczająco dużych odległościach. Efekt ten może faktycznie zostać zwiększony przez obecność innych punktów, które - choć wyeliminowane - mogą zniekształcać postrzeganie odległości. Próbowanie zidentyfikowania najbliższego punktu będzie trudniejszym zadaniem, i może wymagać określonych kroków badania, takich jak użycie instrumentów, które całkowicie zniszczą poczucie ciągłego czasu. Wydaje się jednak, że wyraźnie wykracza poza zakres eksperymentów rozważanych przez PO, a zatem nie jest zbyt istotny.

Pytanie , na które należy odpowiedzieć , to pytanie faktycznie postawione przez PO, brzmi, czy istnieje sposób na wyeliminowanie większości punktów, z wyjątkiem ewentualnie pozostałych kilku, które wydają się mieć bardzo podobne odległości do punktu odniesienia.

$O(log(n))$

Odrzucenie zamortyzowanego kosztu nie pozwala na rozwiązanie komputerowe, ponieważ należy przeanalizować wszystkie punkty. Podkreśla to zasadniczą różnicę w mocy obliczeniowej mózgu i percepcji człowieka: może on wykorzystywać obliczenia analogowe o właściwościach zupełnie innych niż obliczenia cyfrowe . Zazwyczaj ma to miejsce, gdy miliardy punktów nie są rozpoznawalne przez oko, które nie ma rozdzielczości, aby zobaczyć cokolwiek poza dużą chmurą o różnych odcieniach ciemności. Ale oko może wtedy skupić się na odpowiedniej mniejszej części i zobaczyć ograniczoną liczbę punktów zawierających odpowiednie punkty. Nie musi znać wszystkich punktów indywidualnie. Aby komputer zrobił to samo, musiałbyś nadać mu podobny czujnik, a nie dokładne współrzędne liczbowe każdego punktu. To jest zupełnie inny problem.

„Zwykła kontrola wizualna” jest pod pewnymi względami znacznie bardziej wydajna niż obliczenia cyfrowe. Wynika to również z fizyki czujników, a nie tylko z potencjalnie większej mocy obliczeniowej mózgu.

Mieliśmy uczniów w egzaminach, którzy zapytani o to, jak szybko można posortować tablicę, twierdziliby, że komputery są głupie i potrzebują n * log (n) (lub gorzej), podczas gdy ludzie mogą to zrobić szybciej.

Odpowiedź mojego profesora zawsze brzmiała: podam listę 10.000 pozycji. Zobaczmy, czy możesz wymyślić metodę, która jest szybsza niż to, co zrobiłby komputer.

A potem: ile rdzeni przetwarzających jest zaangażowanych, gdy próbujesz znaleźć najbliższy punkt? Nie jesteś maszyną jednoprocesorową, masz sieć neuronową, która ma pewną elastyczność, jeśli chodzi o takie zadania.

Uważam, że @ Patrick87 dał ci wskazówkę: twoje oczy i mózg są masowo równoległą maszyną obliczeniową. Niektórzy twierdzili, że nie wyjaśnia to problemu, ponieważ w przypadku dowolnie dużych problemów skończona liczba równoległych procesorów nie ma znaczenia.

Ale robi się tutaj: jak wielu sugeruje, twoje oczy (i mózg) mają ograniczoną zdolność do rozwiązania tego problemu; a to dlatego, że nie można zmieścić żadnej liczby punktów w zasięgu normalnego ludzkiego wzroku. Twoje oczy muszą być w stanie je rozróżnić na początek, a jeśli będzie ich zbyt wiele, będą tak blisko, że twoje oczy nie zauważą różnicy. Podsumowując: jest szybki dla wystarczająco dobrych punktów, które pasują do twojego normalnego wzroku, tj. Bardzo niewielu. W innych przypadkach zawiedzie.

Tak więc możesz rozwiązać ten problem w O (1) dla małych i prostych przypadków, które twój mózg może przetworzyć w mgnieniu oka. Poza tym nie może i dlatego nie jest nawet O ( cokolwiek ), ponieważ najprawdopodobniej zawiedzie.

Nikt nie wspomniał, że problem ten można rozwiązać bardzo szybko na komputerze z indeksem przestrzennym. Jest to odpowiednik wykreślenia punktów na obrazie, aby twoje oczy szybko zeskanowały i wyeliminowały większość punktów.

Istnieje bardzo dobry algorytm indeksowania wykorzystywany przez Google i inne osoby do znajdowania najbliższych punktów zwanych Geohash. http://en.wikipedia.org/wiki/Geohash .

Myślę, że to nawet zwiększy konkurencję na korzyść komputera. Nie byłem pod wrażeniem niektórych odpowiedzi wykorzystujących myślenie liniowe.

Jeśli weźmiemy pod uwagę przypadek znalezienia najbliższych sąsiadów w zestawie punktowym n-wymiarów w przestrzeni euklidesowej, złożoność jest zwykle ograniczona przez liczbę wymiarów, gdy stają się one duże (tj. Większe niż rozmiar zbioru danych).

$O(\log^{d-2} n)$

Problem znalezienia najbliższego punktu na węźle na wykresie ma wyrażenie euklidesowe, ilekroć wykres można osadzić w przestrzeni euklidesowej z wystarczająco małym zniekształceniem. Korzystając z listy przylegania z wagami, nadal musimy zbudować listę przylegania.

$O(1)$

inne odpowiedzi są dobre, ale co powiesz na pytanie przeciwne zen, które rozciąga podstawowe rozumowanie / założenie pierwotnego pytania do skrajności, aby wykazać pewną wadę [ale jest również paradoksem u podstaw badań nad AI ]:

skoro potrafię myśleć ludzką inteligencją, dlaczego nie mogę stworzyć komputera, który myśli równie dobrze jak człowiek?

istnieje wiele sposobów odpowiedzi na twoje pytanie, ale w zasadzie nasze procesy myślowe i zdolności percepcyjne mózgu niekoniecznie są dostępne dla introspekcji, a introspekcja, którą do nich stosujemy, może być myląca. na przykład możemy rozpoznać obiekty, ale nie mamy sposobu na dostrzeżenie / wyjaśnienie quasi-algorytmicznego procesu, który na to pozwala. istnieje również wiele eksperymentów psychologicznych, które pokazują subtelne zniekształcenia w naszym postrzeganiu rzeczywistości, aw szczególności postrzeganiu czasu, patrz np . postrzeganie czasu .

naukowcy uważają, że ludzki mózg faktycznie stosuje algorytmy, ale działają one inaczej niż skomputeryzowane, a ponadto istnieje bardzo duża liczba procesów równoległych w mózgu za pośrednictwem sieci neuronowych , których nie można rozsądnie porównać z sekwencyjne algorytmy komputerowe. u ssaków znaczna część całej objętości mózgu jest przeznaczona na przetwarzanie wzrokowe.

innymi słowy, ludzki mózg jest pod wieloma względami wysoce zoptymalizowanymi komputerami wizualnymi, i w rzeczywistości pod wieloma względami ma możliwości, które przekraczają obecnie największe superkomputery na świecie, takie jak rozpoznawanie obiektów itp., a to z powodu wad (w porównaniu) w skonstruowanym przez człowieka oprogramowaniu / sprzęcie w porównaniu z biologią, która była przez wiele lat doskonalona / rozwijana / optymalizowana.

Mówiąc ogólnie, rozwiązujesz dwa różne problemy i jeśli bierzesz udział w tej samej konkurencji, złożoność będzie wynosić O (1) dla was obu. Dlaczego? Uprośćmy sytuację - załóżmy, że masz linię z jednym czerwonym punktem i n zielonymi punktami. Twoim zadaniem jest znalezienie zielonego punktu, który jest najbliżej czerwonego punktu. Wszystko jest na wykresie. Teraz to, co robisz i co programujesz, jest w zasadzie takie samo - po prostu „odejdź” (w obu kierunkach) od czerwonego punktu i sprawdź, czy piksel, na który patrzysz, jest biały / czarny (tło) czy zielony. Teraz złożoność wynosi O (1).

Co ciekawe, niektóre metody prezentacji danych dają natychmiastowe odpowiedzi na niektóre pytania (O (1)). Podstawowy przykład jest niezwykle prosty - wystarczy policzyć białe piksele na czarnym obrazie (każda wartość piksela to 0 = czarny lub 1 = biały). Musisz tylko dodać wszystkie wartości pikseli - złożoność jest taka sama dla 1 białego piksela i dla 1000, ale zależy to od rozmiaru obrazu - O (m), m = image.width * image.height. Czy można to zrobić szybciej? Oczywiście wszystko, co musimy zrobić, to zastosować inną metodę przechowywania obrazów, która jest obrazem integralnym : Teraz obliczamy wynik O (1) (jeśli masz już obraz całkowy obliczony). Innym sposobem jest po prostu przechowywanie wszystkich białych pikseli w tablicy / wektorze / liście / ... i po prostu policzenie ich rozmiaru - O (1).