Определите этот алгоритм: слоты и колышки

Question

У меня есть несколько слотов и колышков, расположенных по прямой линии. Колышки могут быть перемещены и должны быть перемещены в слот каждый. Слот можно оставить пустым, только если все колышки заняты. Когда колышек перемещается, он не может пройти мимо другого колышка. Другими словами, порядок колышков должен быть сохранен. Предпочтительно общее расстояние, пройденное всеми колышками, должно быть минимальным. Насколько это возможно, колышек должен быть размещен в ближайшем доступном слоте.

Все, что я хочу знать, это: Какая область математики имеет дело с такой проблемой? Как называются какие-либо хорошо известные алгоритмы, которые имеют дело с подобными проблемами? Я ищу гугл фураж. Некоторые ключевые слова.

+--oooo-+--+---+---o--+------+--+-ooo+o-+-------o--+-----o-o-+-o

+ - Slots
o - Pegs

РЕДАКТИРОВАТЬ: Я думаю, что эта визуализация имеет больше смысла. Это два отдельных трека, которые нужно выстроить в линию.

Slots: +-------+--+---+------+------+--+----+--+----------+---------+--
Pegs:  ---oooo------------o--------------ooo-o---------o--------o-o---o

РЕДАКТИРОВАТЬ: Просто хочу прояснить, что количество слотов может быть больше, меньше или равно количеству колышков.

Answer 1

Я думаю, что это классический корм для динамического программирования . На самом деле, посмотрите «выравнивание последовательности», которое может быть еще одним хорошим поисковым термином на этой странице википедии.

Ключевое понимание заключается в следующем:

Представьте, что у вас есть колышки в виде списка позиций колышков (peg1: больше колышков) и слотов в виде списка позиций слотов (slot1: больше слотов). Назовите эту проблему (peg1: pegs, slot1: slots). Тогда решением будет либо peg1 в slot1 и решение (pegs, slots), либо решение (peg1: pegs, slots).

Это дает рекурсивное определение того, как ее решить.

Или в псевдокоде (написанном в стиле функционального программирования) представьте расстояние функции (колышек, слот):

distance([]) = 0
distance((peg,slot):matches) = distance(peg,slot)+distance(matches)

solution(peg:[], slot:[]) = [(peg,slot)]
solution(peg:pegs, slot:slots) = if distance(a)<distance(b) then a else b
   where a = solution(peg:pegs, slots) and b=(peg,slot):solution(pegs, slots)

Это решение должно стать более эффективным путем объединения расстояния в структуру данных.

Answer 2

Я не знаю, откуда возникла эта проблема, но я почти уверен, что это форма комбинаторной оптимизации , а точнее, той, которую можно решить с помощью (целое) линейное программирование .

Answer 3

"общее расстояние, пройденное всеми колышками должно быть как минимум "

Если я что-то упустил, это не проблема.

Поскольку порядок колышков необходимо поддерживать, вы можете просто нумеровать колышки 1, 2, 3, ...

+ - 1234 - + - + --- + --- 5 - + ------ + - + - 678 + 9 - + ------- 10 - + ----- 11-12 - + - 13

и конечное состояние должно быть: колышек 1 в слоте 1, колышек 2 в слоте 2 и т. Д.

+ - 1 - + - 2 - + - 3 - + - 4 - + - 5 - + - 6 - + - 7 - + - 8 - + - 9 - + - 10 - + - 11 - + - 12 - + - 13 - +

Неспособность прыгать колышки мимо друг друга не имеет значения, каждый колышек должен перемещаться на определенное расстояние от своей начальной точки до своей конечной точки. Пока все движения в правильном направлении и колышек никогда не должен отступать , тогда расстояние, которое должен пройти каждый отдельный колышек, является простой константой (она не зависит на порядок ходов) и сумму этих расстояний, ваша функция стоимости также постоянна.

Я не вижу здесь необходимости в динамическом программировании или в оптимизации линейного программирования.

Если вы введете стоимость подбора колышка и его установки, то, возможно, здесь есть проблема с оптимизацией, но даже это может быть тривиально.

Редактировать в ответ на 1800 Комментарий информации

Это верно только в том случае, если число Слоты равны количеству колышков - это не предполагалось в проблеме выписка - 1800 ИНФОРМАЦИЯ (2 часа назад)

ОК, я пропустил это. Спасибо, что указали на то, что мне не хватало. Я до сих пор не уверен, что это ракетостроение.

Предположим, # колышки> # отверстия. Вычислите конечное состояние, как указано выше, как если бы у вас были дополнительные отверстия; затем выберите N колышков, которые были перемещены дальше всего, и удалите их из задачи: это те, которые не были перемещены. Пересчитайте, игнорируя эти колышки.

Предположим, # отверстия> # колышки. Правильное конечное состояние может иметь или не иметь пробелы. Вычислите конечное состояние, как указано выше, и посмотрите, где соседние колышки смещены друг к другу. Это те точки, где вы можете разбить его на подзадачи, которые могут быть решены тривиально. Есть одна дополнительная переменная, когда у вас есть отверстия на обоих концах смежной подзадачи - там, где начинается финальная смежная последовательность.

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

Answer 4

Если количество колышков == количество слотов, существует только одно решение. Первый колышек ДОЛЖЕН перейти в первый слот, следующий колышек ДОЛЖЕН перейти в следующий слот и т. Д.

Числа отличаются, то это немного сложнее, потому что колышек или слот (не имеет значения, какой из них мы можем перемещать) можно перемещать во многие места.

Грубая сила: Предположим, что количество объектов равно m колышкам и n слотам (взаимозаменяемо), m

1. Для каждого пути (n-m) слотов может быть выбрано (см. некоторые комбинаторики алгоритмы чтобы посмотреть как это сделать)
   1. Там (n-m) выбранные слоты будут пустыми.
   2. Заполните m оставшихся слотов колышками. Рассчитать пройденное расстояние. Это становится таким же, как и случай, обсуждаемый сверху.
2. Выберите расположение с минимальным пройденным расстоянием.

Рекурсивное решение:

    int solve(int pegs, int *peg_x, int slots, int *slot_x)
    {
      if (slots > pegs )
        return solve(slots, slot_x, pegs, peg_x);
      if (slots == 0 || pegs==0)
        return 0; // Cannot move

      int option1 = INT_MAX, options2 = INT_MAX;


      if (pegs > slots ) // Can try skipping a peg
        option1 = solve(pegs-1, peg_x+1 /* Move over one element */
                          slots, slot_x);
      // pegs >= slots 
      option2 = solve(pegs-1, peg_x+1, slots-1, slot_x+1)
                + abs(peg_x[0]-slot_x[0]);
      return min(option1, option2);
    }

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

Мышление .... обновится .....

Answer 5

комбинаторика. Комбинаторные алгоритмы. Конкретная математика. (Также название отличная и актуальная книга Дональда Кнута.

Answer 6

Теория массового обслуживания или математика ...