Я действительно участвовал в этом конкурсе, как вы заметили, я занял 100-е место в общем с набранными 87,00 очками.Я на самом деле использовал ваш метод, потому что понял, что создание «разумного» решения для каждой проблемы было первым препятствием, которое нужно преодолеть.В то время, когда я набрал его, сгенерированных очков было достаточно, чтобы поднять меня до 94 баллов, но по мере того, как лучшие игроки улучшили свои баллы, это число быстро упало до 75.
Первая и самая легкая вещь, которую вы можете сделатьэто понять, что ваша программа запускается в одно мгновение, и если это не так, вы должны потратить время на оптимизацию дерьма из этого в первую очередь.Как только он запустится за достаточно короткое время, вы можете создать любой возможный набор для D = 3, R <= 5 в кратчайшие сроки.Затем вы можете использовать наборы на R = 5 в качестве начальных значений для вашего жадного алгоритма.Теперь вместо одного жадного решения у вас есть несколько тысяч, и вам просто нужно отслеживать самое высокое значение, генерируемое на каждом уровне R, и значения, которые его создают.Это достаточно легко сделать, и это повысит ваш счет выше 80.
Я потратил почти месяц на оптимизацию функции, которая может тестировать любой набор случайных входов, чтобы я мог накачать свой генератор семян доR = 10 и запустите его примерно за 8 часов на одном ядре.Это гарантировало наилучшее возможное решение для «D = 3», «R <= 10» и гораздо лучшие ответы при <code>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.Это потребовало намного больше времени на обработку и потребовало от меня уменьшения максимального значения R, которое я мог использовать для его заполнения, но это дало лучшие результаты для более глубоких поисков.
В этот момент я отказался от жадных подходов ииспользовал этот конкурс, чтобы расширить свои знания AI.Я пытался использовать различные техники Монте-Карло, а также базовый генетический алгоритм.Я многое узнал о Монте-Карло и, отыскивая некоторых из лучших участников этого конкурса, нашел публикации по оптимизации критериев отбора в Монте-Карло, которые были за пределами моего понимания.Я хотел бы помочь вам в этом, но я уверен, что могу утверждать, что преодоление 90 очков с жадным подходом очень маловероятно в моей жизни.Мне было бы интересно узнать, насколько лучше получились бы ответы, если бы они были многопоточными и на них было наложено много энергии.
У меня нет никакой работы, которую я выполнял для этой проблемы со мной,но я помню, как показывал, что взгляд в будущее и большее количество начальных семян были единственными двумя возможными улучшениями жадного алгоритма для этой проблемы.Я расскажу об этом сегодня вечером и опубликую здесь мыслительный процесс, если смогу найти заметки.
РЕДАКТИРОВАТЬ: код, первоначально размещенный на сервере, который был заброшен.Пожалуйста, отправьте сообщение, если хотите, чтобы оно было опубликовано повторно.