Pomoc w programowaniu, odpowiedzi na pytania / Algorytm / Jak mogę ulepszyć ten algorytm do rozwiązania zmodyfikowanej łamigłówki znaczków pocztowych? - algorytm, optymalizacja, azspcs

Jak mogę ulepszyć ten algorytm do rozwiązania zmodyfikowanej łamigłówki pocztowej? - algorytm, optymalizacja, azspcs

Problem Son of Darts był konkurs na Konkursy programistyczne Al Zimmermanna który zakończył się 20 czerwca 2010:

Załóżmy, że masz tarczę podzielonąw regionach R. Każdy region tarczy ma dodatnią wartość całkowitą. Ponadto załóżmy, że masz rzutki D i że rzucasz każdą z nich w tarczę. Każda strzałka ląduje w jednym z regionów R planszy lub całkowicie tęskni za tablicą. Twój wynik jest sumą wartości dla regionów, w których lądują strzałki. rzutki lądują w tym samym regionie, wielokrotnie gromadzisz wartość tego regionu.

Załóżmy na przykład, że R = 5, żeRegiony tarczy mają wartości (1, 2, 4, 7, 11), a D = 3. Jeśli trzy rzutki lądują w regionach 2, 4 i 11, otrzymujesz 17 punktów. Jeśli jedna strzałka nie trafi w planszę, a dwie pozostałe w rejon 7, otrzymasz 14 punktów.
Problem z rzutkami jest następujący: dla danego R i D określ, jakie wartości powinny być powiązane z regionami R tarczy, aby zmaksymalizować najmniejszy wynik nieosiągalny przez rzucanie rzutkami D.
D = number of darts    R = number of dartboard regions
3                      1 through 40
4                      1 through 30
5                      1 through 20
6                      1 through 10

================================================== ================================

UŻYWANE PODSTAWOWE ALGORYTMY (wyjaśnione dla D = 3)

Zaczynam od wynik tablica pokazana poniżej. 0 i 1 są partyturami, które powinny znajdować się na obszarach tarczy. 0 wskazuje, że strzałka nie trafiła w planszę. Tak więc wygeneruję tę tablicę dla 41 elementów (jedna dodatkowa do skompensowania 0). 1 jest obowiązkowe, ponieważ w przeciwnym razie nie ma innego sposobu na wygenerowanie 1.
```
 ____ ____
|    |    |
|  0 |  1 |
|____|____|
```

Generuję zadraśnięcie tablica, która pokazuje, co można uzyskać za pomocą wszystkich rzutek w tablicy wyników, w trzech rzutach. Podkreślone elementy to te, które zostały użyte do wygenerowania zadraśnięcie.

0 = 0 + 0 + 0
1 = 1 + 0 + 0
2 = 1 + 1 + 0
3 = 1 + 1 + 1
____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| *  | *  | *  | *  |    |    |    |    |    |    |    |    |    |
|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
|__-_|__-_|____|____|____|____|____|____|____|____|____|____|____|

Teraz kandydaci na następny element tablicy wyników są 2, 3 lub 4.
- 2 = element pierwszy większy niż obecny największy element
- 4 = niewielki nieosiągalny element

Próbuję każdego z tych kandydatów z kolei i widzę, że jest to maksymalny najmniejszy nieosiągalny element w każdym przypadku. Na przykład

(0, 1, 2)

 ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| *  | *  | *  | *  | *  | *  | *  |    |    |    |    |    |    |
|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
|__-_|__-_|__-_|____|____|____|____|____|____|____|____|____|____|

(0, 1, 3)

 ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| *  | *  | *  | *  | *  | *  | *  | *  |    | *  |    |    |    |
|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
|__-_|__-_|____|__-_|____|____|____|____|____|____|____|____|____|

(0, 1, 4)

 ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| *  | *  | *  | *  | *  | *  | *  |    | *  | *  |    |    | *  |
|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
|__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|

