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!

ProgrammerDan
źródło

Niezła odpowiedź! Kto musi zagrać w swój kod, gdy tylko oni mogą rozwiązać problem? Jestem teraz zmotywowany do napisania własnego rozwiązania, więc będę nad tym pracował.

Rainbolt

Wspaniale, tak miałem nadzieję. Zapraszam do pożyczania / kradzieży czegokolwiek z mojej odpowiedzi, która okaże się przydatna! Chociaż oczywiście mam nadzieję, że inni ludzie niż tylko ja i OP spróbują rozwiązać: P

ProgrammerDan

Zostałem odsunięty na bok i zacząłem minimalizować twój kod. Jeśli wcześniej myślałeś, że twoja odpowiedź była groteskowa, sprawdź to: tny.cz/17ef0b3a . Wciąż trwają prace.

Rainbolt

Haha, naprawdę się odsunąłeś. Jak dotąd dobrze wyglądasz (odpowiednio przerażająco dla golfa kodowego? Wiesz o co mi chodzi)!

Programmer

@Rusher Jak dotąd powodzenia? Mam kilka pomysłów na ulepszenia, które tworzyłem, w tym technikę kompresji reprezentacji tras i sposób szybkiego przewijania do przodu już przetworzonych tras (do pewnego momentu).

Programmer

Kilka abstrakcyjnych notatek na temat rozwiązania

Jeśli będę miał czas, przekonwertuję to na algorytm ...

Dla danego wykresu Gistnieje połączony pod-wykres G'zawierający miasto 1. Jeżeli istnieje nieskończona rozwiązanie to będzie istnieć podłączony sub-wykres G''z G'zawierający Vmiast i Pdrogami.

Ścieżki Pod G''może być podzielony w taki sposób, {p}zawiera ścieżkę, która ma wówczas minimalne koszty wszystkich ścieżek Pi P/{p}to wszystkie pozostałe ścieżki (tworzące drzewa rozpinającego lub ewentualnie cykl). Jeśli założymy, że pnie jest to pętla krawędzi (łącząca oba końce z tym samym miastem), wówczas połączy dwa miasta ( v1i v2) i będzie kosztować camunicję, wtedy (ocalały) będziecie mogli przejść od i v1do v2tyłu za całkowity koszt 2camunicji a to zwiększy amunicję we wszystkich miastach o 2 (dla całkowitego wzrostu 2|V|wewnątrz G''- niektóre z nich zostaną zebrane z v1i v2).

Jeśli podróżujesz z v1do v2iz powrotem do v1wielokrotności ( m) razy, a następnie wybrać się na wycieczkę z v1wzdłuż krawędzi P/{p}, aby odwiedzić wszystkie miasta inne niż v1a v2przed powrotem do v1a to wymaga nścieżki do osiągnięcia (gdzie |P/{p}| ≤ n ≤ 2|P/{p}|ponieważ nigdy nie powinno trzeba przemierzać ścieżki więcej niż dwa razy) kosztem, ka miasta zyskają 2m|V|amunicję (ponownie niektóre z nich zostaną zebrane podczas przemierzania).

Biorąc to wszystko pod uwagę, możesz stwierdzić, czy nieskończone rozwiązanie jest potencjalnie możliwe, jeśli wtedy koszt k + 2mcjest równy lub niższy niż całkowita nagroda 2(m+n)|V|.

Problem wiąże się z dodatkową złożonością polegającą na tym, że:

być może będziesz musiał podróżować z miasta początkowego 1do {p}pierwszej iteracji i będziesz musiał uwzględnić ten koszt; i
musisz także upewnić się, że mi nsą na tyle niskie, że nie zabraknie ci amunicji, zanim będziesz w stanie przejść przez pierwszą iterację, ponieważ pierwsza iteracja będzie miała wyższy koszt niż kolejne iteracje).

Prowadzi to do 24-ścieżkowego rozwiązania neutralnego pod względem kosztów do przykładu w pytaniu (liczby to odwiedzone miasta):

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
źródło

Jedną drobną rzeczą do dodania - być może będziesz musiał rozważyć zapętlenie krawędzi kosztem 1, ponieważ same te krawędzie stanowią warunek wygranej, jeśli możesz je osiągnąć na czas.

Rainbolt

The Final Stand - Pokonaj Hordę Zombie

Odpowiedzi:

Java ( mniej groteskowa: 8415 5291 3301)

Edytować

Fajny faktoid

Najważniejsze informacje o rozwiązaniu

Historia solvera

Kod (golfowy)

Przykład wyjściowy

Notatki końcowe

Kilka abstrakcyjnych notatek na temat rozwiązania