Проблема сина Дартса був конкурс на Конкурси програмування Аль Циммермана що закінчилося 20 червня 2010 року:
Припустимо, у вас є дротик, який розділенийв R регіони. Кожна область дартсборда має з цим пов’язане додатне ціле значення. Далі припустімо, що у вас є D дартс і що ви кидаєте кожен із них на дартс. Кожен дротик або приземляється в одному з R-областей дошки, або взагалі не вистачає дошки. Ваш бал - це сума значень для регіонів, в яких приземляється дартс. дартс приземляється в одному регіоні, ви накопичуєте значення для цього регіону кілька разів.
Наприклад, припустимо, що R = 5, щоУ областях дартсборду є значення (1, 2, 4, 7, 11), і D = 3. Якщо ваші три дартси приземляються в регіонах 2, 4 і 11, ви набираєте 17 балів. Якщо один дартс не вистачає на дошці, а інші два - у регіоні 7, ви набираєте 14 балів.
Проблема з дартсом така: для заданих R і D визначте, які значення повинні бути пов'язані з R-областями дартсборду, щоб максимізувати найменший бал, недосяжний за допомогою метання 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
================================================== ================================
ВИКОРИСТАНО ОСНОВНИЙ АЛГОРИТМ (пояснено для D = 3)
Я починаю з результат показано нижче. 0 і 1 - це бали, які повинні бути там, на областях дартс. 0 вказує на те, що дротик пропустив дошку. Отже, я збираюся створити цей масив для 41 елемента (один додатковий, щоб компенсувати 0) 1 є обов'язковим, оскільки в іншому випадку іншого способу генерування немає 1.
____ ____ | | | | 0 | 1 | |____|____|Я генерую подряпина масив, який показує, які всі підсумки досяжні за допомогою дартс-балів у масиві результатів у три кидки. Підкреслені елементи - це ті, які були використані для створення подряпина.
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 | |__-_|__-_|____|____|____|____|____|____|____|____|____|____|____|Тепер кандидатами на наступний елемент у масиві результатів є 2, 3 або 4.
2 = елемент на один більший за поточний найбільший елемент
4 = тонкий недосяжний елемент
Я спробую по черзі кожного з цих кандидатів і бачу те, що є максимум найменших недосяжних елементів у кожному випадку. Наприклад
(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. Так, 3 вибирається як наступний елемент.Якщо припустити, що, наприклад, я мав би вибирати між (0, 1, 2) і (0, 1, 4), щоб розірвати краватку, я б порахував кількість досяжних чисел, яка більше у випадку (0, 1, 4). Отже, я вибрав би (0, 1, 4) понад (0, 1, 2)
Але в цьому випадку (0, 1, 3) є переможцем, і набір результатів виглядає нижче. Потім я повторюю кроки, поки у мене не з’явиться 41 елемент.
____ ____ ____ | | | | | 0 | 1 | 3 | |____|____|____|Алгоритм жадібний в тому сенсі, що вінпередбачається, що (рішення для R = 20) є підмножиною (рішення для R = 30). Отже, я не обчислюю результати для кожного значення R, але я обчислюю результати для кожного значення D. Отже, для D = 3 я підраховую результат для R = 40, а потім беру перші 30 елементів результату для R = 30, наприклад.
Алгоритм жадібний в тому сенсі, що він передбачає, що ціль на кожному кроці (при створенні результат масив) - це досягнення мінімально недосяжного загального на етапі.
Щоб мати змогу краще виконати грубу силу, алгоритм виключає деяких кандидатів у масив результатів. Наприклад, у випадку, зображеному на схемі нижче (для (0, 1, 4) результат масив), я вважаю лише кандидатами 5, 6 та 7для наступного елемента та виключіть 2 та 3, хоча вони все ще не використовуються. Це припущення може дати мені неоптимальні результати в деяких випадках, але воно скорочує багато обчислень, коли подряпина виростає до тисяч елементів.
____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ | * | * | * | * | * | * | * | | * | * | | | * | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|
ВДОСКОНАЛЕННЯ ДО АЛГОРИТМУ
Оскільки це не давало надто хороших результатів, я спробував генерувати набори результатів для кожного значення D. Наприклад, замість того, щоб вибрати найкращий наступний елемент для результат, Я також міг вибрати другого кращого аботретій найкращий елемент. Отже, за 39 кроків (до 41 елемента в результаті) я міг генерувати близько 3 ^ 39 (для кожного вибору я можу мати найкращий або другий найкращий або третій найкращий елемент) випадків, яких занадто багато. Отже, я вирішив зробити хоча б одну секунду найкращого і принаймні одну третину найкращих варіантів. Це зменшило кількість справ до навколишнього 40С1 * 39С1 = 577980 результатів. Більше, ніж це призведе до ВЕЛИЧЕЗНОЇ кількості випадків для більш високих значень R (для більш високих значень D).
З цих ~ 6E5 результатів, які я маю, я обчислюю мінімальний недосяжний елемент для кожного значення R від 1 до 40. Отже, кожне із значень R отримує вибір із найкращих з цих значень 6E5.
ПРОБЛЕМИ
Цей алгоритм не найкращий результат набори, або навіть закрити.
Я навіть перейшов до четвертого та п’ятого найкращих виборів для D = 3, і вони не дали значних поліпшень результатів. Отже, я не знав, де слід настроїти свій алгоритм.
Де все я можу налаштувати цей алгоритм, щоб отримати кращі результати?
Чи є явні помилки, які робить алгоритм?
Будь-які коментарі / пропозиції вітаються.
Було ще одне питання на цю ж тему тут. Мені більше цікаво знати, де мій алгоритм можна вдосконалити.
Відповіді:
3 для відповіді № 1Я фактично брав участь у цьому конкурсі, як і визауважте, що я посів 100 місце із загальним набраним 87,00 балів Я фактично використовував ваш метод, тому що я зрозумів, що генерування «розумного» рішення для кожної проблеми було першим перешкодою для подолання. На той момент, коли я його запускав, набраних балів вистачило на 94 бали, але в міру того, як найкращі заробітці покращили свої показники, ця кількість швидко впала приблизно до 75.
Перше і найпростіше, що ви можете зробити - це зробитизрозумійте, що ваша програма запускається в одну мить, і якщо це не робити, вам слід витратити час на оптимізацію лайно з цього першого. Після того, як вона працює досить швидко, ви зможете генерувати кожен можливий набір для D = 3, R <= 5 у найкоротший час Потім ви можете використовувати набори на R = 5 як насіння для вашого жадібного алгоритму. Тепер замість одного жадібного рішення у вас є кілька тисяч, і вам просто потрібно слідкувати за найвищим значенням, що генерується на кожному рівні R, і значеннями, які його створюють. Це зробити досить просто, і це призведе до того, що ваш результат буде вище 80.
Я витратив майже місяць на оптимізацію функції, яка може перевірити будь-який набір випадкових входів, щоб я зміг підкачати свій генератор насіння R = 10 і запустіть його приблизно за 8 годин на одному ядрі. Це гарантувало найкраще можливе рішення для "D = 3", "R <= 10" і набагато кращі відповіді, коли R > 10 ніж у мене з оригінальним жадібним результатом. Це отримало мій рахунок досить близько до того, де він закінчився після запуску R вгору якомога вище для кожного D при цьому ще можна запускати програму за один день. Я зміг дістатися R = 9 за D = 4, R = 8 за D = 5, і R = 8 за D = 6.
Після їх запуску я порахував, що не зможу збільшити R по 1 для будь-якого D над щойно перерахованими номерами та заповнити йогоїї виконання за мого життя. Очевидно, що настав час шукати нову техніку. Я зрозумів, що я роблю велику роботу на передньому кінці, перевіряючи кожен можливий стартовий сегмент, то чому б не перенести частину на задній кінець, перевіривши більш глибокі набори результатів для кожного мого стартового сегмента. Замість того, щоб захопити найкращий наступний результат на тому ж рівні, я здійснив 2-х рівневий погляд вперед і взяв найкраще наступне значення з двох рівнів глибиною. Наприклад, ви завжди починаєте з 1, а потім перераховуєте всі значення для R = 2 (2, 3, 4) а потім для кожного з них оцініть усі можливі значення для R = 3. Так 2 (3, 4, 5, 6, 7), 3 (4, 5, 6, 7, 8), 4 (5, 6, 7). Візьміть найвищу з усіх оцінок, а потім виберіть значення R = 2 який містить найвище значення для R = 3. Це вимагало значно більше часу на обробку і вимагало від мене знизити макс R Я міг би використовувати її для висіву, але це дало кращі результати для більш глибоких пошуків.
У цей момент я відмовився від жадібних підходів івикористовував цей конкурс, щоб розширити свої знання про AI. Я спробував використовувати різні методи Монте-Карло, а також основний генетичний алгоритм. Я дізнався багато про monte carlo, і, шукаючи деяких найкращих виконавців у цьому конкурсі, знайшов публікації про оптимізацію за критеріями відбору monte carlo, що було поза моїм розумінням. Я б хотів, щоб я міг вам допомогти далі, але я впевнено стверджую, що зламати 90 балів жадібним підходом в моєму житті дуже малоймовірно. Мені було б цікаво побачити, наскільки краще відповіді отримали б, якби вони були багатопотоковими і на неї кинули купу сили.
Я не маю жодної роботи, яку я зробив для цьогоПроблема зі мною, але я пам’ятаю, що показали, що погляд уперед та більший перелік вихідних насіння були єдиними двома можливими вдосконаленнями жадного алгоритму цієї проблеми. Я буду вечора за ці речі сьогодні та розміщую тут процес думки, якщо зможу знайти нотатки.
EDIT: код, спочатку розміщений на сервері, який був покинутий. Будь ласка, повідомте, якщо ви хочете, щоб це було повторно розміщено.
1 для відповіді № 2
Дякую за дуже цікаве запитання! Я витратив кілька хвилин на розуміння питання.
Я не бачив нотаційного формулювання проблеми, тож, дозвольте мені спробувати придумати нотацію тут.
По-перше, зауваження (як ви правильно зробили), одна з областей повинна бути 1, інакше 1 не буде доступною.
По-друге, оскільки ми намагаємось МАКСИМІЗУВАТИ недосяжний результат, немає сенсу повторювати значення регіону.
Отже, це дає вироджене (але не оптимальне) рішення: 1, 2, 3, ... R
The цільове значення функції цього виродженого розчину: D * R + 1
Наприклад, якщо у вас D = 4 дартса, і ви забарвлюєте дартс в балах 1, 2.40, то кожен бал від значень 1 до 160 досягається. 161 недосяжний.
Очевидно, що це рішення не є оптимальним, і оптимальне рішення передбачає, можливо, деякі сили 2 і, безумовно, деяку думку.
Тепер для позначення:
Нехай f (X, D, {Y_1..Y_R}) =
- 1, якщо бал X досягається, використовуючи D дартс на дартсі з діапазони Y_1 ... Y_R
- 0, якщо це неможливо
Як приклад, обговорений раніше. f (160,4, {1..40}) = 1 і f (161,4, {1..40}) = 0
Цільове значення головоломки може бути позначено як:
g (D, (Y_1..Y_R}) = Min X | f (X, D, {Y_1..Y_R}) = 0
Спостерігаючи 1 раніше, можна припустити, що Y_1 = 1.
Також рекурсивна формулювання функції f може бути наступною.
f (X, D, {1..Y_R} = 1, якщо:
- X = 0, або
- f (X-Y_j, D-1, {1..Y_R}) = 1 для деякого j
[Продовжуватиму працювати над цим і публікувати більше, коли я буду його розробляти.]
1 для відповіді № 3
Максимум найменшого недосяжного елементадобре шукати лише в останній ітерації. Краща первинна ціль - кількість досяжних елементів із заданою кількістю дартс. Один цікавий підряд може бути
Nae * (Rt - Rc) / Rt + Msue, where
- Nae - кількість досяжних елементів (із заданою кількістю дартс)
- Rt - загальнодоступні регіони
- Rc - використовувані в даний час регіони (поточний рівень рекурсії)
- Msue - максимум найменшого недосяжного елемента
Чому Нае цінніше, ніж Мессі на початкуітерації? Чим більше досяжних елементів у нас на початку, тим наступні елементи стануть мені більш працездатними і створюють більше комбінацій, і досягають ще більш досяжних елементів. З вибухом Нее виникає велика ймовірність того, що Мсее також підніметься на хороший рівень. Однак у пізніх ітераціях Msue стає важливішим, і нові елементи використовуються більше для «забивання отворів», сподіваючись, що останній отвір, який заткнеться, буде найдалі можливим.
Фізична аналогія цього обґрунтування була болімпійські стрибки в довжину, де спортсмен на початку бігу спочатку накопичує силу, але коли він наближається до лінії фолу, він синхронізує свої кроки, щоб фактичний стрибок став найбільш ефективним. Спортсмен не синхронізує свої кроки з початку бігу, тому що на цій стадії важливіший імпульс.
0 для відповіді № 4
Як тільки ви нагнітите кілька, ви можете їх побачитишаблони для інформування евристичних пошуків. Наприклад, багато верхніх рішень мають такий малюнок, як цей для D = 3, R = 40: пробіг малих збільшується, біг більших збільшується, потім 2-х стрибок з коротким пробігом малих збільшується.
Принаймні, це говорить про те, що ви не ходите з ідеєю підмножини, де, наприклад, значення 3x30 є підмножиною 3x40.
