Какой самый коварный способ поставить эту проблему? - PullRequest
Новая
       12

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

7 голосов
/ 13 марта 2009

Мой лучший снимок:

Средство доставки должно выполнить серию доставок (d 1 , d 2 , ... d n ) и может сделать это в любой порядок - другими словами, все возможные перестановки множества D = {d 1 , d 2 , ... d n } действительны решения - но конкретное решение должно быть определено до того, как оно покинет базовую станцию ​​на одном конце маршрута (например, представьте, что пакеты должны быть загружены в LIFO транспортного средства).

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

С учетом набора доставок D представлено как расстояние от базовой станции (поэтому abs(d i -d j ) - это расстояние между двумя поставками ) и итератор 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.

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

Ответы [ 6 ]

6 голосов
/ 13 марта 2009

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

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

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

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

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

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

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

Я бы сказал так:

дан список всего возможного перестановки n мест доставки, где каждая перестановка поставок (д 1 , д 2 , ..., d n ) имеет стоимость, определенную как:

image

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

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

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

2 голосов
/ 13 марта 2009

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

Разрешено ли d i быть отрицательным? Если да, то, насколько я вижу, одной сортировки недостаточно.

Например:

d 0 = 0

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

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

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

1 голос
/ 22 марта 2009

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

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

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

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

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

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

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

1 голос
/ 18 марта 2009

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

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

Convination: 

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

Стоимость сцены: 

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

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

0 голосов
/ 23 марта 2009

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

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

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

0 голосов
/ 13 марта 2009

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

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

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

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

...