max (7, 8, 7) = 8. Więc, 3 jest wybrany jako następny element.
Jeśli przypuśćmy, że był remis, na przykład, gdybym musiał wybrać pomiędzy (0, 1, 2) i (0, 1, 4), aby przerwać remis, policzyłbym liczbę możliwych do osiągnięcia liczb, co jest większe w przypadku (0, 1, 4). Więc wybrałbym (0, 1, 4) ponad (0, 1, 2).
Ale w tym przypadku (0, 1, 3) jest zwycięzcą, a zestaw wyników wygląda jak poniżej. Następnie powtarzam kroki, aż otrzymam 41 elementów.
```
 ____ ____ ____
|    |    |    |
|  0 |  1 |  3 |
|____|____|____|
```
Algorytm jest chciwy w tym sensie, że jestzakłada, że (rozwiązanie dla R = 20) jest podzbiorem (rozwiązanie dla R = 30). Tak więc nie obliczam wyników dla każdej wartości R, ale obliczam wyniki dla każdej wartości D. Więc dla D = 3, obliczam wynik dla R = 40, a następnie biorę pierwsze 30 elementów wyniku dla R = 30, na przykład.
Algorytm jest chciwy w tym sensie, że zakłada, że cel na każdym kroku (w tworzeniu wynik tablica) jest osiągnięcie minimalnej nieosiągalnej sumy na etapie.
Aby móc działać lepiej niż brutalna siła, algorytm eliminuje niektórych kandydatów do tablicy wyników. Na przykład w przypadku przedstawionym na poniższym schemacie (dla (0, 1, 4) wynik array), rozważam tylko 5, 6 i 7 jako kandydatówdla następnego elementu i wyklucz 2 i 3, chociaż nadal nie są używane. To założenie może dać mi nieoptymalne wyniki w niektórych przypadkach, ale zmniejsza wiele obliczeń, kiedy zadraśnięcie rośnie do tysięcy elementów.
```
 ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
| *  | *  | *  | *  | *  | *  | *  |    | *  | *  |    |    | *  |
|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
|__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|
```

ULEPSZENIA ALGORYTMU

Ponieważ nie dawało to zbyt dobrych wyników, próbowałem generować zestawy wyników dla każdej wartości D. Na przykład zamiast wybierać najlepszy następny element dla wynik, Mógłbym także wybrać drugi najlepszy lubtrzeci najlepszy element. Tak więc, aby przejść 39 kroków (do 41 elementów w rezultacie), mógłbym wygenerować około 3 ^ 39 (dla każdego wyboru mogę mieć najlepszy lub drugi najlepszy lub trzeci najlepszy element) przypadki, które są zbyt liczne. Postanowiłem więc pójść z najszczęśliwszym sekundowym najlepszym i zdecydowanie najlepszym wyborem. Zmniejszyło to liczbę przypadków dookoła ⁴⁰do₁ * ³⁹do₁ = 577980 wyników. Więcej niż to doprowadziłoby do OGROMNEJ liczby przypadków dla wyższych wartości R (dla wyższych wartości D).
Z tych ~ 6E5 wyników, które posiadam, obliczam minimalny nieosiągalny element dla każdej wartości R od 1 do 40. Zatem każda z wartości R wybiera najlepszy z tych wartości 6E5.

PROBLEMY

Ten algorytm nie daje najlepszych wyników wynik zestawy, a nawet blisko.
Doszedłem nawet do czwartego i piątego najlepszego wyboru dla D = 3 i nie dali żadnych znaczących ulepszeń w wynikach. Więc nie wiedziałem, gdzie powinienem dostroić mój algorytm.

Gdzie mogę dostroić ten algorytm, aby uzyskać lepsze wyniki?

Czy są jakieś oczywiste błędy, które powoduje algorytm?

Wszelkie komentarze / sugestie są mile widziane.

_{Było jeszcze jedno pytanie na ten sam temat tutaj. Jestem bardziej zainteresowany wiedzą, gdzie można poprawić mój algorytm.}

Odpowiedzi:

3 dla odpowiedzi № 1

Brałem udział w tym konkursie, podobnie jak tyZauważ, że zająłem 100. miejsce z 87,00 zebranych punktów. Właściwie użyłem twojej metody, ponieważ zdałem sobie sprawę, że wygenerowanie „rozsądnego” rozwiązania dla każdego problemu było pierwszą przeszkodą do pokonania. W momencie, gdy go prowadziłem, uzyskane punkty były wystarczające, aby zwiększyć mnie o 94 punkty, ale ponieważ najlepsi zarabiali, poprawili swoje wyniki, liczba ta szybko spadła do około 75.

