Интервью головоломки о путешествии на отрезке

10

На числовой линии длины M, где 0 < M <= 1,000,000,000вы задали N( 1 < N <= 100,000) целочисленные пары точек. В каждой паре первая точка указывает, где в данный момент находится объект, а вторая точка указывает, куда должен быть перемещен объект. (Имейте в виду, что secondточка может быть меньше, чем first).

Теперь предположим, что вы начинаете с той точки, 0и у вас есть корзина, в которой можно держать 1объект. Вы хотите переместить все объекты из их начальных положений в их соответствующие конечные положения при перемещении наименьшего расстояния вдоль числовой линии ( не смещения). Вы должны в конечном итоге на точку M.

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

Я нарисовал эти 3примеры тестов здесь:http://i.stack.imgur.com/zRv4Q.png

Ответ на первый тестовый пример 12. Сначала вы берете redпредмет в точку 0. Затем вы перемещаетесь в точку 6(расстояние = 6), redвременно отбрасываете предмет, а затем подбираете greenпредмет. Затем вы перемещаетесь в точку 5(расстояние = 1) и опускаете greenпредмет. Затем вы возвращаетесь в точку 6(расстояние = 1) и поднимаете redпредмет, который вы уронили, перемещаетесь в точку 9 (расстояние = 3), затем перемещаетесь в точку 10(расстояние = 1), чтобы завершить последовательность.

Общее пройденное расстояние было 6 + 1 + 1 + 3 + 1 = 12минимально возможным.

В двух других случаях есть ответы 12, я полагаю. Однако я не могу найти общее правило для его решения.

У кого-нибудь есть идеи?

Дэвид
источник
Если я не ошибаюсь, не нужна ли вам структура данных для подсчета "перекрытия"? В противном случае я решаю это неправильно.
Дэвид
вы все еще можете пометить, и если мод согласится, он снова откроется и мигрирует
чокнутый урод
Мы можем перемещать вопросы между сайтами автоматически (даже если они закрыты), пожалуйста, не пересылайте сообщения. Вместо этого следуйте советам @ ratchetfreak, отметьте модерацию и задайте вопрос, который нужно перенести.
Яннис
1
Это звучит очень странно, но что, если вы начнете двигаться вправо, пока не наткнетесь на кусок груза. Как только вы попали в этот груз, бросьте все, что вы несете, подберите этот груз и приступайте к его размещению в нужном месте. Если вы попали в другой кусок груза, который нужно переместить, сбросьте ток, поднимите его и разберитесь с ним. Когда у вас нет груза, двигайтесь направо.
supersam654
1
Существуют ли объекты во всех точках или только в заданных? Возможно ли иметь несколько объектов в данном месте? Допустимо ли временно размещать объект в месте, отличном от его последнего?
Шон МакSomething

Ответы:

4
  1. Если вы пусты, начните движение вправо.

  2. Всякий раз, когда вы достигаете предмета и становитесь пустым, поднимите его (дух) и двигайтесь к месту назначения.

  3. Всякий раз, когда вы достигаете объекта aи уже несете его b, всегда выбирайте, какой из объектов имеет наименьшее по численности место назначения (крайнее слева).

  4. Если вы еще не в М, вернитесь к шагу 1.

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

Почему этот вопрос на programmers.sx? Да, «вопрос интервью», но это просто приятная загадка.

PS. С точки зрения реализации все, что вам нужно, это список задач (целочисленные пары точек), отсортированный по исходной позиции.

Alexis
источник
1

Предположим, вам даны эти шаги, (a, b), (c, d), (e, f), ...тогда минимальное расстояние, которое вам нужно пройти, abs(b - a) + abs(d - c) + abs(f - e) + ...и фактическое расстояние, которое вы путешествуете abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ....
По сути, учитывая массив перемещений, задача состоит в том, чтобы минимизировать функцию «расстояние перемещения», меняя местами элементы. Если вы рассматриваете конкретную комбинацию как узел, а все комбинации, которые вы можете получить из нее, как ребра, вы можете использовать один из многих алгоритмов поиска по графу, которые используют эвристику. Одним из примеров является поиск луча .

Черный медведь
источник
0

