Depende de los supuestos del problema y de lo que significa “más eficiente”, pero generalmente desea ver las variantes de TSP (http://en.wikipedia.org/wiki/Tra…).
En la versión del problema con la menor cantidad de dimensiones, digamos que tiene un robot similar a un Roomba que solo puede conducir en el suelo alrededor de obstáculos, recogiendo bolas individuales a medida que avanza, y no hay un costo insignificante asociado con recoger bolas , cambiar de dirección, etc. Digamos que el robot comienza en el lugar donde está practicando saques y desea que el robot le responda con todas las bolas lo más rápido posible. Entonces, el problema es el TSP euclidiano de vainilla en un dígrafo ponderado y está buscando algoritmos para ese problema (exacto si el problema es lo suficientemente pequeño, o observe los algoritmos de aproximación / heurísticos disponibles).
Sin embargo, podrías imaginar agregar dimensiones al problema. Por ejemplo, una persona que se inclina hacia arriba puede preocuparse por cuántas veces tiene que inclinarse además de cuánto tiene que caminar, ya que inclinarse es físicamente más exigente (por unidad de tiempo) que caminar. Podría incorporar esto al problema mediante restricciones y / o la función objetivo que está tratando de minimizar, y el algoritmo en sí mismo que navega por el espacio de la solución consideraría que los vértices de TSP no son las bolas, sino que son discretos punto en la cancha donde se pueden alcanzar las bolas En el espacio de la solución, habría algún incentivo para elegir vértices estratégicamente en los que puede recoger varias bolas, y ese incentivo se compararía con los otros costos, como el tiempo que podría aumentar simultáneamente.
- ¿Soy un mal programador si no puedo entender Towers of Hanoi?
- ¿Cuáles son los tipos más comunes de Bloom Filter y cómo funcionan?
- ¿Cuáles son algunos libros excelentes sobre la programación de algoritmos ARM?
- Cómo escribir un programa para ingresar una cadena e imprimir el número de caracteres en minúscula y mayúscula en la cadena
- ¿Qué debo usar para reducir los atributos en mi conjunto de datos, PCA o algoritmos de selección de características?
El tratamiento de la red es un factor importante ya que si usted o su robot pueden pasar por encima o al menos alcanzarlo (y cómo cuantifican el costo de realizar esas acciones) pueden afectar drásticamente la búsqueda de soluciones.
Otra versión que podría imaginar es proporcionar algún incentivo para elegir soluciones parciales que devuelven suficientes bolas a un “costo por bola” que es mucho más bajo que el de las soluciones completas. La mejora marginal en un resultado a un alto costo podría no valer la pena. Por ejemplo, estás practicando cientos de saques y alcanzas el 95% en la red y el 5% en la red en una esquina lejana. Es posible que prefiera simplemente recoger las bolas agrupadas en la red y volver a servir en lugar de ir (o enviar su robot) en un paseo para obtener todas las bolas.
Hasta este punto, las bolas han permanecido estáticas, pero puede imaginar que su agente tenga la capacidad de “patear” las bolas a algún destino sujeto a alguna función de precisión. Si esa patada tiene un costo menor que recoger pelotas, habrá incentivos para hacerlo. Por ejemplo, si tiene un grupo de bolas en la esquina de la cancha y una bola en su camino hacia esa esquina, podría considerar patear esa bola hacia el grupo de la esquina y, con suerte, solo doblarse una vez. Si tiene una tolva o puede levantar pelotas con su raqueta / pie sin doblarse, entonces no sería un gran beneficio patear esa pelota.
