Java ( moins grotesque: 8415 5291 3301)

D'accord. Fondamentalement, je suis gêné, personne n'a soumis de solution. Il y a quelques jours, j'ai commencé à essayer de résoudre ce problème, b / c c'est super. . Suivez ce lien pour voir mes progrès à ce sujet via GitHub.

modifier

Nouvelle version du solveur, beaucoup plus "golfée", avec correcteur de cycle corrigé identifié par MT0. Il prend également en charge les itinéraires d'avance rapide, ajustables en modifiant la quantité de mémoire disponible pour la machine virtuelle. Dernière modification BIG : j'ai réalisé que j'avais quelques autres petites erreurs d'index et des optimisations prématurées, ce qui s'est traduit par un échec à considérer un assez grand nombre de types de gains. C'est donc fixe, soigneusement. La nouvelle version est à la fois plus petite et inférieure. Pour notre itinéraire de référence,java -Xmx2GB ZombieHordeMin fait très bien l'affaire (attention, cela prendra un certain temps).

Cool factoid

Dans une tournure fascinante, il y a BEAUCOUP de solutions à la longueur 24, et mon solveur en trouve une différente de MT0, mais identique en principe, sauf qu'elle commence par visiter les autres avant-postes connectés 1. Fascinant! Totalement contre l'intuition humaine, mais parfaitement valable.

Points saillants de la solution

Voici donc le mien. C'est (partiellement) joué au golf, b / c c'est un solveur exponentiel, presque de force brute. J'utilise un algorithme IDDFS (première profondeur d'approfondissement itératif), c'est donc un excellent solveur général qui ne saute pas, donc il résout les deux parties de la question de l'OP, à savoir:

Si une route gagnante est trouvée (zombies infinis), affichez «x».
Si toutes les routes se terminent par la mort (zombies finis), sortez le plus grand nombre de zombies tués.

Donnez-lui suffisamment de puissance, de mémoire et de temps, et il fera exactement cela, même des cartes à mort lente. J'ai passé un peu plus de temps à améliorer ce solveur, et même si plus peut être fait, c'est un peu mieux maintenant. J'ai également intégré les conseils de MT0 sur la meilleure solution de zombies infinis, et supprimé plusieurs optimisations prématurées de mon vérificateur de gains qui empêchaient la version précédente de la trouver, et maintenant je trouve en fait une solution très similaire à celle décrite par MT0.

Quelques autres points saillants:

Comme mentionné, utilise un IDDFS pour trouver l'itinéraire gagnant le plus court possible.
Puisqu'il est au cœur d'un DFS, il découvrira également si chaque route se termine par la mort de notre héros, et garde la trace de la "meilleure" route en termes de la plupart des zombies tués. Meurs un héros!
~~J'ai instrumenté l'algorithme pour le rendre plus intéressant à regarder~~ Supprimé à des fins de golf. Suivez l'un des liens vers github pour voir la version non golfée.
~~Il y a également un certain nombre de commentaires, alors n'hésitez pas à réimplémenter pour votre propre solution en s'appuyant sur mon approche, ou montrez-moi comment cela doit être fait!~~
Avance rapide de l'itinéraire à mémoire adaptative
- Jusqu'à la mémoire système disponible, gardera une trace des "itinéraires de fin" qui n'ont pas entraîné la mort.
- À l'aide d'une routine de compression et de décompression de route sophistiquée, la progression d'une itération antérieure d'IDDFS est restaurée pour empêcher la redécouverte de toutes les routes visitées précédemment.
- En tant que bonus latéral intentionnel, agit comme un abattage de route sans issue. Les routes sans issue ne sont pas stockées et ne seront plus jamais visitées dans les futures profondeurs d'IDDFS.

Histoire du solveur