Может быть, я неправильно понимаю проблему, но как насчет следующего:

  1. Сортировать пары по первому номеру пары, которая является текущим местоположением
  2. Перемещайтесь вдоль линии, меняя элементы в их правильное положение (у вас есть временная переменная)

Тот факт, что он отсортирован, гарантирует, что вы не будете перемещаться назад и вперед по элементам, чтобы разместить их в нужном месте (независимо от того, представлена ​​ли строка в виде массива или списка)

Обновление после комментария @templatetypedef:
используйте a, HashTableчтобы сохранить все пары. Используйте текущее местоположение каждой пары в качестве ключа индекса.
Используйте второй индекс по парам.

 1. Get next pair according to index from the line.
 2. If current pair exists in hashtable then place element to its target location.  
    2.a Remove pair from hashtable.  
    2.b Make current pair the target location. Then go to step 1  
 ELSE 
        Increment current index until you get a pair present in the hashtable. Go to step 2  
user10326
источник
Вы можете перемещать только одну единицу за раз, поэтому я думаю, что столько раз вам приходилось пересматривать свой путь
Дэвид
Я на самом деле не следую за вами. Кажется, что нужно просто двигаться вперед и менять номера. Вы уже знаете текущее местоположение и целевое местоположение. Просто поменяйте их местами (используя переменную cart, как вы говорите) и перейдите к следующая пара
user10326
Рассмотрим этот контрпример: (1, 10), (10, 1), (2, 3), (3, 4). Оптимальный способ сделать это - перенести объект 1 в положение 10, затем взять объект в положение 10 и перенести его в положение 1, а затем перенести 2 в 3 и 3 в 4. Делать это в отсортированном виде. Порядок стартовой позиции будет нести 1 к 10, затем обратно до самого начала, чтобы нести 2 к 3, 3 к 4, а затем пройти весь путь до конца, чтобы взять 10 и принести его обратно.
templatetypedef
@templatetypedef: я понимаю, что вы имеете в виду. Обновленный ответ
user10326
В вашем обновленном ответе «текущий индекс» просто указывает текущую позицию?
Дэвид
0

Моя склонность к алгоритму, который в основном жадный:

Составьте список точек, которые необходимо переместить. Поскольку оптимизация не является частью требуемой проблемы, я не буду беспокоиться об ее организации.

while !Done
    if CartIsEmpty()
        FindClosestObjectToMove()
        MoveToObject()
       LoadCart()
    else
        Destination = Cart.Contains.Target
        CurrentMove = [Location, Destination]
        SubList = List.Where(Move.Within(CurrentMove))
        if !SubList.Empty
            Destination = SubList.FindSmallest(Location, Move.Origin)
        MoveTo(Destination)
        if !Destination.Empty
            SwapCart()
            UpdateTaskList()
        else
            EmptyCart()
            DeleteTask()

Я думаю, что это охватывает все случаи. В некотором смысле это рекурсивно, но путем обновления списка, а не вызова самого себя.

Лорен Печтель
источник
Спасибо за ответ. Вы можете объяснить Destination = SubList.FindSmallest(Location, Move.Origin)? Что Move.Originпредставляет?
Дэвид
Move.Origin - это место, где находится объект, который нужно переместить в данный момент - это его источник. По сути, когда вы смотрите на движение, сначала делайте любые меньшие движения, содержащиеся в его промежутке.
Лорен Печтел
-1

Это проблема асимметричного коммивояжера . Вы можете думать об этом как о графике. Ребра будут каждой парой (начало, конец), по одной на каждую (0, начало) и все остальные пары (конец, начало).

Предполагая, что NP! = P, он будет иметь экспоненциальное ожидаемое время работы.

MSN
источник
3
Я не уверен, что это правда. Это особый случай асимметричного TSP, поэтому он может иметь решение за полиномиальное время.
templatetypedef
Вам не нужны такие ребра, как (отделка, M), где Mнаходится конечная точка числовой линии?
Дэвид
Кроме того, экспоненциальный алгоритм слишком медленный, потому что Nможет быть 100 000.
Дэвид
Чтобы подтвердить это утверждение, возможно, у вас есть метод преобразования каждой асимметричной задачи коммивояжера в эквивалентную задачу этого описания?
dan_waterworth
1
Это не эквивалентно. Торговый продавец должен посетить все вершины графа. Ваша формулировка требует, чтобы он / она посетил все края.
Алексис