Java ( menos grotesco: 8415 5291 3301)

Okay. Básicamente, me da vergüenza que nadie haya presentado una solución. Hace unos días comencé a tratar de resolver este problema, b / c es genial. . Sigue ese enlace para ver mi progreso en él a través de GitHub.

Editar

Nueva versión de solucionador, mucho más "golfizada", con corrector de ciclo corregido identificado por MT0. También admite rutas de avance rápido, sintonizables cambiando la cantidad de memoria disponible para la VM. Última edición GRANDE : me di cuenta de que tenía algunos otros pequeños errores de índice y optimizaciones prematuras, lo que resultó en una falla al considerar una gran cantidad de tipos de victorias. Entonces eso está arreglado, con cuidado. La nueva versión es más pequeña y más abajo. Para nuestra ruta de referencia,java -Xmx2GB ZombieHordeMin el truco funciona bastante bien (ten en cuenta que tomará un tiempo).

Factoid fresco

En un giro fascinante, hay MUCHAS soluciones con una longitud de 24, y mi solucionador encuentra una diferente de las MT0, pero idéntica en principio, excepto que comienza visitando los otros puestos avanzados conectados 1. ¡Fascinante! Totalmente contraria a la intuición humana, pero perfectamente válida.

Soluciones destacadas

Así que aquí está el mío. Es (parcialmente) golfizado, b / c es un solucionador exponencial de fuerza casi bruta. Utilizo un algoritmo IDDFS (profundización iterativa de primera búsqueda de profundidad), por lo que es un gran solucionador general que no se salta, por lo que resuelve ambas partes de la pregunta del OP, a saber:

Si se encuentra una ruta ganadora (zombis infinitos), muestra 'x'.
Si todas las rutas terminan en muerte (zombis finitos), genera la mayor cantidad de zombis muertos.

Dale suficiente poder, memoria y tiempo, y hará exactamente eso, incluso mapas de muerte lenta. Pasé un poco más de tiempo mejorando este solucionador, y aunque se puede hacer más, ahora es un poco mejor. También integré el consejo de MT0 sobre la mejor solución de zombies infinitos, y eliminé varias optimizaciones prematuras de mi comprobador de victorias que impedían que la versión anterior lo encontrara, y ahora de hecho encuentro una solución muy similar a la que MT0 describió.

Algunos otros puntos destacados:

Como se mencionó, utiliza un IDDFS para encontrar la ruta ganadora más corta posible.
Como se trata de un DFS, también descubrirá si cada ruta termina con la muerte de nuestro héroe, y realiza un seguimiento de la "mejor" ruta en términos de la mayoría de los zombis asesinados. ¡Morir como héroe!
~~He instrumentado el algoritmo para que sea más interesante ver~~ Removed con fines de golf. Siga uno de los enlaces a github para ver la versión sin golf.
~~También hay una serie de comentarios, así que siéntase libre de volver a implementar su propia solución basándose en mi enfoque, ¡o muéstreme cómo debe hacerse!~~
Avance rápido de ruta adaptable a la memoria
- Hasta la memoria del sistema disponible, realizará un seguimiento de las "rutas finales" que no resultaron en la muerte.
- Usando una rutina de compresión y descompresión de ruta elegante, se restaura el progreso de una iteración previa de IDDFS para evitar el redescubrimiento de todas las rutas visitadas anteriormente.
- Como una bonificación secundaria intencional, actúa como un descarte de ruta sin salida. Las rutas sin salida no se almacenan, y nunca se volverán a visitar en futuras profundidades de IDDFS.

Historia del solucionador

Probé un montón de algoritmos de anticipación en un solo paso, y si bien para escenarios muy simples funcionarían, en última instancia, fracasan.
Luego probé un algoritmo de anticipación de dos pasos, que fue ... insatisfactorio.
Luego comencé a construir una búsqueda anticipada de n pasos, cuando reconocí que este enfoque es reducible a DFS, pero DFS es mucho más elegante.
Mientras construía el DFS, se me ocurrió que IDDFS aseguraría (a) encontrar la mejor ruta HÉROE (muerte) o (b) el primer ciclo ganador.
Resulta que construir un verificador de ciclo de ganancia es fácil, pero tuve que pasar por varias iteraciones muy erróneas antes de llegar a un verificador probadamente exitoso.
Se incluyó en la ruta ganadora de MT0 para eliminar tres líneas de optimización prematura que hicieron que mi algoritmo quedara ciego.
Se agregó un algoritmo de enrutamiento de enrutamiento adaptativo que utilizará toda la memoria que le dé para evitar rehacer innecesariamente el trabajo entre llamadas IDDFS, y también elimina las rutas sin salida hasta los límites de la memoria.