J'ai essayé un tas d'algorithmes d'anticipation en une étape, et même si pour des scénarios très simples, ils fonctionneraient, ils finissent par tomber à plat.
Ensuite, j'ai essayé un algorithme d'anticipation en deux étapes, ce qui était .. insatisfaisant.
J'ai ensuite commencé à créer un lookahead en n étapes, quand j'ai reconnu que cette approche était réductible à DFS, mais DFS est beaucoup ... plus élégant.
Lors de la construction de la DFS, il m'est venu à l'esprit que l'IDDFS garantirait (a) la meilleure voie HERO (mort) ou (b) le premier cycle gagnant.
Il s'avère que la construction d'un vérificateur de cycle de victoire est facile, mais j'ai dû passer par plusieurs itérations très très erronées avant d'arriver à un vérificateur qui a prouvé son succès.
Prise en compte du chemin gagnant de MT0 pour supprimer trois lignes d'optimisation prématurée qui ont rendu mon algorithme aveugle.
Ajout d'un algorithme adaptatif de mise en cache de route qui utilisera toute la mémoire que vous lui donnez pour éviter de refaire inutilement le travail entre les appels IDDFS, et élimine également les routes sans issue jusqu'aux limites de la mémoire.

Le code (golfé)

Passons au code (obtenez la version non golfée ici ou ici ):

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);}}

Obtenez le code de github ici, pour suivre toutes les modifications que j'apporte. Voici quelques autres cartes que j'ai utilisées.

Exemple de sortie

Exemple de sortie pour la solution de référence:

    $ 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

Lisez la sortie de l'itinéraire comme ceci step:: source, route-to-get-here- ammo. Donc, dans la solution ci-dessus, vous le liriez comme:

À l'étape 0, à l'avant-poste 1avec des munitions 100.
À l'étape 1, utilisez l'itinéraire 1pour vous rendre à l'avant-poste 3avec des munitions de fin97
À l'étape 2, utilisez l'itinéraire 1pour vous rendre à l'avant-poste 1avec des munitions de fin95
...

Notes de clôture

J'espère donc avoir rendu ma solution plus difficile à battre, mais S'IL VOUS PLAÎT ESSAYEZ! Utilisez-le contre moi, ajoutez un traitement parallèle, une meilleure théorie des graphes, etc. Quelques éléments que je pense pourraient améliorer cette approche:

"réduire" de manière agressive les boucles pour supprimer le rechapage inutile au fur et à mesure que l'algorithme progresse.
- Un exemple: dans l'exemple de problème, considérez les boucles 1-2-3 et les autres permutations comme "une étape", afin que nous puissions avancer plus rapidement vers la fin du cycle.
- Par exemple, si vous êtes au nœud 1, vous pouvez soit (a) aller à 2, (b) aller à 1, (c) passer par 1-2-3 en une seule étape et ainsi de suite. Cela permettrait à un résolu de plier la profondeur en largeur, augmentant le nombre de routes à une profondeur particulière mais accélérant considérablement le temps de solution pour les longs cycles.
abattre les routes mortes. Ma solution actuelle ne "se souvient" pas qu'un itinéraire particulier est sans issue et doit le redécouvrir à chaque fois. Il serait préférable de garder une trace du premier moment sur une route dont la mort est certaine, et de ne jamais progresser au-delà. a fait ça ...
si vous faites attention, vous pouvez appliquer l'abattage de route morte en tant qu'élimination de sous-route. Par exemple, si 1-2-3-4 entraîne toujours la mort et que le solveur est sur le point de tester l'itinéraire 1-3-1-2-3-4, il doit immédiatement arrêter de descendre ce chemin car il est garanti qu'il se terminera déçu. Il serait toujours possible de calculer le nombre de victimes, avec quelques calculs minutieux.
~~Toute autre solution qui échange la mémoire contre du temps ou permet d'éviter de manière agressive de suivre des voies sans issue.~~ a fait ça aussi!

ProgrammerDan
la source

