Какой самый коварный способ постановки этой проблемы?

StackOverflow https://stackoverflow.com/questions/643594

  •  22-07-2019
  •  | 
  •  

Вопрос

Мой лучший снимок на данный момент:

Транспортное средство доставки должно выполнить серию доставок (d1,d2,...dn), и может делать это в любом порядке - другими словами, все возможные перестановки множества D = {d1,d2,...dn} являются допустимыми решениями, но конкретное решение должно быть определено до того, как оно покинет базовую станцию на одном конце маршрута (представьте, что пакеты необходимо загрузить, например, в LIFO транспортного средства).

Кроме того, стоимость различных перестановок неодинакова.Он может быть вычислен как сумма квадратов расстояния, пройденного между di -1 и di, где d0 принимается за базовую станцию с оговоркой, что любой сегмент, связанный с изменением направления, стоит в 3 раза дороже (представьте, что это происходит на железной дороге или пневматической трубе, и резервное копирование нарушает движение других транспортных средств).

Учитывая набор поставок D представлены как их расстояние от базовой станции (так abs(di-dj) является расстоянием между двумя поставками) и итератором permutations(D) который будет производить каждую перестановку последовательно, найдите перестановку, стоимость которой меньше или равна стоимости любой другой перестановки.

Теперь прямая реализация из этого описания может привести к такому коду, как этот:

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

Который равен O (n*n!^2), напримердовольно ужасно - особенно по сравнению с O (n log (n)), который мог бы найти кто-то с пониманием, просто отсортировав D.

Мой вопрос:можете ли вы придумать правдоподобное описание проблемы, которое, естественно, привело бы неосторожного к хуже (или по-другому ужасная) реализация алгоритма сортировки?

Это было полезно?

Решение

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

[Это предположение неверно - MarkusQ]

Вы даете слишком много информации.

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

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

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

Еще одним важным ключом к разгадке являются входные значения для алгоритма:список целых чисел.Дайте им список перестановок или даже ВСЕ перестановки.Это заставляет их думать, что на самом деле можно ожидать использования алгоритма O (n!).

Я бы сформулировал это так:

Дан список всех возможных перестановок из n мест доставки, где каждая перестановка поставок (d1, d2, ..., dn) имеет стоимость, определяемую:

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

Все, что действительно нужно сделать, - это прочитать первую перестановку и отсортировать ее.

Если они строят один цикл для сравнения затрат, спросите их, каково время выполнения big-o их алгоритма, где n - количество мест доставки (еще одна ловушка).

Другие советы

Это не прямой ответ, но я думаю, что необходимо внести дополнительные уточнения.

Является di разрешено быть негативным?Если это так, то одной сортировки недостаточно, насколько я могу судить.

Например:

d0 = 0

deliveries = (-1,1,1,2)

Кажется, оптимальным путем в этом случае был бы 1 > 2 > 1 > -1.

Редактировать:Возможно, на самом деле это не оптимальный путь, но он иллюстрирует суть дела.

Вы могли бы перефразировать это, сначала найдя оптимальное решение, как

"Приведите мне доказательство того, что следующее решение является наиболее оптимальным для следующего набора правил, где оптимальное означает наименьшее число, полученное из суммы затрат на все этапы, принимая во внимание, что все этапы (A..Z) нужно присутствовать один и только один раз.

Объединение:

A->C->D->Y->P->...->N

Затраты на этап:

A->B = 5,
B->A = 3,
A->C = 2,
C->A = 4,
...
...
...
Y->Z = 7,
Z->Y = 24."

Это должно занять кого-то на некоторое время.

Это напоминает мне о Проблема с рюкзаком, больше, чем Коммивояжер.Но Рюкзак - это также NP-сложная задача, поэтому вы могли бы обмануть людей, заставив их придумать слишком сложное решение с помощью динамического программирования, если они соотнесут вашу проблему с рюкзаком.Где основная проблема заключается в:

можно ли достичь значения по меньшей мере V без превышения веса W?

Теперь проблема заключается в том, что довольно хорошее решение можно найти, когда V уникально, ваши расстояния, как таковые:

Задача о рюкзаке с каждым типом предмета j, имеющего различное значение на единицу веса (vj = pj / wj) считается одной из самых простых NP-полных задач.Действительно эмпирический сложность порядка O ((log n) 2) и очень большие проблемы могут быть решены очень быстро, напримерв 2003 году среднее время, необходимое для решения примеров с n = 10 000, составляло менее 14 миллисекунд при использовании обычных персональных компьютеров1.

Таким образом, вы можете указать, что несколько остановок / пакетов могут использовать один и тот же vj, приглашая людей подумать о действительно сложном решении для:

Однако в вырожденном случае нескольких элементов , имеющих одинаковое значение vj, становится намного сложнее с экстремальным случаем, когда vj = константа, являющаяся задачей о сумме подмножеств со сложностью равной O (2N / 2N).

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

Разве это не просто (NP-Жесткий) Проблема Коммивояжера?Маловероятно, что вы собираетесь сделать это намного сложнее.

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

Как насчет описания вопроса таким образом, чтобы у кого-то возникло искушение выполнить рекурсивные сравнения - например"можете ли вы ускорить алгоритм, используя оптимальное максимальное подмножество ваших лучших (на данный момент) результатов"?

Кстати, какова цель этого - звучит так, будто цель состоит в том, чтобы пытать интервьюируемых.

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

Если вы обманом вынудили кого-то дать плохой ответ (например, не предоставив ему всей информации), то кто стал причиной этого - его глупость или ваш обман?

Насколько велика мудрость мудрых, если они не обращают внимания на ложь своего эго?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top