Pierwszą i najłatwiejszą rzeczą, jaką możesz zrobić, jestzdaj sobie sprawę, że twój program działa w jednej chwili, a jeśli nie, nie należy tracić czasu na optymalizację tego bzdury. D = 3, R <= 5 w krótkim czasie. Następnie możesz użyć zestawów w R = 5 jako nasiona twojego zachłannego algorytmu. Teraz zamiast jednego zachłannego rozwiązania masz kilka tysięcy, a po prostu musisz śledzić najwyższą wartość generowaną na każdym poziomie R i wartości, które go tworzą. To jest łatwe do zrobienia, a otrzymasz wynik powyżej 80.

Spędziłem prawie miesiąc optymalizując funkcję, która może przetestować dowolny losowy zestaw wejściowy, dzięki czemu mogłem przepompować mój generator nasion R = 10 i uruchom go w ciągu około 8 godzin na jednym rdzeniu. Gwarantowało to najlepsze możliwe rozwiązanie dla „D = 3”, „R <= 10” i znacznie lepsze odpowiedzi, gdy R > 10 niż w oryginalnym chciwym wyniku. To spowodowało, że mój wynik był bardzo zbliżony do tego, gdzie zakończył się po uruchomieniu R jak najwyżej dla każdego D nadal będąc w stanie uruchomić program w ciągu jednego dnia. Udało mi się dotrzeć R = 9 dla D = 4, R = 8 dla D = 5, i R = 8 dla D = 6.

Po uruchomieniu obliczyłem, że nie będę w stanie zwiększyć R o 1 dla każdego D nad liczbami właśnie wymienionymi i uzupełnij jejego wykonanie za mojego życia. Oczywiście nadszedł czas, aby poszukać nowej techniki. Doszedłem do wniosku, że wykonuję świetną robotę na froncie, testując każdy możliwy segment początkowy, więc dlaczego nie przesunąć części tego do końca, testując głębsze zestawy wyników dla każdego z moich początkowych segmentów. Zamiast chwycić najlepszy następny wynik na tym samym poziomie, wykonałem 2 poziom patrzenia przed siebie i wybrałem najlepszą następną wartość z dwóch poziomów. Na przykład zawsze zaczynasz od 1, a następnie wyliczasz wszystkie wartości dla R = 2 (2, 3, 4) a następnie dla każdego z nich oceń wszystkie możliwe wartości dla R = 3. Więc 2 (3, 4, 5, 6, 7), 3 (4, 5, 6, 7, 8), 4 (5, 6, 7). Weź najwyższą ze wszystkich ocen, a następnie wybierz wartość w R = 2 który zawiera najwyższą wartość dla R = 3. Wymagało to znacznie więcej czasu przetwarzania i wymagało ode mnie obniżenia max R Mógłbym go użyć, ale przyniosło to lepsze wyniki dla głębszych poszukiwań.

W tym momencie zrezygnowałem z chciwych podejść iwykorzystałem tę konkurencję do poszerzenia mojej wiedzy o sztucznej inteligencji. Próbowałem użyć różnych technik monte carlo, a także podstawowego algorytmu genetycznego. Dowiedziałem się wiele o monte carlo i poszukuje najlepszych wykonawców w tym konkursie, znalazłem publikacje na temat optymalizacji kryteriów selekcji monte carlo, które były poza moim zrozumieniem. Chciałbym pomóc ci dalej, ale czuję się przekonany, że złamanie 90 punktów przy zachłannym podejściu jest bardzo mało prawdopodobne w moim życiu. Byłbym zainteresowany, aby zobaczyć, o ile lepiej uzyskałyby odpowiedzi, gdyby były wielowątkowe i rzucono na nie garść mocy.

Nie mam żadnej pracy, którą dla mnie zrobiłemproblem ze mną, ale pamiętam, że pokazałem, że spojrzenie w przyszłość i większe wyliczenie początkowych nasion były jedynymi możliwymi ulepszeniami algorytmu zachłannego dla tego problemu. Będę za to dziś wieczorem i zamieścił tutaj proces myślenia, jeśli znajdę notatki.

EDIT: kod pierwotnie opublikowany na serwerze, który został porzucony. Proszę o wiadomość, jeśli chcesz, aby została opublikowana ponownie.

1 dla odpowiedzi nr 2

Dziękujemy za bardzo interesujące pytanie! Spędziłem kilka minut na zrozumieniu pytania.