Bonne réponse! Qui a besoin de jouer à son code alors qu'il est le seul à pouvoir résoudre le problème? Je suis maintenant motivé pour écrire ma propre solution, donc je vais y travailler.

Rainbolt

Excellent, c'est ce que j'espérais que cela ferait. N'hésitez pas à emprunter / voler quoi que ce soit de ma réponse que vous trouverez utile! Bien sûr, j'espère que d'autres personnes que moi-même et OP essaieront de résoudre: P

ProgrammerDan

J'ai été détourné et j'ai commencé à réduire votre code. Si vous pensiez que votre réponse était grotesque auparavant, vérifiez ceci: tny.cz/17ef0b3a . Encore un travail en cours.

Rainbolt

Haha, vous avez vraiment été détourné. Vous cherchez bien (horriblement approprié pour le code-golf? Vous savez de quoi je parle) jusqu'à présent!

ProgrammeurDan

@Rusher Vous avez de la chance jusqu'à présent? J'ai quelques idées d'améliorations que j'ai préparées, y compris une technique de compression de représentation d'itinéraire et un moyen d'avancer rapidement à travers des itinéraires déjà traités (jusqu'à un certain point).

ProgrammerDan

Quelques notes abstraites sur une solution

Si j'ai le temps, je le convertirai en algorithme ...

Pour un graphe donné, Gil existe alors un sous-graphe connecté G'qui contient la ville 1. S'il y a une solution infinie alors il existera un sous-graphe connexe G''de G'qui contient des Vvilles et des Pchemins.

Les chemins Pd' accès G''peuvent être partitionnés de manière à {p}contenir un chemin d'accès qui a alors un coût minimal de tous les chemins d'accès Pet P/{p}constitue tous les autres chemins (formant un arbre couvrant ou éventuellement un cycle). Si nous partons du principe que pn'est pas un bord en boucle (reliant les deux extrémités de la même ville), il reliera deux villes ( v1et v2) et a coûté des cmunitions alors vous (le survivant) peut alors traverser de v1à v2et revenir à un coût total de 2cmunitions et cela augmentera les munitions dans toutes les villes de 2 (pour une augmentation totale de l' 2|V|intérieur G''- dont certaines auront été collectées auprès de v1et v2).

Si vous voyagez de v1à v2et revenir à v1plusieurs ( mfois, puis prendre un voyage de) le v1long des bords P/{p}à visiter toutes les villes autres que v1et v2avant de revenir à v1ce qui prend des nchemins pour atteindre (où |P/{p}| ≤ n ≤ 2|P/{p}|puisque vous ne devriez jamais avoir à traverser une voie plus plus de deux fois) avec un coût de ket les villes gagneront des 2m|V|munitions (dont une partie aura été récupérée lors de la traversée).

Compte tenu de tout cela, vous pouvez savoir si une solution infinie est potentiellement possible si le coût k + 2mcest égal ou inférieur à la récompense totale 2(m+n)|V|.

Il y a une complexité supplémentaire au problème en ce que:

vous devrez peut-être voyager de la ville de départ 1à {p}la première itération et prendre en compte ce coût; et
vous devez également vous assurer que le met nsont suffisamment bas pour ne pas manquer de munitions avant de pouvoir passer par la première itération car la première itération aura un coût plus élevé que les itérations suivantes).

Cela conduit à une solution neutre en termes de coûts sur 24 voies pour l'exemple de la question (les chiffres sont les villes visitées):

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
la source

Une petite chose à ajouter - vous devrez peut-être envisager de boucler les bords avec un coût de 1, car ces bords seuls constituent une condition de victoire si vous pouvez les atteindre à temps.

Rainbolt

La position finale - Vaincre la horde de zombies

Réponses:

Java ( moins grotesque: 8415 5291 3301)

modifier

Cool factoid

Points saillants de la solution

Histoire du solveur

Le code (golfé)

Exemple de sortie

Notes de clôture

Quelques notes abstraites sur une solution