Esto podría estar al borde de la ciencia cognitiva computacional, pero tengo curiosidad sobre cómo el proceso seguido por los algoritmos de búsqueda de caminos comunes (como A * ) se compara con el proceso que los humanos usan en diferentes situaciones de búsqueda de caminos (dada la misma información). ¿Son similares estos procesos?
algorithms
graphs
artificial-intelligence
DorkRawk
fuente
fuente
Respuestas:
Los humanos tienden a elegir soluciones no estrictamente óptimas, sino cercanas a las más cortas. Por lo tanto, deberá buscar algoritmos difusos (aproximados), no A *.
El algoritmo más cercano al pensamiento humano que conozco es una jerarquía de contacto a la par con un algoritmo de poda Reach . Cuando necesito encontrar una ruta entre A y B en el mapa, hago una descripción general rápida, teniendo en cuenta si hay cruce de río u otra cosa y buscando algunas formas generales y luego agrego detalles que podrían acortar la ruta.
fuente
Aquí tienes una serie de consideraciones. Los dos primeros fueron tomados del maravilloso doctorado por Andreas Junghanns (ahora de vuelta a la industria en Berlín, Alemania y feliz de contarlo entre mis amigos :)):
Búsqueda de Breadth-First : si está de pie frente a un mueble y algo valioso (por ejemplo, una moneda o un anillo) cae y se coloca debajo del mueble, para que no pueda verlo, entonces agita la mano ligeramente desde el punto donde vio desaparecer el objeto. Si no lo encuentra, vaya un poco más allá y continúe de esta manera hasta que lo encuentre o pierda la paciencia. Esa es exactamente la búsqueda de amplitud en acción: primero, considera todas las ubicaciones desconocidas en la profundidad 1, luego en la profundidad 2 y así sucesivamente.
Búsqueda en profundidad : cuando busca algo que se encuentra de forma remota en su entorno, nunca elige el algoritmo mencionado anteriormente y, en cambio, se compromete con una dirección. Un ejemplo es Cristóbal Colón comprometiéndose con el oeste cuando busca una ruta hacia los indios. Bueno, estaba equivocado, pero eso lo sabemos hoy en día. Imagínese a Colón intentando una búsqueda de primer orden y moviéndose a lo largo de una espiral desde Burgos, donde se firmó el contrato entre los Reyes Católicos y Colón. En cambio, señaló una dirección determinada sin retroceder nunca.
Otro ejemplo de uno de mis profesores en la Universidad (José Cuena, quien ya falleció) se refiere a la búsqueda bidireccional : ingenieros, cuando la construcción de túneles en las montañas comienza desde ambos extremos simultáneamente y termina cuando se encuentran en algún punto intermedio. La razón es simple: si comienzan solo desde un extremo, es muy probable que haya una gran desviación en el otro extremo. Comenzar desde ambos extremos minimiza simultáneamente la desviación en el punto de encuentro.
Una pregunta muy interesante de alguna manera abordada por otros es si los humanos pueden ejecutar algún algoritmo y (aún más interesante desde mi punto de vista) si estos algoritmos (o, en general, la forma en que construimos la Inteligencia Artificial) imitan nuestros procedimientos inteligentes naturales.
fuente
¿Has visto a un niño aprender a navegar por una habitación? Tienes que decirles: "Ve alrededor de la mesa. ALREDEDOR ".
La planificación del camino humano es una bolsa de heurística, algunas innatas y otras aprendidas. Lookahead probablemente está fijado a un número pequeño, ciertamente no es una recursividad general como A *.
fuente