Как я могу улучшить этот алгоритм для решения модифицированной головоломки Postage Stamp?

Проблема сорта Дартов - это конкурс на Конкурсы программирования Al Zimmermann, закончившиеся 20 июня 2010 года:

Предположим, что у вас есть мишень, разделенная на R областей. Каждая область дартс имеет положительное целочисленное значение, связанное с ней. Предположим, что у вас есть D дартс и что вы бросаете каждый из них на мишень. Каждый дротик либо попадает в одну из областей R борту, либо вообще пропускает плату. Ваша оценка - это сумма значений для регионов, в которых дротики земли. Дарт, который пропускает доску, ничего не дает для вашего счета. Если несколько дартов попадают в один и тот же регион, вы накапливаете значение для этого региона несколько раз.

Например, предположим, что R = 5, что области дартборда имеют значения (1, 2, 4, 7, 11) и что D = 3. Если ваши три дарта приземляются в регионах 2, 4 и 11 вы набрали 17 очков. Если один дротик пропустит доску и две другие земли в регионе 7, вы наберете 14 очков.
Задача Дартс заключается в следующем: для заданных R и D определите, какие значения должны быть связаны с областями R для карт Dartboard, чтобы максимизировать наименьший результат, недостижимый, бросая 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 |
|____|____|
```
Я генерирую массив scratch, который показывает, что все итоги достижимы, используя оценки дротика в массиве результатов в трех бросках. Подчеркнутые элементы - это те, которые были использованы для создания царапины.
```
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, например.
Алгоритм является жадным в том смысле, что он предполагает, что цель на каждом шаге (при создании массива result) заключается в достижении минимального недостижимого итога на этапе.
Чтобы работать лучше, чем грубая сила, алгоритм устраняет некоторые кандидаты для массива результатов. Например, в случае, показанном на диаграмме ниже (для массива <(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 (для каждого выбора у меня может быть либо лучший, либо второй лучший или третий лучший элемент) случаев, которых слишком много. Итак, я решил пойти с максимальной секундой лучше всего и на треть один лучший выбор. Это уменьшило количество случаев до примерно ⁴⁰ C ₁ * ³⁹ C ₁= 577980 результатов. Более того, это приведет к большому числу случаев для более высоких значений R (для более высоких значений D).
Из этих результатов ~ 6E5, которые у меня есть, я вычисляю минимальный недостижимый элемент для каждого значения R от 1 до 40. Таким образом, каждое из значений R получает выбор наилучшего из этих значений 6E5.

ПРОБЛЕМЫ

Этот алгоритм не создает лучшие результат множества или даже закрывает.
Я даже пошел на четвертый и пятый лучший выбор для D = 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 по только что перечисленным числам и завершить его выполнение за всю свою жизнь. Очевидно, пришло время искать новую технику. Я полагал, что я отлично справляюсь с внешним интерфейсом, проверяя каждый возможный стартовый сегмент, поэтому почему бы не переместить некоторые из них на задний план, проверяя более глубокие результирующие наборы для каждого из моих начальных сегментов. Вместо того, чтобы захватить лучший следующий результат на том же уровне, я выполнил двухуровневый взгляд вперед и получил лучшее следующее значение с двух уровней в глубину. Например, вы всегда начинаете с 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. Это потребовало гораздо большего времени обработки и потребовало, чтобы я уменьшил max R, который мог бы использовать для его семени, но он дал лучшие результаты для более глубоких поисков.

В этот момент я отказался от жадных подходов и использовал этот конкурс для расширения знаний по ИИ. Я пробовал использовать различные методы monte carlo, а также базовый генетический алгоритм. Я много узнал о монте-карло, и, взглянув на некоторых из лучших исполнителей этого конкурса, нашел публикации об оптимизации для критериев отбора монте-карло, которые были выше моего понимания. Хотел бы я помочь вам в дальнейшем, но я уверен в том, что в моей жизни очень маловероятно, что нарушение 90 пунктов с жадным подходом очень маловероятно. Мне было бы интересно посмотреть, насколько лучше получат ответы, если бы они были многопоточными, и куча власти была брошена на него.

У меня нет какой-либо работы, которую я сделал для этой проблемы со мной, но я помню, что это выглядело вперёд, и большее количество начальных семян было единственным возможным улучшением жадного алгоритма для этой проблемы. Я буду этим вечером и отправлю мыслительный процесс здесь, если найду заметки.

EDIT: код, первоначально размещенный на сервере, который был оставлен. Пожалуйста, сообщите, если вы хотите, чтобы он был повторно отправлен.

Ответ 2

Спасибо за очень интересный вопрос! Я потратил несколько минут на понимание вопроса.

Я не видел нотной формулировки проблемы, поэтому позвольте мне сделать снимок с обозначением здесь.

Во-первых, наблюдение (как вы правильно сделали), одна из областей должна быть 1, иначе 1 не будет достижима.

Во-вторых, поскольку мы пытаемся МАКСИМАЛЬНО недостижимый балл, нет смысла повторять значения региона.

Итак, это дает вырожденное (но не оптимальное) решение: 1, 2, 3,... R

Значение целевой функции этого вырожденного решения: 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

[Будет продолжать работать над этим и публиковать больше, когда я его развиваю.]

Ответ 3

Максимальный наименьший недостижимый элемент хорош, чтобы искать только в последней итерации. Лучшее первичное подцель - это количество достижимых элементов с заданным количеством дротиков. Одним из интересных подцелей может быть

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

Nae - количество достижимых элементов (с заданным количеством дротиков)
Rt - общие доступные регионы
Rc - используемые в настоящее время регионы (текущий уровень рекурсии)
Msue - максимум наименьшего недостижимого элемента

Почему Nae более ценна, чем Msue на ранних итерациях? Чем более достижимые элементы у нас есть на ранней стадии, все последующие элементы меня будут более трудоспособными и производят больше комбинаций и достигают еще более достижимых элементов. При взрыве Nae существует высокая вероятность того, что Msue также повысится до хорошего уровня. Тем не менее, в поздних итерациях Msue становится более важным, и новые элементы больше используются для "подключения отверстий", с надеждой на то, что последнее отверстие для подключения будет максимально возможным.

Физическая аналогия этого рассуждения была бы олимпийским длинным прыжком, где спортсмен в начале пробега сначала накапливает импульс, но когда он приближается к фол-линии, он синхронизирует свои шаги, так что фактический прыжок становится наиболее эффективным. Спортсмен не синхронизирует свои шаги с самого начала прогона, потому что импульс более важен на этом этапе.

Ответ 4

После того, как вы нажмете несколько, вы можете увидеть некоторые шаблоны, чтобы сообщить эвристические запросы. Например, многие из лучших решений имеют такой же шаблон для D = 3, R = 40: пробег небольшого увеличения, пробег большего увеличения, затем 2x-прыжок с последующим небольшим увеличенным малым увеличением.

По крайней мере, это говорит вам не идти с идеей подмножества, где значения 3x30 являются подмножеством 3x40, например.