Einführung

Du bist alleine auf einer Insel. Der Rest der Menschheit ist tot ( wahrscheinlich aufgrund des Fehlers im Code von user12345 ). Die Zombie-Piraten-Horde hat Ihre Insel erreicht und sie ist endlos. Es ist Zeit, Arsch zu treten oder Kaugummi zu kauen, und Sie sind alle aus Kaugummi.

Problem

Unser Schreckensszenario wird durch zwei ganze Zahlen in einer Zeile beschrieben, mund n. Auf Ihrer Insel befinden sich Außenposten mit einer eindeutigen Nummer von 1 bis m. Die folgenden nZeilen enthalten jeweils drei ganze Zahlen, x, yund z, durch einen Raum getrennt. xund ysind die eindeutigen IDs von zwei Außenposten undz die Anzahl der Zombies, die auf dem Pfad zwischen ihnen angetroffen werden.

Wenn du einen Weg zurücklegst, verlierst du zMunition und tötestz Zombies. Wenn Sie den gleichen Weg wieder zurücklegen, werden Sie leider auf die gleiche Anzahl von Zombies stoßen. Alle Außenposten generieren bei jedem Befahren eines Pfades +1 Munition. Sie beginnen mit 100 Munition bei Außenposten 1. Alle Außenposten beginnen mit 0 Munition. Sie sterben sofort, wenn es keinen Weg gibt, für den Ihre Munition größer ist als die Anzahl der Zombies auf diesem Weg, und der Rest Ihrer Munition wird in Kills umgewandelt. So ist dein letzter Standpunkt.

Schreiben Sie ein Programm, das die maximale Anzahl von Zombies ausgibt, die Sie für ein bestimmtes Szenario töten können. Wenn Sie eine unendliche Anzahl von Zombies töten können, geben Sie einfach aus x.

Beispiel Eingabe

5 6
1 2 4
2 3 4
3 1 4
2 4 10
2 5 10
1 1 50

Beispielausgabe

x

Annahmen

• Ein Pfad wird zwischen zwei gültigen Außenposten liegen. Das heißt 1 <= x/ y<=m
• Wenn ein Pfad zwischen xund ynicht aufgeführt ist, kann er nicht befahren werden
• Ein Pfad ist bidirektional
• 1 m<<= 100
• 1 n<<= 500
• Die Eingabe muss über stdin erfolgen, aus einer Datei gelesen oder als einziges Argument für das Programm akzeptiert werden und genau dem Format des Beispiels entsprechen
• Die Laufzeit Ihres Programms kann beliebig groß sein, muss aber bestimmbar begrenzt sein

Der Code mit den wenigsten Zeichen gewinnt!

Java ( weniger grotesk: 8415 5291 3301)

Okay. Im Grunde ist es mir peinlich, dass niemand eine Lösung vorgelegt hat.Also habe ich vor ein paar Tagen angefangen, dieses Problem zu lösen, b / c, es ist großartig. . Folgen Sie diesem Link, um meinen Fortschritt über GitHub zu verfolgen.

Bearbeiten

Neue Solver-Version, viel mehr "Golf", mit korrigiertem Zyklus-Checker, wie von MT0 identifiziert. Es werden auch Weiterleitungsrouten unterstützt, die durch Ändern der verfügbaren Speicherkapazität für die VM angepasst werden können. Neueste BIG Bearbeitung: Ich habe festgestellt, dass ich noch ein paar kleine Indexfehler und vorzeitige Optimierungen hatte, die dazu führten, dass eine große Anzahl von Gewinnarten nicht berücksichtigt wurde. Also das ist behoben, sorgfältig. Die neue Version ist kleiner und niedriger. Für unsere Referenzroutejava -Xmx2GB ZombieHordeMin ist der Trick ganz gut (seien Sie gewarnt, es wird eine Weile dauern).

Cooles Faktoid

In einer faszinierenden Twist gibt es viele Lösungen endlich 24 und mein Löser findet man sich von MT0 wird , aber im Prinzip identisch, mit der Ausnahme , dass es beginnt , durch die die anderen Vorposten verbunden zu besuchen 1. Faszinierend! Völlig gegen die menschliche Intuition, aber vollkommen gültig.

Lösungs-Highlights

Also hier ist meins. Es ist (teilweise) Golf, b / c es ist ein exponentieller, fast Brute-Force-Solver. Ich verwende einen IDDFS-Algorithmus (iterative Deepening Depth First Search), daher ist er ein großartiger allgemeiner Löser, der nicht überspringt und daher beide Teile der OP-Frage löst , nämlich:

• Wenn eine Gewinnroute gefunden wird (unendliche Zombies), gib 'x' aus.
• Wenn alle Routen mit dem Tod enden (endliche Zombies), wird die größte Anzahl der getöteten Zombies ausgegeben.