El código (golfizado)

En el código (obtenga la versión no protegida aquí o aquí ):

import java.util.*;public class ZombieHordeMin{int a=100,b,m,n,i,j,z,y,D=0,R,Z,N;int p[][][];Scanner in;Runtime rt;int[][]r;int pp;int dd;int[][]bdr;int ww;int[][]bwr;int[][]faf;int ff;boolean ffOn;public static void main(String[]a){(new ZombieHordeMin()).pR();}ZombieHordeMin(){in=new Scanner(System.in);rt=Runtime.getRuntime();m=in.nextInt();N=in.nextInt();p=new int[m+1][m+1][N+1];int[]o=new int[m+1];for(b=0;b<N;b++){i=in.nextInt();j=in.nextInt();z=in.nextInt();o[i]++;o[j]++;D=(o[i]>D?o[i]:D);p[i][j][++p[i][j][0]]=z;if(i!=j)p[j][i][++p[j][i][0]]=z;D=(o[j]>D?o[j]:D);}m++;}void pR(){r=new int[5000][m+3];r[0][0]=a;Arrays.fill(r[0],1,m,1);r[0][m]=1;r[0][m+1]=0;r[0][m+2]=0;ww=-1;pp=dd=0;pR(5000);}void pR(int aMD){faf=new int[D][];ff=0;ffOn=true;for(int mD=1;mD<=aMD;mD++){System.out.printf("Checking len %d\n",mD);int k=ffR(0,mD);if(ww>-1){System.out.printf("%d x\n",ww+1);for(int win=0;win<=ww;win++)System.out.printf(" %d:%d,%d-%d",win,bwr[win][0],bwr[win][1],bwr[win][2]);System.out.println();break;}if(k>0){System.out.printf("dead max %d kills, %d steps\n",pp,dd+1);for(int die=0;die<=dd;die++)System.out.printf(" %d:%d,%d-%d",die,bdr[die][0],bdr[die][1],bdr[die][2]);System.out.println();break;}}}int ffR(int dP,int mD){if(ff==0)return pR(dP,mD);int kk=0;int fm=ff;if(ffOn&&D*fm>rt.maxMemory()/(faf[0][0]*8+12))ffOn=false;int[][]fmv=faf;if(ffOn){faf=new int[D*fm][];ff=0;}for(int df=0;df<fm;df++){dS(fmv[df]);kk+=pR(fmv[df][0],mD);}fmv=null;rt.gc();return kk==fm?1:0;}int pR(int dP,int mD){if(dP==mD)return 0;int rT=0;int dC=0;int src=r[dP][m];int sa=r[dP][0];for(int dt=1;dt<m;dt++){for(int rut=1;rut<=p[src][dt][0];rut++){rT++;r[dP+1][0]=sa-p[src][dt][rut]+r[dP][dt];for(int cp=1;cp<m;cp++)r[dP+1][cp]=(dt==cp?1:r[dP][cp]+1);r[dP+1][m]=dt;r[dP+1][m+1]=rut;r[dP+1][m+2]=r[dP][m+2]+p[src][dt][rut];if(sa-p[src][dt][rut]<1){dC++;if(pp<r[dP][m+2]+sa){pp=r[dP][m+2]+sa;dd=dP+1;bdr=new int[dP+2][3];for(int cp=0;cp<=dP+1;cp++){bdr[cp][0]=r[cp][m];bdr[cp][1]=r[cp][m+1];bdr[cp][2]=r[cp][0];}}}else{for(int chk=0;chk<=dP;chk++){if(r[chk][m]==dt){int fR=chk+1;for(int cM=0;cM<m+3;cM++)r[dP+2][cM]=r[dP+1][cM];for(;fR<=dP+1;fR++){r[dP+2][0]=r[dP+2][0]-p[r[dP+2][m]][r[fR][m]][r[fR][m+1]]+r[dP+2][r[fR][m]];for(int cp=1;cp<m;cp++)r[dP+2][cp]=(r[fR][m]==cp?1:r[dP+2][cp]+1);r[dP+2][m+2]=r[dP+2][m+2]+p[r[dP+2][m]][r[fR][m]][r[fR][m+1]];r[dP+2][m]=r[fR][m];r[dP+2][m+1]=r[fR][m+1];}if(fR==dP+2&&r[dP+2][0]>=r[dP+1][0]){ww=dP+1;bwr=new int[dP+2][3];for(int cp=0;cp<dP+2;cp++){bwr[cp][0]=r[cp][m];bwr[cp][1]=r[cp][m+1];bwr[cp][2]=r[cp][0];}return 0;}}}dC+=pR(dP+1,mD);if(ww>-1)return 0;}for(int cp=0;cp<m+3;cp++)r[dP+1][cp]=0;}}if(rT==dC)return 1;else{if(ffOn&&dP==mD-1)faf[ff++]=cP(dP);return 0;}}int[]cP(int dP){int[]cmp=new int[dP*2+3];cmp[0]=dP;cmp[dP*2+1]=r[dP][0];cmp[dP*2+2]=r[dP][m+2];for(int zip=1;zip<=dP;zip++){cmp[zip]=r[zip][m];cmp[dP+zip]=r[zip][m+1];}return cmp;}void dS(int[]cmp){int[]lv=new int[m];int dP=cmp[0];r[dP][0]=cmp[dP*2+1];r[dP][m+2]=cmp[dP*2+2];r[0][0]=100;r[0][m]=1;for(int dp=1;dp<=dP;dp++){r[dp][m]=cmp[dp];r[dp][m+1]=cmp[dP+dp];r[dp-1][cmp[dp]]=dp-lv[cmp[dp]];r[dp][m+2]=r[dp-1][m+2]+p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];r[dp][0]=r[dp-1][0]+r[dp-1][cmp[dp]]-p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];lv[cmp[dp]]=dp;}for(int am=1;am<m;am++)r[dP][am]=(am==cmp[dP]?1:dP-lv[am]+1);}}

