Odwiedzanie punktów na linii liczbowej przy minimalizacji kosztów niezwiązanych z odległością

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 = 1000pojemniki 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 = 0i może przemieszczać 1jednostkę 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:

4Kontenery znajdujące się przy ul [-12, -2, 3, 7].

Najlepszym sposobem na odbiór tych pojemników jest [-2, 3, 7, -12]minimalna emisja 50jednostek. Wyjaśnienie: osoba idzie do -2w ciągu 2 sekund i w tym czasie 2 unitspromieniowania są emitowane. Następnie idzie do 3(odległość 5:), aby lufa uwolniła 2 + 5 = 7jednostki promieniowania. Potrzebuje 4więcej sekund, aby dotrzeć do x = 7miejsca, w którym ta beczka wyemitowała 2 + 5 + 4 = 11jednostki. Zajmuje 19sekundy, aby dotrzeć do x = -12miejsca, w którym ta beczka emitowała 2 + 5 + 4 + 19 = 30jednostki. 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:

1. Wstawiamy 0jako pozycję wyjściową (będzie to stan początkowy)
2. Następnie sortujemy pozycje od najmniejszej do największej.
3. Następnie wykonujemy BFS / PFS, na który stateskłada się
   • Dwie liczby całkowite li rktóre stanowią ciągły zakres w posortowanej tablicy pozycji, które już odwiedził
   • Liczba całkowita, locktóra mówi nam, czy jesteśmy na lewym, czy na prawym punkcie końcowym zakresu
   • Liczba całkowita, timektó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)
4. Z każdego stanu możemy przejść do [l - 1, r] i [l, r + 1], odpowiednio modyfikując pozostałe 3 liczby całkowite
5. 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 costprzy 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 costjest niski, nie oznacza, że ​​jest to optymalna odpowiedź na ten problem podrzędny, ponieważ timeró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.

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.

    +------+------+------+------+------+
    |  -9  |  -6  |  -1  |   3  |   5  |
+---+------+------+------+------+------+
|-9 |      |      |      | X, 24| X, 14|
+---+------+------+------+------+------+
|-6 | 3, X |      |      | 9, 27| 6, 22|
+---+------+------+------+------+------+
|-1 |      |10, X |      |20, 8 |15, 18|
+---+------+------+------+------+------+
| 3 |24, 4 |27, 6 |16, 8 |      | X, 2 |
+---+------+------+------+------+------+
| 5 |14, X |22, X |18, X |      |      |
+---+------+------+------+------+------+

Zasady poruszania się między kwadratami mogą być nieco mylące.

W przypadku kolumn z liczbami ujemnymi reguły są następujące:

• Idąc w prawo przesuwa się o jedną komórkę w dół.
• Przechodzenie w lewo przesuwa się w dół o jedną komórkę, a następnie odzwierciedla lustro po przekątnej.
• Jeśli prawą wartością jest X, przejście w lewo przesuwa się w górę do przekątnej (gdzie kolumna i rząd są równe) i w lewo o jeden.

W przypadku kolumn z dodatnimi numerami reguły są następujące:

• W lewo przesuwa się w górę o jedną komórkę.
• Idąc w prawo przesuwa się w górę o jedną komórkę, a następnie odzwierciedla lustro po przekątnej.
• Jeśli lewą wartością jest X, przejście w prawo przesuwa się w dół do przekątnej i w prawo o jeden.

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:

• O (N log N) do początkowego sortowania wartości wejściowych wzdłuż linii
• O (N ^ 2) do obliczenia tabeli / wykresu
• O (N ^ 2 log N) do uruchamiania Dijkstry na wykresie (Uwaga: dla każdego wierzchołka istnieją najwyżej dwie krawędzie).

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.

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.

• Umieść numery kontenerów na Liście <Liczba całkowita>
• Podczas gdy lista zawiera elementy;
  • Znajdź najbliższe elementy
  • Jeśli jest jeden element, przejdź tam i usuń element.
  • Jeśli są dwa elementy, skopiuj ścieżkę i przejdź do obu elementów
• Znajdź ścieżkę o najmniejszej wartości promieniowania.

Oto niektóre dane wyjściowe z aplikacji

10 containers are located at [-90, -75, -47, -9, 9, 26, 48, 50, 64, 79].

You walk to position -9 and pick up the container.  The total radiation emitted is 90 units.
You walk to position 9 and pick up the container.  The total radiation emitted is 252 units.
You walk to position 26 and pick up the container.  The total radiation emitted is 388 units.
You walk to position 48 and pick up the container.  The total radiation emitted is 542 units.
You walk to position 50 and pick up the container.  The total radiation emitted is 554 units.
You walk to position 64 and pick up the container.  The total radiation emitted is 624 units.
You walk to position 79 and pick up the container.  The total radiation emitted is 684 units.
You walk to position -47 and pick up the container.  The total radiation emitted is 1,062 units.
You walk to position -75 and pick up the container.  The total radiation emitted is 1,118 units.
You walk to position -90 and pick up the container.  The total radiation emitted is 1,133 units.

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.

Mam rozwiązanie, które rozwiąże ten problem na 2^Nczas, 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. Niech h(K)będzie wysokość bieżącego węzła K, 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 -2wtedy -12i 3stają się „sąsiedzi” i jeśli pójdziesz do 3wtedy -2i 7są 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.

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.

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.

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:

1. Zainicjuj pulę krotek do pojedynczego wpisu (min, 0, 0, 0, „”)
2. Znajdź element w basenie, który emituje minimalne promieniowanie. Jeśli min. I maks. Odpowiadają min i maks. Wszystkich beczek, historia ścieżki jest optymalnym rozwiązaniem. W przeciwnym razie usuń go z puli.
3. Oblicz 2 potomków tej krotki, z których każdy odpowiada chodzeniu w lewo lub w prawo do następnej nieprzetworzonej beczki.
4. Wstaw potomków do puli. Jeśli w puli znajduje się już element o tej samej wartości logicznej, min i max jako nowy potomek, należy odrzucić element o wyższej liczbie promieniowania.
5. Goto 2.

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.