Gib ihm genug Kraft, Gedächtnis und Zeit, und es wird genau das tun, sogar Slow-Death-Maps. Ich habe mehr Zeit damit verbracht, diesen Solver zu verbessern, und obwohl mehr getan werden kann, ist es jetzt ein bisschen besser. Ich habe auch den Ratschlag von MT0 zur besten Lösung für unendliche Zombies integriert und mehrere vorzeitige Optimierungen aus meinem Win-Checker entfernt, die verhindert haben, dass die vorherige Version ihn findet, und jetzt finde ich tatsächlich eine sehr ähnliche Lösung wie die beschriebene MT0.

Ein paar weitere Highlights:

• Wie bereits erwähnt, wird ein IDDFS verwendet, um die kürzestmögliche Gewinnroute zu finden.
• Da es sich im Kern um eine DFS handelt, wird auch ermittelt, ob jede Route mit dem Tod unseres Helden endet, und die "beste" Route in Bezug auf die meisten getöteten Zombies verfolgt. Stirb als Held!
• Ich habe den Algorithmus instrumentiert, um es interessanter zu machen, Removed für Golfzwecke anzusehen . Folgen Sie einem der Links zu Github, um die ungolfed version zu sehen.
• Es gibt auch eine Reihe von Kommentaren, zögern Sie also nicht, Ihre eigene Lösung neu zu implementieren, indem Sie auf meinem Ansatz aufbauen, oder zeigen Sie mir, wie es gemacht werden sollte!
• Speicheradaptives Weiterleiten von Routen
  • Verfolgt bis zum verfügbaren Systemspeicher "Endrouten", die nicht zum Tod geführt haben.
  • Mithilfe einer ausgefallenen Routenkomprimierungs- und -dekomprimierungsroutine wird der Fortschritt einer vorherigen IDDFS-Iteration wiederhergestellt, um zu verhindern, dass alle zuvor besuchten Routen erneut erkannt werden.
  • Als absichtlicher Nebenbonus fungiert er als Sackgasse. Sackgassenrouten werden nicht gespeichert und werden in zukünftigen Tiefen von IDDFS nie wieder aufgesucht.

Geschichte des Lösers

• Ich habe ein paar einstufige Look-Ahead-Algorithmen ausprobiert, und während sie in sehr einfachen Szenarien funktionieren, fallen sie letztendlich flach.
• Dann habe ich einen zweistufigen Look-Ahead-Algorithmus ausprobiert, der .. unbefriedigend war.
• Ich habe dann angefangen, einen n-Step-Lookahead zu erstellen, als ich erkannte, dass dieser Ansatz auf DFS reduziert werden kann, aber DFS weitaus eleganter ist.
• Während des Aufbaus der DFS kam mir der Gedanke, dass IDDFS sicherstellen würde, (a) die beste HERO-Route (Todesroute) oder (b) den ersten Siegerzyklus zu finden.
• Es stellte sich heraus, dass das Erstellen eines Win-Cycle-Checkers einfach ist, aber ich musste einige sehr sehr falsche Iterationen durchlaufen, bevor ich zu einem nachweislich erfolgreichen Checker kam.
• Berücksichtigt den Win-Pfad von MT0, um drei Zeilen vorzeitiger Optimierung zu entfernen, die meinen Algorithmus blind gemacht haben.
• Es wurde ein adaptiver Routing-Caching-Algorithmus hinzugefügt, der den gesamten verfügbaren Speicher verwendet, um unnötiges Wiederherstellen der Arbeit zwischen IDDFS-Aufrufen zu verhindern, und um auch Sackgassen-Routen bis zur Speichergrenze zu löschen.

Der (Golf-) Code

Weiter zum Code ( hier oder hier die ungolfed version holen ):

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

Holen Sie sich den Code von Github hier, um alle Änderungen zu verfolgen, die ich vornehme. Hier sind einige andere Karten, die ich verwendet habe.

Ausgabebeispiel

Beispielausgabe für Referenzlösung:

    $ 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

Lesen Sie die Route Ausgabe wie folgt: step: source, route-to-get-here- ammo. In der obigen Lösung würden Sie es folgendermaßen lesen:

• Bei Schritt 0, am Außenposten 1mit Munition 100.
• 1Verwenden Sie bei Schritt die Route 1, um zum Außenposten 3mit Endmunition zu gelangen97
• 2Verwenden Sie bei Schritt die Route 1, um zum Außenposten 1mit Endmunition zu gelangen95
• ...

Notizen schließen

