Java ( mniej groteskowa: 8415 5291 3301)
Dobrze. Zasadniczo jestem zawstydzony, nikt nie przedstawił rozwiązania. Kilka dni temu zacząłem próbować rozwiązać ten problem, b / c to świetnie. . Kliknij ten link, aby obejrzeć moje postępy w GitHub.
Edytować
Nowa wersja solvera, znacznie bardziej „golfowa”, z poprawionym sprawdzaniem cyklu zidentyfikowanym przez MT0. Obsługuje również trasy szybkiego przekazywania, dostrajane przez zmianę ilości pamięci dostępnej dla maszyny wirtualnej. Ostatnia DUŻA edycja: zdałem sobie sprawę, że miałem kilka innych drobnych błędów indeksu i przedwczesnych optymalizacji, co spowodowało, że nie wziąłem pod uwagę dość dużej liczby rodzajów zwycięstw. To jest naprawione, ostrożnie. Nowa wersja jest zarówno mniejsza, jak i niższa. W przypadku naszej trasy odniesienia java -Xmx2GB ZombieHordeMintrik wygląda całkiem nieźle (uwaga, zajmie to trochę czasu).
Fajny faktoid
W fascynującym wydaniu jest WIELE rozwiązań o długości 24, a mój solver znajduje inny niż MT0, ale zasadniczo identyczny, z tym wyjątkiem, że zaczyna się od odwiedzenia innych placówek powiązanych z1 . Fascynujący! Całkowicie przeciwstawia się ludzkiej intuicji, ale doskonale obowiązuje.
Najważniejsze informacje o rozwiązaniu
Więc tu jest moje. Jest (częściowo) grał w golfa, b / c jest wykładniczym solwerem o prawie brutalnej sile. Używam algorytmu IDDFS (iteracyjne pogłębianie pierwszego wyszukiwania), więc jest to świetny ogólny solver, który nie przeskakuje, więc rozwiązuje obie części pytania OP, a mianowicie:
- Jeśli zostanie znaleziona zwycięska trasa (nieskończone zombie), wypisz „x”.
- Jeśli wszystkie trasy zakończą się śmiercią (skończone zombie), wypisz największą liczbę zabitych zombie.
Daj mu wystarczającą moc, pamięć i czas, a zrobi to samo, nawet mapy powolnej śmierci. Spędziłem trochę czasu na ulepszaniu tego solvera i chociaż można zrobić więcej, teraz jest trochę lepiej. Zintegrowałem również porady MT0 dotyczące najlepszego rozwiązania z nieskończonymi zombie i usunąłem kilka przedwczesnych optymalizacji z mojego narzędzia do sprawdzania wygranych, które uniemożliwiły poprzedniej wersji znalezienie tego, a teraz znajduję bardzo podobne rozwiązanie do opisanego MT0.
Kilka innych głównych atrakcji:
- Jak wspomniano, wykorzystuje IDDFS, aby znaleźć najkrótszą możliwą zwycięską trasę.
- Ponieważ jest to podstawa DFS, odkryje również, czy każda trasa kończy się śmiercią naszego bohatera, i śledzi „najlepszą” trasę pod względem większości zabitych zombie. Umrzyj bohaterowi!
Oprzyrządowałem algorytm, aby oglądanie było bardziej interesujące Removed do gry w golfa . Kliknij jeden z linków do github, aby zobaczyć wersję bez golfa.Jest też wiele komentarzy, więc zachęcamy do ponownego wdrożenia własnego rozwiązania w oparciu o moje podejście lub pokaż mi, jak należy to zrobić!- Szybkie przewijanie trasy dostosowane do pamięci
- Do dostępnej pamięci systemowej będzie śledzić „trasy końcowe”, które nie doprowadziły do śmierci.
- Korzystając z fantazyjnej procedury kompresji i dekompresji trasy, przywracany jest postęp z poprzedniej iteracji IDDFS, aby zapobiec ponownemu odkryciu wszystkich wcześniej odwiedzonych tras.
- Jako celowy bonus dodatkowy działa jako ślepy zaułek trasy. Trasy ślepe zaułki nie są przechowywane i nigdy nie będą odwiedzane w przyszłych głębinach IDDFS.
Historia solvera
- Wypróbowałem kilka jednoetapowych algorytmów wybiegających w przyszłość i choć w przypadku bardzo prostych scenariuszy działałyby, ostatecznie się nie sprawdzają.
- Potem wypróbowałem dwustopniowy algorytm wybiegający w przyszłość, który był ... niezadowalający.
- Potem zacząłem budować n-krok do przodu, kiedy zdałem sobie sprawę, że takie podejście można zredukować do DFS, ale DFS jest znacznie ... bardziej elegancki.
- Podczas budowania DFS przyszło mi do głowy, że IDDFS zapewni (a) znalezienie najlepszej trasy HERO (śmierci) lub (b) pierwszego zwycięskiego cyklu.
- Okazuje się, że zbudowanie kontrolera cyklu wygranych jest łatwe, ale musiałem przejść kilka bardzo błędnych iteracji, zanim doszedłem do sprawdzonego kontrolera.
- Uwzględniono w ścieżce wygranych MT0 usunięcie trzech linii przedwczesnej optymalizacji, która spowodowała, że mój algorytm był na nią ślepy.
- Dodano adaptacyjny algorytm buforowania tras, który będzie wykorzystywał całą podaną pamięć, aby zapobiec niepotrzebnemu ponawianiu pracy między wywołaniami IDDFS, a także przerywa ślepe trasy do granic pamięci.
Kod (golfowy)
Do kodu (pobierz wersję bez golfa tutaj lub tutaj ):
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);}}
Pobierz kod z github tutaj, aby śledzić wszelkie zmiany, które wprowadzam. Oto kilka innych map, z których korzystałem.
Przykład wyjściowy
Przykładowe dane wyjściowe dla rozwiązania referencyjnego:
$ 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
Przeczytaj wynik trasy w ten sposób step:: source, route-to-get-here- ammo. W powyższym rozwiązaniu odczytałbyś to jako:
- W kroku
0, na posterunku 1z amunicją 100.
- Na początku
1użyj trasy, 1aby dostać się do placówki 3z zakończoną amunicją97
- Na początku
2użyj trasy, 1aby dostać się do placówki 1z zakończoną amunicją95
- ...
Notatki końcowe
Mam nadzieję, że trudniej pokonałem moje rozwiązanie, ale WYPRÓBUJ! Użyj go przeciwko mnie, dodaj trochę przetwarzania równoległego, lepszą teorię grafów itp. Kilka rzeczy, które według mnie mogą poprawić to podejście:
- agresywnie „redukuj” pętle, aby wycinać niepotrzebne bieżnikowanie w miarę postępu algorytmu.
- Przykład: w przykładzie problemu rozważ pętle 1-2-3 i inne kombinacje jako „jeden krok”, abyśmy mogli szybciej przejść do końca cyklu.
- Na przykład, jeśli jesteś w węźle 1, możesz (a) przejść do 2, (b) przejść do 1, (c) przejść przez 1-2-3 jako jeden krok i tak dalej. Pozwoliłoby to rozwiązanemu na zwijanie głębokości na szerokość, zwiększając liczbę tras na określonej głębokości, ale znacznie przyspieszając czas do rozwiązania dla długich cykli.
wytnij martwe trasy. Moje obecne rozwiązanie nie „pamięta”, że dana trasa jest ślepa i za każdym razem musi ją odkrywać na nowo. Lepiej byłoby śledzić najwcześniejszy moment na drodze, na której śmierć jest pewna, i nigdy nie przekraczać jej. zrobił to...- jeśli jest to ostrożne, można zastosować ubytek trasy martwej jako ubój podtoru. Na przykład, jeśli 1-2-3-4 zawsze kończy się śmiercią, a solver ma zamiar przetestować trasę 1-3-1-2-3-4, powinien natychmiast przestać schodzić z tej ścieżki, ponieważ gwarantuje się, że się skończy rozczarowany. Nadal można obliczyć liczbę zabójstw, zachowując ostrożność.
Każde inne rozwiązanie, które wymienia pamięć na czas lub umożliwia agresywne unikanie podążania ślepymi drogami. też to zrobiłem!
1początkową 0 amunicją? Czy wykres jest niekierunkowy?