algorithm - harary - Calcula el camino más corto a través de una tienda de comestibles

graph theory harary

Question

Estoy tratando de encontrar la manera de encontrar el camino más corto a través de una tienda de comestibles, visitando una lista de lugares (lista de compras). La ruta debe comenzar en una posición de inicio especificada y puede finalizar en múltiples posiciones finales (hay varios contadores de pago). Además, tengo algunas limitaciones predefinidas en la ruta, como "el elemento x en la lista de compras debe ser el último, el último último o el último tercer elemento en la ruta". Hay una función que devolverá verdadero o falso para una ruta determinada. Finalmente, esto debe calcularse con una potencia de CPU limitada (en un teléfono inteligente) y dentro de un segundo más o menos. Si esto no es posible, entonces una aproximación a la ruta óptima también está bien.

es posible? Hasta ahora creo que necesito comenzar por calcular la distancia entre cada elemento de la lista usando algo como A * o Dijkstra. Después de eso, ¿debería tratarlo como el problema del vendedor ambulante? Porque en mi problema hay un nodo de inicio especificado, nodos finales especificados y algunas restricciones que no están en el problema del vendedor viajero.

Answer 1

Bueno, básicamente es un problema de vendedor ambulante, pero con sus requisitos limita bastante bien el espacio de búsqueda. Si no hay demasiadas ubicaciones, puede intentar calcular todas las opciones posibles, pero si eso no es posible, debe limitar el espacio de búsqueda aún más.

Puede limitar el tiempo de búsqueda para que regrese el camino más corto que puede encontrar en 1 segundo, pero puede que no sea el más corto de todos, pero de todos modos es bastante corto.

También puede aplicar el algoritmo Greedy para encontrar la siguiente ubicación más cercana, luego usar Backtracking, seleccionar la siguiente ubicación más cercana, etc.

Pseudo código para una posible solución:

def find_shortest_path(current_path, best_path): if time_limit() return if len(current_path) == NUM_LOCATIONS: # destionation reached if calc_len(current_path) < calc_len(best_path): best_path = current_path return # You need to sort the possible locations well to maximize your chances of finding the # the shortest solution sort(possible_locations) for location in possible_locations: find_shortest_path(current_path + location, best_path)

Answer 2

Bueno, podría limitar el espacio de búsqueda utilizando información sobre el diseño de la tienda. Por ejemplo, una tienda típica (al menos aquí en Alemania) tiene muchos estantes que se pueden considerar para formar carriles. En el medio hay carriles ortogonales que conectan los carriles de estante. Ahora define los cruces para que sean los nodos y los carriles para que sean bordes en un gráfico. Los bordes están etiquetados con todos los elementos en los estantes de esa sección de carril. Ahora, incluso para una gran tienda, este gráfico sería bastante pequeño. Ahora debería encontrar la ruta más corta que incluye todas las etiquetas de borde (elementos) que necesita. Esto debería ser posible utilizando el enfoque codicioso / de retroceso sugerido por Tuomas Pelkonen .

Esto es solo una idea, y no sé si realmente funciona, pero tal vez puedas tomarlo desde aquí.

Answer 3

El requisito de un nodo de inicio es ficticio. Al usar el TSP, terminará con un recorrido en el que puede elegir el nodo de inicio que desee sin alterar el costo de la solución.

Es un poco más complicado cuando se trata de los contadores: lo que necesita es resolver el problema en un gráfico dirigido con algunos arcos perdidos (o, lo que es lo mismo, donde algunos arcos tienen un costo muy alto).

Comenzando con el gráfico dirigido completo, debe modificar los costos de los arcos correspondientes para:

1. negar pasar de los elementos al nodo de inicio
2. negar pasar de los contadores a los artículos
3. negar ir desde el nodo de inicio a los contadores
4. permite ir desde los contadores al nodo de inicio a costo cero (esto solo es necesario para cerrar el camino)
5. después de haber dibujado la cosa, dime si me perdí algo :)

HTH

Answer 4

Parece que verlo como un problema TSP lo hace más difícil. Alguien señaló que las historias de comestibles no son tan complicadas. En las tiendas de comestibles con las que estoy familiarizado (en los EE. UU.), No existen muchas rutas razonables. Especialmente si tienes un punto de partida dado. Creo que una heurística bien pensada probablemente sea el truco.

Por ejemplo: generalmente comienzo en un extremo. Si es un gran viaje, me aseguro de que revise los alimentos congelados al final, pero a menudo no importa y comenzaré más cerca de donde entro a la tienda. Generalmente camino por el exterior, solo bajando por pasillos individuales si necesito algo en eso. Una vez que entras en un pasillo, recoge todo en ese. Con algunos pasillos, es mejor caer en un extremo, agarrar el artículo y regresar al punto de partida, y otros que simplemente comprometes con todo el pasillo: es una función del último elemento que necesitas en ese pasillo y donde necesitas ser el siguiente-- cómo salir del pasillo depende del siguiente elemento necesario - puede o no implicar un retroceso - pero la computadora puede calcular fácilmente el camino más corto hacia los siguientes elementos.

Así que estoy de acuerdo con los consejos útiles de los otros problemas anteriores, pero tal vez un algoritmo menos general funcionará. Y probablemente funcionará mejor con recursos limitados. Sin embargo, TSP nos dice que no se puede probar que sea el enfoque óptimo, pero sospecho que no es realmente necesario ...

Answer 5

Solo la primera búsqueda de ancho se asegurará de no "perder" una ruta a través de la tienda que es mejor que la actual "mejor" solución, pero no necesita buscar todos los nodos en la ruta. Los nodos que son "obviamente" más largos que la "mejor" solución actual se pueden ampliar más adelante.

Esto significa que aborda el problema como una búsqueda de "aliento primero", pero altera la expansión de sus nodos en función de la distancia actual recorrida. Algunas ramas del árbol de búsqueda se expandirán más rápido que otras, porque logran visitar más nodos en la misma cantidad de tiempo.

Entonces, si la expansión del nodo no es realmente la primera respiración, ¿por qué sigo usando esa palabra? Porque después de encontrar una solución, aún debe expandir el conjunto actual de "nodos considerados" hasta que cada una de esas rutas de búsqueda exceda la solución. Esto evita que se pierda un camino que consume mucho tiempo en las piernas iniciales, pero termina más rápido que la solución actual porque el último paso es la iluminación rápida.