Jak wspólne algorytmy odnajdywania ścieżek mają się do procesu ludzkiego

11

Może się to wiązać z obliczeniową kognitywistyką, ale jestem ciekawy, w jaki sposób proces, po którym następują popularne algorytmy wyszukiwania ścieżek (takie jak A * ), porównuje się z procesem stosowanym przez ludzi w różnych sytuacjach poszukiwania ścieżki (biorąc pod uwagę te same informacje). Czy te procesy są podobne?

DorkRawk
źródło
3
Ludzie mogą korzystać z algorytmu A * pathfinding ... Mam na myśli, że algorytm to tylko technika, prawda? Nie sądzę, aby istniał jakiś algorytm, którego człowiek nie mógłby wykonać. Przypuszczam, że staram się osiągnąć to, że prawdopodobnie powinieneś być o wiele bardziej jasny w kwestii tego, co stanowi „proces, który ludzie wykorzystują w różnych sytuacjach poszukiwania ścieżki”. Nie sądzę, aby ktokolwiek mógł udzielić ci sensownej odpowiedzi, dopóki nie powiesz, jak ludzie to robią ... co jest prawdopodobnie problematyczne w ogólnym przypadku i wydaje się tutaj również trudne.
Patrick87,
Proszę również krótko wyjaśnić, co robi A * i / lub link do referencji. I witam!
Raphael
@ Patrick87 Z pewnością ludzie MOGĄ zrobić dowolny algorytm, ale to nie jest bardzo interesujące pytanie. To, o co starałem się zrozumieć, to porównanie algorytmów odnajdywania ścieżek z technikami stosowanymi przez ludzi, gdy pozostawiono je samodzielnie, aby rozwiązać problem (bez wcześniejszej wiedzy na temat algorytmów odnajdywania ścieżek).
DorkRawk,
3
Istnieją badania nad ludzkim zachowaniem w takich sytuacjach: rozsądna odpowiedź może wskazywać na faktyczne badania, w jaki sposób ludzie szukają ścieżki.
Suresh
2
Ludzie naprawdę nie radzą sobie dobrze z wykresami z milionami węzłów, szczególnie podanymi jako listy przyległości, ale działa dobrze. (Innymi słowy: jak ludzie robią to , co dokładnie?)ZA
JeffE

Odpowiedzi:

6

Ludzie wybierają nie do końca optymalne, ale zbliżają się do najkrótszych rozwiązań. Musisz więc spojrzeć na algorytmy rozmyte (przybliżone), a nie na A *.

Algorytm najbliższy myśleniu ludzkiemu, jaki znam, to hierarchie kontaktów na równi z algorytmem przycinania zasięgu . Kiedy muszę znaleźć na mapie ścieżkę między A i B, robię szybki przegląd, biorąc pod uwagę, czy przepływa rzeka lub coś innego, i szukam ogólnych sposobów, a następnie dodam szczegóły, które mogą skrócić ścieżkę.

mniam mniam mniam
źródło
Czy możesz powiedzieć, że to drugie podejście jest najkrótszą ścieżką, którą zaczynasz od przybliżonego przybliżenia wykresu i dopracowujesz go w miarę upływu czasu?
Raphael
@Raphael Tak, w rzeczywistości jest to opis tego, co robią Hierarchie Kontaktów (jest też krok przetwarzania wstępnego, który bierze wykres i zwija go do hierarchii z różnymi poziomami szczegółów) i jednocześnie tego, co zrobię jako istota ludzka
om-nom -nom
4

Oto kilka uwag. Dwa pierwsze pochodzą ze wspaniałego doktora Andreasa Junghannsa (teraz z powrotem do przemysłu w Berlinie, Niemcy i chętnie zaliczam go do grona moich przyjaciół :)):

Pierwsze wyszukiwanie szerokości : jeśli stoisz przed meblem, a coś cennego (na przykład moneta lub pierścionek) spada i wchodzi pod meble, abyś ich nie widział, wtedy machasz ręką, zaczynając od punkt, w którym widziałeś, jak obiekt znika. Jeśli go nie znajdziesz, pójdź trochę dalej i idź dalej, dopóki go nie znajdziesz lub stracisz cierpliwość. To jest dokładnie pierwsze wyszukiwanie w akcji: najpierw bierzesz pod uwagę wszystkie nieznane lokalizacje na głębokości 1, następnie na głębokości 2 i tak dalej.

Głębokie wyszukiwanie : szukając czegoś, co jest zdalnie zlokalizowane w twoim otoczeniu, nigdy nie wybierasz wyżej wspomnianego algorytmu, a zamiast tego decydujesz się na kierunek. Przykładem jest Cristobal Colon zobowiązujący się na zachód, szukając drogi do Indian. Cóż, mylił się, ale wiemy o tym dzisiaj. Wyobraź sobie, że Colon próbuje przeprowadzić pierwsze wyszukiwanie i ruszy wzdłuż spirali z Burgos, gdzie podpisano umowę między Reyes Católicos i Colon. Zamiast tego wskazał na określony kierunek bez cofania się.

Kolejny przykład jednego z moich profesorów z uniwersytetu (José Cuena, który już zmarł) dotyczy poszukiwań dwukierunkowych : inżynierów, kiedy budowanie tuneli w górach zaczyna się od obu końców jednocześnie i kończy, gdy spotykają się gdzieś pośrodku. Powód jest prosty: jeśli zaczynają się tylko od jednego końca, bardzo prawdopodobne jest, że na drugim końcu wystąpi ogromne odchylenie. Począwszy od obu końców jednocześnie minimalizuje się odchylenie w miejscu spotkania.

  • Otwarta lista jest tylko lista otwartych możliwości oczekujących należy rozważyć. Wszyscy ludzie to robią, chociaż nie jesteśmy tak dobrzy, jak komputery pamiętające rzeczy.
  • Lista zamknięta tylko służy do uniknięcia błędnego koła lub dalszego uzasadnienia z punktu widzenia, że już przed badanym. Dzieje się tak, jeśli rozumujesz głośno i coś powtarzasz. Wtedy ktoś zrozumie i natychmiast powie ci „hej, już to powiedziałeś”

Bardzo interesującym pytaniem, na które w jakiś sposób odpowiedzieli inni, jest to, czy ludzie mogą uruchomić dowolny algorytm i (jeszcze bardziej interesujące z mojego punktu widzenia), czy te algorytmy (lub, ogólnie rzecz biorąc, sposób, w jaki budujemy Sztuczną Inteligencję) naśladują nasze naturalne inteligentne procedury.

Carlos Linares López
źródło
Artykuł wymieniony przez Carlosa można przeczytać tutaj: svn.sable.mcgill.ca/sable/courses/COMP763/oldpapers/…
TFerrell
-2

Czy widziałeś dziecko uczące się poruszania po pokoju? Musisz im powiedzieć: „Idź dookoła stołu. WOKÓŁ ”.

Planowanie ścieżki ludzkiej to chwyt heurystyki, niektóre wrodzone, a niektóre wyuczone. Lookahead jest prawdopodobnie ustawiony na niewielką liczbę, z pewnością nie jest to ogólna rekurencja jak A *.

Trevor Blackwell
źródło
1
Te odpowiedzi zawierają tylko spekulacje.
Raphael