Obtenga el código de github aquí, para rastrear cualquier cambio que realice. Aquí hay algunos otros mapas que utilicé.

Ejemplo de salida

Ejemplo de salida para la solución de referencia:

    $ java -d64 -Xmx3G ZombieHordeMin > reference_route_corrected_min.out
    5 6 1 2 4 2 3 4 3 1 4 2 4 10 2 5 10 1 1 50
    Checking len 1
    Checking len 2
    Checking len 3
    Checking len 4
    Checking len 5
    Checking len 6
    Checking len 7
    Checking len 8
    Checking len 9
    Checking len 10
    Checking len 11
    Checking len 12
    Checking len 13
    Checking len 14
    Checking len 15
    Checking len 16
    Checking len 17
    Checking len 18
    Checking len 19
    Checking len 20
    Checking len 21
    Checking len 22
    Checking len 23
    Checking len 24
    25 x
     0:1,0-100 1:3,1-97 2:1,1-95 3:2,1-94 4:5,1-88 5:2,1-80 6:4,1-76 7:2,1-68 8:1,1-70 9:2,1-68 10:1,1-66 11:2,1-64 12:1,1-62 13:2,1-60 14:1,1-58 15:2,1-56 16:1,1-54 17:2,1-52 18:1,1-50 19:2,1-48 20:1,1-46 21:2,1-44 22:1,1-42 23:2,1-40 24:1,1-38

Lea la salida de la ruta de esta manera step:: source, route-to-get-here- ammo. Entonces, en la solución anterior, lo leería como:

En el paso 0, en el puesto avanzado 1con munición 100.
En el paso 1, usa la ruta 1para llegar al puesto avanzado 3con munición final97
En el paso 2, usa la ruta 1para llegar al puesto avanzado 1con munición final95
...

Notas de cierre

Por lo tanto, espero haber hecho que mi solución sea más difícil de superar, ¡pero POR FAVOR INTENTE! Úselo en mi contra, agregue un procesamiento paralelo, una mejor teoría de gráficos, etc. Un par de cosas que creo podrían mejorar este enfoque:

"reduce" agresivamente los bucles para cortar el recauchutado innecesario a medida que avanza el algoritmo.
- Un ejemplo: en el problema de ejemplo, considere los bucles 1-2-3 y otras permutaciones como "un paso", de modo que podamos llegar al ciclo final más rápidamente.
- Por ejemplo, si está en el nodo 1, puede (a) ir a 2, (b) ir a 1, (c) pasar por 1-2-3 como un paso y así sucesivamente. Esto permitiría a un resuelto plegar la profundidad en amplitud, aumentando el número de rutas a una profundidad particular, pero acelerando enormemente el tiempo de solución para ciclos largos.
descartar rutas muertas. Mi solución actual no "recuerda" que una ruta en particular tiene un punto muerto y tiene que redescubrirla cada vez. Sería mejor hacer un seguimiento del primer momento en una ruta en la que la muerte es segura, y nunca avanzar más allá. hice esto...
si tiene cuidado, puede aplicar la eliminación de ruta muerta como una eliminación de ruta secundaria. Por ejemplo, si 1-2-3-4 siempre da como resultado la muerte, y el solucionador está a punto de probar la ruta 1-3-1-2-3-4, inmediatamente debe dejar de descender ese camino ya que se garantiza que terminará En decepción. Todavía sería posible calcular el número de asesinatos, con algunas matemáticas cuidadosas.
~~Cualquier otra solución que cambie la memoria por tiempo o que permita evitar agresivamente seguir las rutas sin salida.~~ hizo esto también!