Nie widziałem formalnego sformułowania problemu, więc pozwólcie mi rzucić okiem na wymyślenie tutaj zapisu.

Po pierwsze, obserwacja (jak również poprawnie zrobiłeś), jeden z regionów musi być 1, w przeciwnym razie 1 nie byłby osiągalny.

Po drugie, ponieważ staramy się zmaksymalizować nieosiągalny wynik, nie ma sensu w powtarzających się wartościach regionu.

To daje zdegenerowane (ale nie optymalne) rozwiązanie: 1, 2, 3, ... R

The wartość funkcji celu tego zdegenerowanego rozwiązania jest: D * R + 1

Na przykład, jeśli masz D = 4 rzutki i pokolorujesz swoją tarczę o wyniki 1, 2. ..40, to każdy wynik z wartości od 1 do 160 jest osiągalny. 161 nie jest osiągalny.

Jest oczywiste, że to rozwiązanie nie jest optymalne, a optymalne rozwiązanie wiąże się prawdopodobnie z pewnymi mocami 2 i zdecydowanie pewną myślą.

Teraz notacja:

Niech f (X, D, {Y_1..Y_R}) =

1, jeśli wynik X jest osiągalny za pomocą rzutek D na tarczy z zakresy Y_1 ... Y_R
0 jeśli nieosiągalne

Jako przykład omówiony wcześniej. f (160,4, {1..40}) = 1 i f (161,4, {1,.40}) = 0

Wartość funkcji celu układanki można następnie oznaczyć jako:

g (D, (Y_1..Y_R}) = Min X | f (X, D, {Y_1..Y_R}) = 0

Obserwacją 1 wcześniej możemy założyć, że Y_1 = 1.

Również rekurencyjne sformułowanie funkcji f może być następujące.

f (X, D, {1..Y_R} = 1 jeśli:

X = 0 lub
f (X-Y_j, D-1, {1..Y_R}) = 1 dla niektórych j

[Będzie dalej pracować nad tym i publikować więcej, gdy go rozwijam.]

1 dla odpowiedzi nr 3

Maksymalny najmniejszy nieosiągalny element todobrze szukać tylko w ostatniej iteracji. Lepsza podstawowa subgala to liczba możliwych do osiągnięcia elementów z określoną liczbą rzutek. Jednym z interesujących subgłówek może być

Nae * (Rt - Rc) / Rt + Msue, where

Nae - liczba możliwych do osiągnięcia elementów (z określoną liczbą rzutek)
Rt - całkowite dostępne regiony
Rc - aktualnie używane regiony (obecny poziom rekurencji)
Problem - maksimum najmniejszego nieosiągalnego elementu

Dlaczego Nae jest bardziej wartościowy niż na początku?iteracje? Im więcej elementów będzie osiągalnych na początku, tym więcej elementów będzie dla mnie bardziej użytecznych i da więcej kombinacji, a nawet osiągnie jeszcze więcej osiągalnych elementów. Wraz z eksplozją Nae pojawia się wysokie prawdopodobieństwo, że problem wzrośnie również do dobrego poziomu. Jednak w późnych iteracjach problem staje się coraz ważniejszy, a nowe elementy są bardziej wykorzystywane do „zatkania dziur”, z nadzieją, że ostatni otwór do zatkania będzie najdalej możliwy.

Fizyczna analogia tego uzasadnienia byłabyolimpijskie długie skoki, w których zawodnik na początku biegu najpierw nabiera rozpędu, ale gdy zbliża się do linii faulu, synchronizuje swoje kroki, aby rzeczywisty skok był najbardziej efektywny. Sportowiec nie synchronizuje swoich kroków od początku biegu, ponieważ momentum jest ważniejsze na tym etapie.

0 dla odpowiedzi nr 4

Po brutalnym zmuszeniu kilku, niektórzy mogą zobaczyćwzorce do informowania o poszukiwaniach heurystycznych. Na przykład wiele najlepszych rozwiązań ma wzór taki jak dla D = 3, R = 40: seria małych wzrostów, seria większych wzrostów, a następnie skok 2x, po którym następuje krótki wzrost małych.

Przynajmniej mówi ci, aby nie iść z ideą podzbioru, gdzie wartości 3x30 są podzbiorem 3x40, na przykład.

tekst alternatywny