Ich hoffe, ich habe meine Lösung schwerer zu schlagen gemacht, aber BITTE VERSUCHEN! Verwenden Sie es gegen mich, fügen Sie Parallelverarbeitung, bessere Graphentheorie usw. hinzu. Ein paar Dinge, die ich herausgefunden habe, könnten diesen Ansatz verbessern :

• Reduzieren Sie die Schleifen aggressiv, um unnötige Runderneuerungen im Verlauf des Algorithmus zu vermeiden.
  • Ein Beispiel: Betrachten Sie in dem Beispielproblem die Schleifen 1-2-3 und andere Permutationen als "einen Schritt", damit wir schneller zum Ende des Zyklus gelangen.
  • Wenn Sie sich beispielsweise an Knoten 1 befinden, können Sie entweder (a) zu 2 gehen, (b) zu 1 gehen, (c) 1-2-3 als einen Schritt durchlaufen und so weiter. Dies würde es einem Gelösten ermöglichen, die Tiefe in die Breite zu falten, die Anzahl der Routen in einer bestimmten Tiefe zu erhöhen, aber die Zeit bis zur Lösung für lange Zyklen erheblich zu verkürzen.
• tote Strecken aussortieren. Meine derzeitige Lösung "erinnert" sich nicht daran, dass eine bestimmte Route in einer Sackgasse liegt, und muss sie jedes Mal neu entdecken. Es wäre besser, den frühesten Moment auf einem Weg zu verfolgen, bei dem der Tod sicher ist, und niemals darüber hinauszugehen. machte dies...
• Wenn Sie vorsichtig sind, können Sie die Dead-Route-Culling-Methode als Sub-Route-Culling anwenden. Wenn zum Beispiel 1-2-3-4 immer zum Tod führt und der Löser dabei ist, die Route 1-3-1-2-3-4 zu testen, sollte er sofort aufhören, diesen Pfad herunterzufahren, da das Ende garantiert ist in enttäuschung. Es wäre immer noch möglich, die Anzahl der Abschüsse mit etwas sorgfältiger Mathematik zu berechnen.
• Jede andere Lösung, bei der Speicher gegen Zeit eingetauscht wird oder die aggressive Vermeidung von Sackgassen. tat dies auch!

Einige abstrakte Hinweise zu einer Lösung

Wenn ich Zeit habe, werde ich das in einen Algorithmus umwandeln ...

Für einen gegebenen Graphen Gexistiert dann ein verbundener Subgraphen, G'der die Stadt enthält 1. Wenn es eine unendliche Lösung gibt, gibt es einen zusammenhängenden Untergraphen, G''der Städte und G'enthältVP Pfade .

Die Pfade Pvon G''können so unterteilt werden, dass sie {p}einen Pfad enthalten, der nur minimale Kosten für alle Pfade in sich hat Pund P/{p}alle anderen Pfade (die einen Spanning Tree oder möglicherweise einen Zyklus bilden) sind. Wenn wir davon ausgehen , dass pkein Schleifenkante (beide Enden an der gleichen Stadt verbindet) , dann wird es zwei Städte verbinden ( v1und v2) und Kosten hat cMunition dann Sie (der Überlebende) kann dann Verfahrweg von v1bis v2und zurück zu einem Gesamtpreis von 2cMunition und dies wird die Munition in allen Städten von 2 (für eine Steigerung von insgesamt erhöhen 2|V|innerhalb G''- von denen einige gesammelt wurde , wird von v1und v2).

Wenn Sie reisen von v1bis v2zu und wieder v1mehr ( m) und dann mal einen Ausflug aus v1entlang der Kanten P/{p}alle Städte außer zu besuchen v1und v2vor der Rückkehr in v1und dies dauert nPfade zu erreichen (wo |P/{p}| ≤ n ≤ 2|P/{p}|da sollte man sich nie einen Weg mehr zu durchqueren muß als zweimal) mit einem Preis von kund erhalten die Städte 2m|V|Munition (von denen wiederum einige während der Durchquerung gesammelt wurden).

Anhand all dessen können Sie erkennen, ob möglicherweise eine unendliche Lösung möglich ist, wenn die Kosten k + 2mcgleich oder niedriger als die Gesamtbelohnung sind 2(m+n)|V|.

Das Problem hat eine zusätzliche Komplexität:

• Möglicherweise müssen Sie von der Startstadt 1nach{p} zur ersten Iteration und diese Kosten berücksichtigen. und
• Sie müssen auch sicherstellen, dass die mund nniedrig genug sind, damit Ihnen nicht die Munition ausgeht, bevor Sie die erste Iteration durchlaufen können, da die erste Iteration höhere Kosten verursacht als die nachfolgenden Iterationen.

Dies führt zu einer kostenneutralen Lösung mit 24 Pfaden für das Beispiel in der Frage (die Zahlen sind die besuchten Städte):

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 ...