Programador Dan
fuente

¡Buena respuesta! ¿Quién necesita jugar golf su código cuando son los únicos que pueden resolver el problema? Ahora estoy motivado para escribir mi propia solución, así que estaré trabajando en eso.

Rainbolt

Excelente, eso era lo que esperaba que esto hiciera. ¡Siéntase libre de pedir prestado / robar cualquier cosa de mi respuesta que encuentre útil! Aunque, por supuesto, espero que otras personas además de mí y OP intentemos resolver: P

ProgramadorDan

Me desvié y comencé a minificar tu código. Si antes pensabas que tu respuesta era grotesca, mira esto: tny.cz/17ef0b3a . Todavía un trabajo en progreso.

Rainbolt

Jaja, realmente te desvió. ¡Se ve bien (apropiadamente horrible para el golf de código? Ya sabes a lo que me refiero) hasta ahora.

ProgramadorDan

@Rusher ¿Alguna suerte hasta ahora? Tengo algunas ideas para las mejoras que he estado elaborando, incluida una técnica de compresión de representación de ruta y una forma de avanzar rápidamente a través de rutas ya procesadas (hasta cierto punto).

ProgramadorDan

Algunas notas abstractas sobre una solución

Si tengo tiempo, convertiré esto en un algoritmo ...

Para un gráfico dado G, existe un sub-gráfico conectado G'que contiene la ciudad 1. Si hay una solución infinito entonces existirá una sub-gráfico conectado G''de G'que contiene Vpueblos y Pcaminos.

Las rutas Pde G''pueden dividirse de manera tal que {p}contengan una ruta que tenga un costo mínimo de todas las rutas Py que P/{p}sean todas las demás rutas (formando un árbol de expansión o posiblemente un ciclo). Si asumimos que pno es una ventaja bucle (que conecta los dos extremos a la misma ciudad), se conectará dos ciudades ( v1y v2) y tiene costo cmuniciones entonces (el sobreviviente) puede entonces tener travesía de v1a v2y de vuelta a un costo total de 2cmuniciones y esto aumentará la munición en todos los pueblos en 2 (para un aumento total de 2|V|dentro G'', algunos de los cuales se habrán recogido de v1y v2).

Si usted viaja de v1a v2y de vuelta al v1múltiple ( m) veces y luego toma un viaje de v1largo de los bordes P/{p}para visitar todos los pueblos distintos v1y v2antes de regresar a v1lo cual requiere de ncaminos para lograr (donde |P/{p}| ≤ n ≤ 2|P/{p}|ya que nunca debería tener que recorrer un camino más que dos veces) con un costo de ky las ciudades obtendrán 2m|V|municiones (de nuevo, algunas de las cuales se habrán recogido durante el recorrido).

Dado todo esto, puede decir si una solución infinita es potencialmente posible si el costo k + 2mces igual o menor que la recompensa total 2(m+n)|V|.

Hay una complejidad adicional al problema en que:

es posible que deba viajar desde la ciudad inicial 1hasta {p}la primera iteración y tenga en cuenta este costo; y
también debe asegurarse de que my nsean lo suficientemente bajos como para no quedarse sin municiones antes de poder pasar por la primera iteración, ya que la primera iteración tendrá un costo mayor que las iteraciones posteriores).

Esto lleva a una solución de costo neutral de 24 caminos para el ejemplo en la pregunta (los números son las ciudades visitadas):

1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,2,4,2,5,2,3, ... and repeat ...

MT0
fuente

Una pequeña cosa para agregar: es posible que tenga que considerar la posibilidad de bordes en bucle con un costo de 1, porque esos bordes solo forman una condición ganadora si puede alcanzarlos a tiempo.

Rainbolt

The Final Stand - Derrota a la Horda Zombie

Respuestas:

Java ( menos grotesco: 8415 5291 3301)

Editar

Factoid fresco

Soluciones destacadas

Historia del solucionador

El código (golfizado)

Ejemplo de salida

Notas de cierre

Algunas notas abstractas sobre una solución