Мне нужна помощь по этой проблеме ACM ICPC. Моя текущая идея состоит в том, чтобы смоделировать это как задачу кратчайшего пути, которая описана в формулировке проблемы.
проблема
Есть N = 1000
контейнеры ядерных отходов , расположенных вдоль числовой прямой 1-D в различных позициях от -500,000 to 500,000
, за исключением x=0
. Человеку поручено собрать все мусорные баки. Каждую секунду, когда контейнер для отходов не собирается, он излучает 1 единицу излучения. Человек начинает с x = 0
и может перемещать 1
юнит каждую секунду, а сбор отходов занимает незначительное количество времени. Мы хотим найти минимальное количество радиации, выделяемой при сборе всех контейнеров.
Пример ввода:
4
Контейнеры расположены по адресу [-12, -2, 3, 7]
.
Наилучший порядок сбора этих контейнеров - [-2, 3, 7, -12]
минимальное количество 50
единиц. Пояснение: человек идет -2
через 2 секунды и за это время 2 units
излучение испускается. Затем он идет 3
(расстояние 5
:), чтобы ствол выпустил 2 + 5 = 7
единицы излучения. Ему требуется 4
больше секунд, чтобы добраться туда, x = 7
где этот ствол испустил 2 + 5 + 4 = 11
юниты. Ему нужны 19
секунды, чтобы добраться туда, x = -12
где этот ствол испустил 2 + 5 + 4 + 19 = 30
юниты. 2 + 7 + 11 + 30 = 50
, который является ответом.
Примечания
Есть очевидное O(N!)
решение. Однако я исследовал жадные методы, такие как переход к ближайшему или переход к ближайшему кластеру, но они не сработали.
Я долго думал об этой проблеме, и смоделировал ее как проблему поиска графа:
- Мы вставляем
0
в качестве базовой позиции (это будет начальное состояние) - Затем мы сортируем позиции от наименьшего к наибольшему.
- Затем мы делаем BFS / PFS, где
state
состоит из- Два целых числа ,
l
иr
которые представляют собой непрерывный диапазон в отсортированном массиве позиции , которые мы посетили уже - Целое число,
loc
которое говорит нам, находимся ли мы в левой или правой конечной точке диапазона - Целое число,
time
которое сообщает нам прошедшее время - Целочисленная «стоимость», которая сообщает нам общую стоимость (на основе посещенных нами узлов)
- Два целых числа ,
- Из каждого состояния мы можем перейти к [l - 1, r] и [l, r + 1], соответственно настраивая остальные 3 целых числа
- Конечное состояние - [0, N], проверяя обе конечные позиции.
Тем не менее, кажется, что [L, R, loc]
это не однозначно определяет состояние, и мы должны хранить L, R, loc, and time
, минимизируя cost
при каждом из них. Это приводит к экспоненциальному алгоритму, который все еще слишком медленный для пользы.
Может ли кто-нибудь помочь мне расширить мою идею или подтолкнуть меня в правильном направлении?
Редактировать: Может быть, это может быть смоделировано как проблема оптимизации динамического программирования? Размышляя об этом, он имеет те же проблемы, что и решение для поиска в графике - просто потому, что ток cost
низкий, не означает, что он является оптимальным ответом для этой подзадачи, так как он time
также сильно влияет на ответ.
Жадность не работает: у меня есть жадный алгоритм выбора, который оценивает стоимость перемещения в определенное место (например, если мы движемся вправо, мы удваиваем расстояния до левых стволов и тому подобное).
Не могли бы вы сделать приоритетный поиск с эвристикой? Эвристика может объединять стоимость текущей поездки с количеством прошедшего времени.
источник
Ответы:
Я думаю, что вы можете улучшить это, рассматривая проблему как ориентированный граф пар позиций.
Для этого примера я буду использовать строку со значениями -9, -6, -1, 3 и 5.
Поскольку нарисовать график с помощью простого текста слишком сложно, я собираюсь представить пары в виде таблицы. Мы можем думать о ячейках как о состоянии, в котором были собраны все контейнеры между этими двумя позициями. Каждая ячейка имеет два значения, одно из которых представляет стоимость перехода влево, а другую - стоимость перехода вправо (к следующему контейнеру).
Значения могут быть просто рассчитаны как расстояние между двумя точками, умноженное на количество баррелей за пределами этих двух точек + 1 . Ячейки, в которых оба числа имеют одинаковый знак, представляют случаи, когда были собраны все бочки противоположного знака. Они рассчитываются с использованием только количества стволов в направлении от нуля.
В таблице значения X означают, что вы не можете идти в этом направлении (все бочки в этом направлении были взяты). Строки представляют текущее положение коллектора, а столбцы представляют местоположение следующего противоположного ствола.
Правила перемещения между квадратами могут быть несколько запутанными.
Для столбцов с отрицательными номерами действуют следующие правила:
Для столбцов с положительными номерами действуют следующие правила:
Теперь мы можем запустить алгоритм Дейкстры, чтобы рассчитать лучший путь, используя эти правила движения для обхода графика. Наши стартовые позиции (-1, 3) и (3, -1) с начальными затратами 5 и 15 соответственно. После того, как мы вычислили значения для двух конечных положений (слева от (-9, -9) и справа от (5, 5)), нашим ответом будет меньшее из двух.
Время выполнения для каждого из шагов:
Первые два шага преобладают над последними, поэтому ваше общее время выполнения равно O (N ^ 2 log N), которое должно быть достаточно хорошим временем выполнения для задачи.
источник
Наименьшее расстояние
Я написал вчера приложение Java, чтобы решить эту проблему. Эта проблема, по сути, является проблемой кратчайшего расстояния, как сказал SRJ в своем комментарии. Излучение просто показывает, что вы можете накопить значение вместе с кратчайшим расстоянием.
По сути, вот что я сделал.
Вот некоторые выводы из приложения
Я не оптимизировал алгоритм никоим образом. Я даже не заметил, что входной список чисел был отсортирован. (Я тупица.)
Когда я запускал свой код с максимальными значениями, 1000 контейнеров и диапазоном от -500 000 до 500 000, мой код выполнялся за 3 секунды. Большую часть времени он записывал на консоль 1000 строк печати.
Я не большой человек О, но я думаю, что мой грубый ход по алгоритму кратчайшего пути - это О (N в квадрате), а не О (N!).
Если бы я воспользовался тем фактом, что входные числа отсортированы, так что мне нужно было проверить только два числа по обе стороны от того места, где я сейчас нахожусь, я мог бы приблизить приложение к O (N). Мне нужно только проверить 2 числа, потому что я удаляю элементы из списка по мере их поступления.
Вы использовали разные алгоритмы, такие как жадный алгоритм, чтобы найти приближенное решение.
Если бы моей программе потребовалось 3 часа вместо 3 секунд, то у вас был бы выбор.
Достаточно ли хорошее решение достаточно хорошо?
Другими словами, готов ли я обменять скорость обработки на достаточно хороший ответ?
Если достаточно хороший ответ достаточно хорош, то вы используете приближенные алгоритмы.
Если вы хотите идеальный ответ, вы должны пройти все кратчайшие пути. Там нет ярлыка.
Если кто-то захочет, чтобы я опубликовал свой код, я сделаю это. Я уверен, что все еще есть ошибки, так как я хотел посмотреть, смогу ли я реализовать алгоритм кратчайшего обхода.
источник
У меня есть решение, которое решит эту проблему
2^N
вовремя, но оно плохое, но я думаю, что это полезный способ сформулировать проблему, поэтому я решил опубликовать.Вместо того, чтобы смоделировать проблему в виде графика, я бы смоделировал это, скажем, двоичное дерево решений
T
. На каждом уровне вы должны выбирать между движением направо или налево. Довольно просто рассчитать «стоимость» каждого ребра. Позвольтеh(K)
быть высота текущего узлаK
, а затем стоимость края собираетсяleft_child(K) = h(K) x dist(K, left_child(K))
. Подобного расчета достаточно для стоимости ребра для нужного ребенка. Вы создаете это дерево и отслеживаете совокупную стоимость ребер на всем пути вниз и сообщаете путь к конечному узлу с наименьшей общей стоимостью.Обратите внимание, что расчет стоимости работает, потому что длина каждого ребра
dist(K, left_child(K))
представляет время для перехода к следующему сайту, а высота поддерева - это количество оставшихся сайтов (например, все еще излучающих излучение).Теперь хитрость в этой структуре состоит в том, чтобы определить, есть ли какие-то эвристики, которые вы можете использовать, чтобы «доказать», что вы можете игнорировать расширение поиска по некоторой ветви. Моя интуиция заключается в том, что для любой такой эвристики есть расположение сайтов, которые ее победят, но, возможно, кто-то может что-то придумать.
Некоторые предложили применять решения для кратчайших путей для графов, у меня есть некоторые сомнения относительно того, может ли такое решение работать. Ваши соседи по «графику» задачи будут меняться в зависимости от пути, которым вы следуете. Например, в исходном сообщении,
[-12, -2, 3, 7]
если вы идете в-2
то-12
и3
становитесь «соседями», а если вы идете в «3
тогда»-2
и «7
соседями». Каждая возможная «пара» положительных и отрицательных значений потенциально может быть соседями в конечном графике. Я не знаю ни одного алгоритма кратчайшего пути, который доказуемо корректен в динамическом графе.источник
Я думаю, что имеет смысл думать о каждой стадии просто как о бинарном выборе между движением вправо до ближайшего ствола и движением влево до ближайшего ствола. Просто имейте функцию стоимости, которая детализирует количество единиц радиации, которые будут понесены в целом, делая любое движение, и выберите ту с наименьшей стоимостью.
НЕ просто рассматривайте ближайший ствол, а вместо этого предполагайте, что, удаляясь от ствола, вы фактически добавляете вдвое больше излучения, потому что, удаляясь, вы также понесли расходы на то, чтобы позже двигаться назад в этом направлении.
В вашем примере [-12, -2,3,7] перемещение влево повлечет за собой 14 (2 + 2 + 10) слева и 18 (2 + 2 + 5 + 9) справа, всего 22. Движение вправо повлечет за собой 10 (3 + 3 + 4) справа и 26 (3 + 3 + 5 + 15) справа. Ясно, что слева - правильное решение на первый взгляд. Аналогичный расчет можно сделать для каждого последовательного движения.
После этого проблема в основном сводится к поиску, поэтому сложность должна быть O (nlog (n)), что НАМНОГО лучше, чем O (n!). Я считаю, что это обязательно самая низкая сложность, которая может существовать для этой проблемы, поскольку это в основном алгоритм поиска, основанный на сравнении, для которого невозможно добиться большего успеха, чем O (nlog (n))
По-видимому, я не был достаточно понятен с этим описанием, поэтому я решил сделать его немного более программным: 1. Рассчитать стоимость, понесенную при движении влево, и стоимость, понесенную при движении вправо, на основе текущей позиции 2. Переместить в Наименее дорогостоящее направление 3. Уберите достигнутый ствол из расчета при расчете стоимости перемещения в направлении.
Расчет стоимости: 1. Определите ближайший ствол в заданном направлении. Допустим, $ dist - это расстояние от текущей позиции до ближайшего барреля в заданном направлении. 2. Стоимость инициализируется как N * $ dist, где N учитывает только все еще активные стволы. 3. К этому добавьте расстояние, которое новая позиция, обозначенная $ dist, будет от каждого оставшегося барреля.
источник
[43, -18, -98, -82, 63]
[-10,-11, 10,20,30,40,50,60,70]
. Правильное и единственное решение - собрать все отрицательные, а затем собрать положительные. Для ответа 455.Частичное решение - я вернусь к нему позже.
Предположим, что стратегия «по умолчанию» выполняется полностью влево или вправо, в зависимости от того, что дешевле. А теперь спросите, стоит ли немного побочного пути другим способом забрать одну бочку. Это довольно легко рассчитать ответ.
Для вашей выборки ввод полностью вправо обходится дешевле, чем полностью слева. Собирается ли -2 на боковую поездку? Снижается стоимость бега в нужном направлении, а затем обратно до 0 на 14 (потому что вы «платили» 4 единицы радиации за ход с 0 до 3 в стратегии по умолчанию, теперь она снижается до 3, вы платили 3 из 3 до 7, теперь это 2 и т. д.), плюс уменьшает на 1 за ход ваши затраты на переход от 0 до -2, таким образом, экономя еще 2 на общую сумму 16.
Тем не менее, это добавляет стоимость перехода к -2, затем обратно к 0 из 14 (4 единицы за ход до -2, 3 за ход обратно до 0), для чистого прироста (16-14) = 2. Обратите внимание, что для расчета этого вам не нужно оценивать точную стоимость решения всей проблемы для каждого решения - у вас есть достаточно информации, чтобы принять решение, просто зная, дешевле ли работать весь путь влево, чем работать полностью вправо, плюс как много мусорных контейнеров на каждой стороне от вас, и расстояние до ближайшего 2. Так что это O (N ^ 2).
За исключением одной важной проблемы - я предполагал, что вы пробежите до конца, и мы знаем, что вы можете отступить. Чтобы очистить это, мы должны обновить мой расчет. Для ввода образца я предположил, что вы сэкономите 14, испуская на 1 единицу меньше общего излучения в секунду при работе от 0 до 7 и обратно. Но если вы удвоитесь до 7, вы сэкономите.
Это довольно плохо, потому что я не знаю, как рассчитать следующий двойной возврат, не испробовав все возможности, что возвращает нас к O (2 ^ N).
За исключением - это 2 ^ N с обрезкой. Я подсчитал, что «боковая поездка» до -2 стоит 14, но набрал 16, если у меня не было больше побочных поездок, прежде чем я добрался до самого правого числа. Если бы самый правый номер был 5, я бы сразу понял, что дополнительная поездка до -2 не окупится. (Стоимость еще 14, максимальная выгода 12). И при этом я не должен думать о том, чтобы пойти в -2, а затем совершить боковое путешествие, прежде чем достигнуть 6, поскольку это всегда хуже, чем просто идти прямо к этой точке.
источник
Я думаю, что вы можете решить это, используя поиск в ширину, поддерживая не более 2 * N ^ 2 кортежей (boolean, int, int, int, string), где строки такие же, как и сложный путь.
Кортежи (мин. Или макс. Логическое значение, мин. Пройденное положение, макс. Пройденное положение, общее излучение, история пути).
Я вижу, что алгоритм работает так:
Поиск и удаление доминирующих кортежей значительно улучшит производительность. Возможно, стоит добавить флаг 'has bred' к каждому кортежу и оставить его в пуле.
Есть также некоторые важные решения, которые необходимо принять при принятии решения о том, как хранить кортежи и искать в них доминанты и новые элементы для размножения.
источник