Задачка для интересу
Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё Elm и Rust, и вообще, потенциально определённая свобода в этом плане. Пишите, когда ещё вам предложат попрограммировать с пользой на чём-то неунылом за деньги
( Read more... )
Это, конечно, убавляет интерес к задаче, но для knapsack problem имеется более-менее эффективное решение с помощью динамического программирования. Можно, например, подумать, можно ли его использовать при произвольном количестве ядер.
Reply
Как мы уже выяснили, задача точно NP-полная, и она точно может решаться полным перебором.
С другой стороны, как мне кажется, у меня получилось её решить с помощью DP. По-крайней мере, я пока не могу найти контрпримеров. Но thesz уверяет, что решение таким образом я могу найти только приблизительное.
Я смутно подозреваю, что он прав (потому что чётко доказать корректность своего решения не могу), и, допускаю, что есть какие-то крайние случаи, где мой вариант может провраться.
С третьей стороны, в плане задачи оценки кандидата, меня устраивает любое разумное решение, в том числе и приблизительный шедулер, и генерация расписания полным перебором. Потому что аккуратно этот перебор запрограммировать, по-моему, уже требует достаточно высокой квалификации :)
Reply
Ради интереса прогони тесты, которые ты нам не показывал, вот на этом решении и сравни ответы со своей DP-реализацией
https://www.dropbox.com/s/lc0obw7jlp5qvjp/task3.tar.gz?dl=0
... это направленный перебор с отсечениями, он гарантированно должен находить лучшие решения для небольших s-exp'ов.
Reply
Reply
У меня там немного совсем дополнительных тестов, и все они пока совпадают с твоими результатами. Надо, наверно, генератор рандомных s-выражений написать, и на них погонять уже. Не хочешь такой спрограммировать? :)
Reply
Я именно это и собирался сделать, но внезапно устал)
Завтра спрограммирую.
Reply
https://www.dropbox.com/s/lpjcs7okrz93h9x/expresso.tar.gz?dl=0
Reply
Ну, как и следовало ожидать, мой вариант, действительно, подвирает на более длинных тестах =) Значит, вы с thesz были правы, и вправду только брутфорсом можно оптимальные расписания получать.
Reply
Reply
Если да, то не во все укладывается :) Например, interpret_cpu(sample_7(), 4) работает 16 секунд, хотя можно 15.
Или вот, пример от thesz:
(+ (+ 1 2) (+ 3 4) (+ 5 6) (+ 6 7) (+ 7 8) (+ 9 10) (+ 11 12) (+ 13 14) (* 1 (* 2 (* 3 4) 5) 6))
Оптимальное расписание там 32 секунды, а у вас получается 34 или 35.
Reply
Reply
Накидал вариант с тупым перебором, правда не всего графа, а только части что можем посчитать.
p:run_tests().
1[2]: 21 (delay 15 sec)
2[2]: 10 (delay 0 sec)
3[2]: -10 (delay 13 sec)
4[2]: 25 (delay 5 sec)
5[2]: 1 (delay 30 sec)
6[2]: 8 (delay 28 sec)
6[3]: 8 (delay 25 sec)
7[2]: 50 (delay 27 sec)
7[3]: 50 (delay 22 sec)
7[4]: 50 (delay 17 sec)
8[2]: 8 (delay 17 sec)
8[3]: 8 (delay 13 sec)
9[2]: 66 (delay 16 sec)
Так себе из меня сварщик ).
Reply
Reply
Leave a comment