Potrzebuję pomocy w związku z tym problemem ICPC ACM. Mój obecny pomysł polega na zamodelowaniu tego jako problemu najkrótszej ścieżki, który jest opisany w opisie problemu.
Problem
Istnieją N = 1000
pojemniki na odpady nuklearne umieszczone wzdłuż linii liczbowej 1-D w różnych pozycjach od -500,000 to 500,000
, z wyjątkiem x=0
. Osoba ma za zadanie zebrać wszystkie kosze na śmieci. Co sekundę, gdy pojemnik na śmieci nie jest zbierany, emituje 1 jednostkę promieniowania. Osoba zaczyna od x = 0
i może przemieszczać 1
jednostkę co sekundę, a zbieranie odpadów zajmuje niewiele czasu. Chcemy znaleźć minimalną ilość promieniowania uwalnianego podczas zbierania wszystkich pojemników.
Przykładowe dane wejściowe:
4
Kontenery znajdujące się przy ul [-12, -2, 3, 7]
.
Najlepszym sposobem na odbiór tych pojemników jest [-2, 3, 7, -12]
minimalna emisja 50
jednostek. Wyjaśnienie: osoba idzie do -2
w ciągu 2 sekund i w tym czasie 2 units
promieniowania są emitowane. Następnie idzie do 3
(odległość 5
:), aby lufa uwolniła 2 + 5 = 7
jednostki promieniowania. Potrzebuje 4
więcej sekund, aby dotrzeć do x = 7
miejsca, w którym ta beczka wyemitowała 2 + 5 + 4 = 11
jednostki. Zajmuje 19
sekundy, aby dotrzeć do x = -12
miejsca, w którym ta beczka emitowała 2 + 5 + 4 + 19 = 30
jednostki. 2 + 7 + 11 + 30 = 50
, która jest odpowiedzią.
Uwagi
Istnieje oczywiste O(N!)
rozwiązanie. Jednak badałem chciwe metody, takie jak przejście do najbliższej lub przejście do najbliższej gromady, ale te nie zadziałały.
Długo zastanawiałem się nad tym problemem i zamodelowałem go jako problem z wyszukiwaniem wykresów:
- Wstawiamy
0
jako pozycję wyjściową (będzie to stan początkowy) - Następnie sortujemy pozycje od najmniejszej do największej.
- Następnie wykonujemy BFS / PFS, na który
state
składa się- Dwie liczby całkowite
l
ir
które stanowią ciągły zakres w posortowanej tablicy pozycji, które już odwiedził - Liczba całkowita,
loc
która mówi nam, czy jesteśmy na lewym, czy na prawym punkcie końcowym zakresu - Liczba całkowita,
time
która pokazuje nam upływ czasu - Całkowity „koszt”, który mówi nam całkowity koszt do tej pory (na podstawie odwiedzonych węzłów)
- Dwie liczby całkowite
- Z każdego stanu możemy przejść do [l - 1, r] i [l, r + 1], odpowiednio modyfikując pozostałe 3 liczby całkowite
- Stan końcowy to [0, N], sprawdzanie obu pozycji końcowych.
Wydaje się jednak, że [L, R, loc]
nie definiuje ono jednoznacznie stanu i musimy przechowywać L, R, loc, and time
, minimalizując cost
przy każdym z nich. Prowadzi to do algorytmu wykładniczego, który jest wciąż zbyt wolny dla jakiegokolwiek dobra.
Czy ktoś może mi pomóc rozwinąć pomysł lub popchnąć go we właściwym kierunku?
Edycja: Może to może być modelowane jako problem z optymalizacją programowania dynamicznego? Myśląc o tym, ma te same problemy, co rozwiązanie do wyszukiwania wykresów - tylko dlatego, że prąd cost
jest niski, nie oznacza, że jest to optymalna odpowiedź na ten problem podrzędny, ponieważ time
również ma duży wpływ na odpowiedź.
Chciwość nie działa: mam chciwy algorytm selekcji, który szacuje koszt przeniesienia do określonego miejsca (np. Jeśli ruszymy w prawo, podwajamy odległości do lewej beczki i tak dalej).
Czy możesz przeprowadzić wyszukiwanie z priorytetem za pomocą heurystyki? Heurystyka mogłaby połączyć koszt bieżącej podróży z upływem czasu.
źródło
Odpowiedzi:
Myślę, że można to poprawić, patrząc na problem jako ukierunkowany wykres par pozycji.
W tym przykładzie użyję linii o wartościach -9, -6, -1, 3 i 5.
Ponieważ zbyt trudno jest narysować wykres za pomocą samego tekstu, zamierzam przedstawić pary jako tabelę. Możemy myśleć o komórkach jako o stanie, w którym zebrano wszystkie pojemniki między tymi dwiema pozycjami. Każda komórka ma dwie wartości, jedną reprezentującą koszt przejścia w lewo, drugą reprezentującą koszt przejścia w prawo (do następnego kontenera).
Wartości można po prostu obliczyć jako odległość między dwoma punktami pomnożoną przez liczbę beczek poza tymi dwoma punktami + 1 . Komórki, w których obie liczby mają ten sam znak, reprezentują przypadki, w których zebrano wszystkie beczki przeciwnego znaku. Są one obliczane przy użyciu tylko liczby beczek w kierunku od zera.
W tabeli wartości X oznaczają, że nie możesz iść w tym kierunku (wszystkie lufy w tym kierunku zostały zabrane). Rzędy reprezentują aktualną pozycję kolektora, a kolumny przedstawiają położenie następnej przeciwległej lufy.
Zasady poruszania się między kwadratami mogą być nieco mylące.
W przypadku kolumn z liczbami ujemnymi reguły są następujące:
W przypadku kolumn z dodatnimi numerami reguły są następujące:
Teraz możemy uruchomić algorytm Dijkstry, aby obliczyć najlepszą ścieżkę, używając tych reguł ruchu do przechodzenia przez wykres. Nasze pozycje początkowe to (-1, 3) i (3, -1) z początkowymi kosztami odpowiednio 5 i 15. Po obliczeniu wartości dla dwóch pozycji końcowych (na lewo od (-9, -9) i na prawo od (5, 5)) mniejsza z tych dwóch jest naszą odpowiedzią.
Czas wykonywania każdego z kroków to:
Pierwsze dwa kroki są zdominowane przez ostatnie, więc całkowity czas działania to O (N ^ 2 log N), co powinno być wystarczającym czasem wykonania dla wyzwania.
źródło
Najkrótsza odległość
Wczoraj napisałem aplikację Java, aby rozwiązać problem. Problem jest w zasadzie problemem najkrótszej odległości, jak powiedział SRJ w swoim komentarzu. Promieniowanie pokazuje po prostu, że można zgromadzić wartość wraz z najkrótszą odległością.
Zasadniczo oto co zrobiłem.
Oto niektóre dane wyjściowe z aplikacji
W żaden sposób nie zoptymalizowałem algorytmu. Nawet nie zauważyłem, że lista liczb wejściowych jest posortowana. (Jestem doofusem.)
Kiedy uruchomiłem mój kod z maksymalnymi wartościami, 1000 kontenerów i zakresem od -500 000 do 500 000, wykonanie kodu zajęło mi 3 sekundy. Przez większość czasu zapisywałem w konsoli 1000 wierszy wydruku.
Nie jestem wielką osobą O, ale myślę, że moją brutalną siłą chodzenia algorytmem najkrótszej ścieżki jest O (N do kwadratu), a nie O (N!).
Gdybym skorzystał z faktu, że liczby wejściowe są posortowane, tak że musiałem tylko sprawdzić dwie liczby po obu stronach miejsca, w którym się obecnie znajduję, mógłbym umieścić aplikację w pobliżu O (N). Muszę tylko sprawdzić 2 liczby, ponieważ usuwam elementy z Listy, gdy do nich docieram.
Użyłeś różnych algorytmów, takich jak algorytm zachłanny, aby znaleźć przybliżone rozwiązanie.
Gdyby uruchomienie mojego programu zajęło 3 godziny zamiast 3 sekund, będziesz musiał dokonać wyboru.
Czy wystarczająco dobre rozwiązanie jest wystarczająco dobre?
Innymi słowy, czy chcę wymienić szybkość przetwarzania na wystarczająco dobrą odpowiedź?
Jeśli wystarczająco dobra odpowiedź jest wystarczająco dobra, wówczas używasz algorytmów aproksymacyjnych.
Jeśli chcesz uzyskać idealną odpowiedź, musisz przejść wszystkie najkrótsze ścieżki. Nie ma skrótu.
Jeśli ktoś chce, żebym opublikował mój kod, zrobię to. Jestem pewien, że nadal występują błędy, ponieważ chciałem sprawdzić, czy mogę zaimplementować algorytm najkrótszego spaceru.
źródło
Mam rozwiązanie, które rozwiąże ten problem na
2^N
czas, co jest kiepskie, ale myślę, że jest to pomocny sposób na sformułowanie problemu, więc pomyślałem, że opublikuję.Zamiast modelować problem jako wykres, modelowałbym to binarne drzewo decyzyjne (powiedzmy
T
). Na każdym poziomie musisz wybierać między przejściem w prawo lub w lewo. Obliczenie „kosztu” każdej krawędzi jest dość łatwe. Niechh(K)
będzie wysokość bieżącego węzłaK
, a następnie koszt przejścia na krawędźleft_child(K) = h(K) x dist(K, left_child(K))
. Podobne obliczenia wystarczają na pokrycie krawędzi odpowiedniego dziecka. Konstruujesz to drzewo i śledzisz skumulowany koszt krawędzi do końca, i raportujesz ścieżkę do węzła liścia przy najmniejszym koszcie całkowitym.Należy pamiętać, że obliczanie kosztów działa, ponieważ długość każdej krawędzi
dist(K, left_child(K))
reprezentuje czas przejścia do następnego miejsca, a wysokość poddrzewa jest liczbą pozostałych miejsc (np. Wciąż emitujących promieniowanie).Teraz podstępem w tych ramach jest ustalenie, czy istnieją jakieś heurystyki, których można użyć do „udowodnienia”, że można zignorować rozszerzanie wyszukiwania wzdłuż jakiejś gałęzi. Moją intuicją jest to, że dla każdej takiej heurystyki istnieje układ witryn, który ją pokona, ale być może ktoś coś wymyśli.
Wielu zaproponowało zastosowanie najkrótszych ścieżek dla grafów, mam pewne wątpliwości, czy takie rozwiązanie może zadziałać. Twoi sąsiedzi na „wykresie” problemu zmienią się w zależności od ścieżki, którą podążasz. Na przykład w swoim pierwotnym stanowisku ze
[-12, -2, 3, 7]
jeśli pójdziesz do-2
wtedy-12
i3
stają się „sąsiedzi” i jeśli pójdziesz do3
wtedy-2
i7
są sąsiadami. Każda możliwa „para” wartości dodatnich i ujemnych może potencjalnie być sąsiadami na końcowym wykresie. Nie znam żadnych algorytmów najkrótszej ścieżki, które są poprawne na wykresie dynamicznym.źródło
Myślę, że najbardziej sensowne jest myślenie o każdym etapie po prostu jako binarny wybór między przejściem w prawo do najbliższej beczki a przejściem w lewo do najbliższej beczki. Wystarczy mieć funkcję kosztów, która wyszczególnia liczbę jednostek promieniowania, które zostałyby poniesione w całości przez wykonanie dowolnego ruchu i wybierz tę o najniższym koszcie.
NIE bierz po prostu pod uwagę najbliższej beczki, ale zamiast tego załóż, że oddalając się od beczki, skutecznie dodajesz dwa razy więcej promieniowania, ponieważ odsuwając się, poniosłeś również koszt powrotu w tym kierunku później.
W twoim przykładzie [-12, -2,3,7] przesunięcie w lewo spowodowałoby łącznie 14 (2 + 2 + 10) po lewej stronie i 18 (2 + 2 + 5 + 9) po prawej stronie, w sumie 22. Przesunięcie w prawo spowoduje 10 (3 + 3 + 4) po prawej stronie i 26 (3 + 3 + 5 + 15) po prawej stronie. Na początku wyraźnie lewe jest właściwe rozwiązanie. Podobne obliczenia można wykonać dla każdego kolejnego ruchu.
Po tym problem zasadniczo sprowadza się do wyszukiwania, więc złożoność powinna wynosić O (nlog (n)), która jest DUŻO lepsza niż O (n!). Uważam, że jest to koniecznie najniższa złożoność, jaka może istnieć dla tego problemu, ponieważ jest to w zasadzie algorytm wyszukiwania oparty na porównaniu, dla którego nie można zrobić lepiej niż O (nlog (n))
Najwyraźniej ten opis nie był wystarczająco jasny, więc postanowiłem uczynić go nieco bardziej zautomatyzowanym: 1. Oblicz koszty poniesione przez przejście w lewo i koszty poniesione przez przejście w prawo na podstawie bieżącej pozycji 2. Wejdź najtańszy kierunek 3. Odejmij do rozważenia osiągniętą lufę przy obliczaniu kosztu ruchu w danym kierunku
Obliczanie kosztów: 1. Zidentyfikuj najbliższą beczkę w danym kierunku. Powiedzmy, że $ dist to odległość od bieżącej pozycji do najbliższej lufy w danym kierunku. 2. Koszt jest inicjowany jako N * $ dist, gdzie N bierze pod uwagę tylko wciąż aktywne beczki. 3. Do tego dodaj odległość, jaką nowa pozycja oznaczona $ dist będzie od każdej pozostałej beczki.
źródło
[43, -18, -98, -82, 63]
[-10,-11, 10,20,30,40,50,60,70]
. Prawidłowym i jedynym rozwiązaniem jest zebranie wszystkich negatywnych, a następnie zebranie pozytywnych. Po odpowiedź 455.Częściowe rozwiązanie - wrócę do niego później.
Załóżmy, że strategia „domyślna” jest uruchamiana do końca w lewo lub w prawo, w zależności od tego, która opcja jest tańsza. Teraz zapytaj, czy warto wybrać się na małą wycieczkę w drugą stronę, aby podnieść jedną beczkę. Obliczenie odpowiedzi jest dość łatwe.
Dla przykładowego wprowadzania, bieg do końca w prawo jest tańszy niż do końca w lewo. Czy wybranie opcji -2 jest warte wycieczki? Zmniejsza to koszt prawidłowego działania, a następnie powrotu do 0 o 14 (ponieważ „płaciłeś” 4 jednostki promieniowania na ruch z 0 do 3 przy domyślnej strategii, teraz spada do 3, płacisz 3 z 3 do 7, teraz jest to 2 itd.), plus zmniejsza o jeden ruch za ruch z 0 do -2, oszczędzając w ten sposób 2 więcej za 16.
Dodaje jednak koszt przejścia do -2, a następnie z powrotem do 0 z 14 (4 jednostki na ruch do -2, 3 za ruch z powrotem do 0), dla zysku netto (16-14) = 2. Pamiętaj, że aby to obliczyć, nie musisz oceniać dokładnego kosztu rozwiązania całego problemu dla każdej decyzji - masz wystarczającą ilość informacji, aby zdecydować, wiedząc, czy bieg do końca w lewo jest tańszy niż bieg do końca w prawo, a także jak wiele pojemników na odpady znajduje się po każdej stronie ciebie, a odległość do najbliższego 2. Więc to jest O (N ^ 2).
Z wyjątkiem jednego ważnego problemu - zakładam, że pobiegniesz do końca i wiemy, że możesz się wycofać. Aby to oczyścić, musimy zaktualizować moje obliczenia. W przypadku próbki wejściowej założyłem, że zaoszczędzisz 14, emitując o 1 mniej promieniowania całkowitego na jednostkę na sekundę podczas pracy od 0 do 7 iz powrotem. Ale jeśli podwoisz liczbę punktów przed biegiem do 7, oszczędności zostaną zmniejszone.
To całkiem źle, ponieważ nie wiem, jak obliczyć następne podwójne odwrócenie bez wypróbowania wszystkich możliwości, co powoduje powrót do O (2 ^ N).
Z wyjątkiem - to 2 ^ N z przycinaniem. Obliczyłem, że „podróż boczna” do -2 kosztuje 14, ale zyskałem 16, jeśli nie miałem więcej podróży bocznych, zanim dotarłem do skrajnej prawej liczby. Gdyby liczba po prawej stronie wynosiła 5, od razu wiedziałbym, że poboczna wycieczka do -2 nie mogłaby się opłacić. (Koszt nadal 14, maksymalna korzyść 12). Nie muszę też rozważać przejścia do -2, a następnie odbycia podróży bocznej przed osiągnięciem 6, ponieważ zawsze jest to gorsze niż po prostu przejście prosto do tego punktu w pierwszej kolejności.
źródło
Myślę, że możesz to rozwiązać za pomocą wyszukiwania na szerokość, zachowując nie więcej niż 2 * N ^ 2 krotek (boolean, int, int, int, string), gdzie łańcuchy są tak długie, jak długo ścieżka jest skomplikowana.
Krotki to (min. Lub maks. Wartość logiczna, min. Przebyta pozycja, maks. Przebyta pozycja, całkowite wyemitowane promieniowanie, historia ścieżki).
Widzę następujący algorytm:
Znajdowanie i usuwanie dominujących krotek znacznie poprawi wydajność. Warto dodać flagę „wyhodował” do każdej krotki i pozostawić krotki w puli.
Istnieją również ważne decyzje, które należy podjąć przy podejmowaniu decyzji o przechowywaniu krotek i poszukiwaniu ich dominacji i nowych elementów do rozmnażania.
źródło