Araña caza moscas

Question

Una telaraña es un cuadrado con $100 \times 100$ nodos. $100$ moscas atrapadas en la web apilados en $100$ diferentes nodos. Una araña que estaba originalmente en la esquina de la web rastrea desde un nodo a un lado de nodo contar mueve y comiendo moscas en su camino. Puede que la araña comer todas las moscas en no más de $2100$ se mueve? o $2000$ se mueve?

Gracias de antemano.

Answer 1

Como se ha señalado, su pregunta es muy claro. En mi respuesta voy a asumir que usted comience en la esquina de la $O$ $n \times n$ cuadrado de la cuadrícula de nodos y sólo puede mover a lo largo de los bordes entre (ortogonal) de los nodos adyacentes. A continuación, el número máximo de movimientos que usted necesita para llegar a cualquier conjunto dado de $n$ destino de los nodos en la red es, al menos, $(r^3+2s-r)$ y en la mayoría de las $(2ns-s-1)$ donde$r = \lfloor\sqrt{n}\rfloor$$s = \lceil\sqrt{n}\,\rceil$. Tenga en cuenta que ambos límites se $Θ(n \sqrt{n})$$n \to \infty$.

En primer lugar, si el objetivo de los nodos incluyen un $r \times r$ subarray de nodos con una separación de $r$ nodos entre cada fila o columna, se posiciona como lejos de $O$ como sea posible (*), entonces usted necesita, al menos, $r$ se mueve para llegar de un nodo en el subarray a otra, y por lo menos $2s$ se mueve para obtener el primer nodo en el subarray, y por lo tanto, usted necesita un total de, al menos, $(r^2-1)r+2s = r^3+2s-r$ se mueve.

En segundo lugar, siempre podemos dividir la cuadrícula en $s$ rectangular subgrids en una pila vertical (cada uno tiene la anchura $n$ y la altura a la mayoría de las $s$). Podemos movernos a través de la subgrids de uno en uno, desde el más cercano al más alejado $O$, y en cada subgrid nos visita el destino de los nodos en que subgrid en el orden de su posición horizontal, empezando y terminando en los nodos a la izquierda/derecha límites, alternando de izquierda a derecha y de derecha a izquierda cada vez que vamos a la siguiente subgrid. Podemos completar cada subgrid utilizando en la mayoría de las $(n-1)$ horizontal se mueve y $k(s-1)$ vertical se mueve, donde $k$ es el número de nodos de destino en el subgrid. Podemos recorrer entre subgrids utilizando en la mayoría de las $(n-1)$ vertical se mueve. Por lo tanto necesitamos en la mayoría de las $(s+1)(n-1)+n(s-1) = 2ns-s-1$ se mueve.

(*) En caso de que esto no es lo suficientemente claro, estamos considerando el caso cuando el objetivo de los nodos incluyen $r^2$ nodos colocado en una plaza de configuración donde el objetivo adyacente nodos se $r$ se aleja. Por supuesto, queremos poner esta configuración tan lejos de $O$ como sea posible. Uno puede conseguir un poco mejor límite inferior, añadiendo al $(n-r^2)$ restos de nodos en algún lugar, pero estoy demasiado ocupado para trabajar en los detalles, y a ellos no les importa mucho.

Answer 2

No es una prueba, pero me decidí a probar el problema con Mathematica para tener una idea de lo que es un caso típico podría ser. Aquí está mi código principal:

n=100;
Flies = Union[{{0, 0}}, Table[{RandomInteger[n-1]+1, RandomInteger[n-1]+1}, {i, 1, n}]]
Hunt = First[FindShortestTour[Flies, DistanceFunction -> ManhattanDistance]]

Después de ejecutar dentro de un bucle $2000$ de las veces me tienen los siguientes resultados

Average Tour Length = 1044.62
Max Tour Length     = 1182

(El mínimo de la Duración del Tour iba a ser $100$ se mueve.)

---

Editar:

El tour longitudes de encontrar no son verdaderamente óptima a menos que se use Method -> "IntegerLinearProgramming" como un argumento para FindShortestTour. Sin embargo, esto es mucho más lento. El óptimo tours son aproximadamente el $100$ se mueve mejor.

---

Ejemplos de trayectos más largos

Ejemplo 1: espaciados de manera Uniforme.

Conjunto de las moscas:

{{0, 0}, {50, 50}, {0, 11}, {0, 22}, {0, 33}, {0, 44}, {0, 55}, {0, 66}, {0, 77}, {0, 88}, {0, 99}, {11, 0}, {11, 11}, {11, 22}, {11, 33}, {11, 44}, {11, 55}, {11, 66}, {11, 77}, {11, 88}, {11, 99}, {22, 0}, {22, 11}, {22, 22}, {22, 33}, {22, 44}, {22, 55}, {22, 66}, {22, 77}, {22, 88}, {22, 99}, {33, 0}, {33, 11}, {33, 22}, {33, 33}, {33, 44}, {33, 55}, {33, 66}, {33, 77}, {33, 88}, {33, 99}, {44, 0}, {44, 11}, {44, 22}, {44, 33}, {44, 44}, {44, 55}, {44, 66}, {44, 77}, {44, 88}, {44, 99}, {55, 0}, {55, 11}, {55, 22}, {55, 33}, {55, 44}, {55, 55}, {55, 66}, {55, 77}, {55, 88}, {55, 99}, {66, 0}, {66, 11}, {66, 22}, {66, 33}, {66, 44}, {66, 55}, {66, 66}, {66, 77}, {66, 88}, {66, 99}, {77, 0}, {77, 11}, {77, 22}, {77, 33}, {77, 44}, {77, 55}, {77, 66}, {77, 77}, {77, 88}, {77, 99}, {88, 0}, {88, 11}, {88, 22}, {88, 33}, {88, 44}, {88, 55}, {88, 66}, {88, 77}, {88, 88}, {88, 99}, {99, 0}, {99, 11}, {99, 22}, {99, 33}, {99, 44}, {99, 55}, {99, 66}, {99, 77}, {99, 88}, {99, 99}}

Óptima Duración Del Tour: $1110$

Óptima Tour:

Ejemplo 2: generados al Azar, a continuación, refinado.

Conjunto de las moscas:

{{0, 0}, {1, 48}, {3, 68}, {4, 39}, {5, 96}, {77, 70}, {6, 51}, {23, 89}, {89, 36}, {8, 64}, {10, 17}, {10, 48}, {22, 100}, {68, 31}, {59, 80}, {15, 42}, {25, 16}, {16, 54}, {19, 12}, {30, 92}, {21, 48}, {22, 63}, {22, 69}, {22, 79}, {24, 55}, {25, 84}, {26, 73}, {25, 42}, {75, 52}, {12, 72}, {30, 44}, {30, 82}, {76, 14}, {32, 10}, {32, 25}, {32, 59}, {35, 76}, {36, 38}, {67, 84}, {37, 56}, {37, 99}, {38, 12}, {39, 4}, {39, 87}, {40, 26}, {42, 69}, {43, 44}, {44, 31}, {44, 80}, {45, 98}, {46, 13}, {66, 0}, {47, 53}, {38, 31}, {49, 25}, {49, 67}, {51, 94}, {53, 57}, {56, 22}, {58, 51}, {54, 34}, {60, 42}, {61, 65}, {62, 8}, {64, 18}, {65, 58}, {67, 5}, {67, 70}, {69, 21}, {69, 56}, {1, 30}, {72, 7}, {15, 28}, {72, 63}, {74, 23}, {49, 34}, {75, 41}, {69, 48}, {76, 75}, {59, 92}, {80, 32}, {80, 56}, {80, 82}, {81, 44}, {84, 39}, {85, 2}, {82, 22}, {25, 93}, {88, 80}, {90, 47}, {91, 70}, {23, 37}, {93, 98}, {53, 0}, {97, 0}, {98, 41}, {98, 62}, {50, 74}, {99, 84}, {100, 31}, {28, 98}}

Óptima Duración Del Tour: $1252$

Óptima Tour:

(Nota: Este tour tiene una duración estimada de $1360$ utilizando el valor predeterminado (no óptimo) método usado en la primera parte.)

Answer 3

La utilización de @Alexis Olson código de mathematica, se me ocurrió la siguiente distribución de longitudes de ruta (se muestra en rojo) y conspiraron en contra de la distribución normal (que se muestra en azul, utilizando la media y la desviación estándar de la longitud del recorrido). Parece estar de acuerdo muy bien (probado en 5000 caminos).

Answer 4

Yo tenía una solución diferente de la respuesta por user21820 para el asintótica límite superior para un $n\times n$ cuadrícula. Voy a esbozar brevemente aquí:

Tomamos el de la izquierda-la mayoría de los restantes $\approx\sqrt{n}$ puntos (que vamos a llamar a un bloque), y recorrer desde la parte superior a la parte inferior, que sale a la izquierda/derecha cuando sea necesario. Repita, pero cambiar la dirección vertical alternativamente. Total de movimiento vertical es $\text{number of repeats}\times (n-1)$ y el total de movimiento horizontal es $\le\sum_{\text{block}}{\text{width of block}\times(\text{number of points in block}+1)}$. Máximo es $\approx 2n\sqrt{n}$.

Edit: Esta solución es un poco peor que el otro, y por lo tanto no puede responder a la pregunta acerca de 2000 se mueve.