Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.141.202.54] |
|
Страницы: (3) 1 [2] 3 все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|
|
ADD> В предыдущем моем посте в прикрепленном архиве - текстовые файлы. Которые получаются путем перехвата вывода из STDOUT (типа ./myprog > 1). А смотреть и сравнивать нужно вот это:
|
Сообщ.
#17
,
|
|
|
JoeUser, это раздел "Алгоритмы", а не "C++". То, что есть исходник программы - это, конечно, хорошо (возможно даже, удастся его скомпилировать и запустить). Но хотелось бы увидеть описание алгоритма (или формулы).
|
Сообщ.
#18
,
|
|
|
Цитата AVA12 @ Но хотелось бы увидеть описание алгоритма (или формулы). Хорошо, попробую на пальцах ... Пусть дан список работ. Каждая работа представлена в списке тройкой [порядковый_номер_работы, продолжительность_работы, штраф_за _простой] {{0, 1, 1}, {1, 2, 3}, {2, 3, 2}}; Нам нужно для каждой работы вычислить "взвешенный коэффициент" Работа 0 sum_r = равна сумме всех штрафов, кроме работы №0 (равна 5); sum_j = равна сумме всех продолжительностей работ, кроме работы №0 (равна 5); k1 = промежуточный коэффициент, равный (штраф_работы_№0/sum_r) = 0.2 k2 = промежуточный коэффициент, равный (продолжительность_работы_№0/sum_j) = 0.2 взвешенный коэффициент работы №0 = k1/k2 (равен 1.0) Работа 1 sum_r = равна сумме всех штрафов, кроме работы №1 (равна 3); sum_j = равна сумме всех продолжительностей работ, кроме работы №1 (равна 4); k1 = промежуточный коэффициент, равный (штраф_работы_№1/sum_r) = 1 k2 = промежуточный коэффициент, равный (продолжительность_работы_№1/sum_j) = 0.5 взвешенный коэффициент работы №1 = k1/k2 (равен 2.0) Работа 2 sum_r = равна сумме всех штрафов, кроме работы №2 (равна 4); sum_j = равна сумме всех продолжительностей работ, кроме работы №2 (равна 3); k1 = промежуточный коэффициент, равный (штраф_работы_№2/sum_r) = 0.5 k2 = промежуточный коэффициент, равный (продолжительность_работы_№2/sum_j) = 1 взвешенный коэффициент работы №2 = k1/k2 (равен 0.5) Значит, работы нужно расположить по убыванию их "взвешенных коэффициентов" в порядке: 1-0-2, вот так: {{1, 2, 3}, {0, 1, 1}, {2, 3, 2}} Считаем суммарный штраф: 2*(1+2) +1*(2) = 8 Проверяем перебором все перестановки: {1,2,3}, {0,1,1}, {2,3,2} = 8 {0,1,1}, {1,2,3}, {2,3,2} = 9 {1,2,3}, {2,3,2}, {0,1,1} = 9 {0,1,1}, {2,3,2}, {1,2,3} = 14 {2,3,2}, {1,2,3}, {0,1,1} = 14 {2,3,2}, {0,1,1}, {1,2,3} = 15 Проверка прошла удачно! Найденное значение по взвешенным коэффициентам равно минимальному значению при полном переборе. Бинго. Добавлено Цитата AVA12 @ возможно даже, удастся его скомпилировать и запустить) Да, пожалуйста, https://ideone.com/y0IcNc, только без последнего длинного теста, ибо онлан-компилятор обрубает по времени исполнения. |
Сообщ.
#19
,
|
|
|
Короче говоря, итоговый коэффициент k[i] = (P[i] / T[i]) * (sum(T) - T[i]) / (sum(P) - P[i]), где P - это штрафы, а T - время выполнения. Не совсем понятно, для чего тут нужны суммы. Все, что они делают - это добавляют нелинейности к итоговым коэффициентам, а поскольку нас интересуют только отношения больше/меньше, эта нелинейность ничего не меняет.
|
Сообщ.
#20
,
|
|
|
Цитата AVA12 @ Не совсем понятно, для чего тут нужны суммы. Я уже объяснял вой взгляд ранее - посчитал, что каждый параметр вносит свой вклад в расчеты. А как его (вклад) можно определить? Самое простое - разделить его на сумму остальных и оценить долю. Повторюсь - такой метод расчетов просто получился путем догадок! Никаких точных математических обоснований, никаких прочих формул и правил. |
Сообщ.
#21
,
|
|
|
Что-то ТС молчит как рыба об лед! У меня еще появились идеи ... только мне одному они ни разу не упали.
|
Сообщ.
#22
,
|
|
|
Легко можно показать, что решение локально оптимально, если величина Duration/Cost не убывает.
Скрытый текст Рассмотрим последовательность работ и выделим в ней две соседние работы W[1] ... W[k+1] W[k+2] .... W[N] D[k+1] D[k+2] C[k+1] C[k+2] Как легко заметить штраф за работы выполняемые до них не меняется, если их поменять местами. Так же не меняется штраф за последующие работы. Запишем общий штраф для рассмотренной последовательности и последовательности, в которой эти работы поменяны местами. Ss + Ds*C[k+1] + (Ds + D[k+1])*C[k+2] + Se Ss + Ds*C[k+2] + (Ds + D[k+2])*C[k+1] + Se Раскроем скобки и объединим совпадающие в обоих выражениях слагаемые Ss + Ds*(C[k+1] + C[k+2]) + Se + D[k+1]*C[k+2] = S + D[k+1]*C[k+2] Ss + Ds*(C[k+1] + C[k+2]) + Se + D[k+2]*C[k+1] = S + D[k+2]*C[k+1] Должно выполняться S + D[k+1]*C[k+2] <= S + D[k+2]*C[k+1] D[k+1]*C[k+2] <= D[k+2]*C[k+1] D[k+1]/C[k+1] <= D[k+2]/C[k+2] Добавлено Вообще говоря, поскольку данное соотношение не зависит от места задачи в очереди выполнения локально оптимальное решение должно быть оптимальным и глобально. А потому непонятно, почему у JoeUser'а иногда получаются не самые оптимальные решения. Или он по какому-то другому критерию сортирует? Добавлено Разобрался. Он действительно в качеств отношения использует другое значение и получает неточный результат. А правильный ответ почти сразу дал AVA12. |
Сообщ.
#23
,
|
|
|
Цитата amk @ А правильный ответ почти сразу дал AVA12 Прошу его еще раз процитировать/уточнить, чтобы провести замеры. |
Сообщ.
#24
,
|
|
|
Держи
Цитата AVA12 @ Кажется, я что-то нащупал. С одной стороны, нужно выполнять задания в порядке убывания возрастания времени выполнения, чтобы простой был минимальным. С другой стороны, нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало. Объединяем оба требования, для каждой задачи вычисляем отношение штраф/время и сортируем их в порядке убывания этого отношения. Получается, вроде бы, неплохо. Ну и конкретно, на что обратить внимание Я предложил то же самое отношение, только делил время на штраф, и соответственно, сортировал по возрастанию. У меня в спойлере это отношение даже выводится. Специально потратил десяток минут. |
Сообщ.
#25
,
|
|
|
amk, да, я проверил - у меня вариант хуже. Из 1000 рандомных наборов, у меня около 30 неоптимальные (ошибочные).
|
Сообщ.
#26
,
|
|
|
В списке модельных NP-полных задач из старого Гэри, Джонсона такой нет.
Задача, скорее всего, полиномиально сводится к коммивояжеру. Но это, конечно, нужно доказать. |
Сообщ.
#27
,
|
|
|
swf, как уже выяснилось, эта задача сводится к сортировке и имеет сложность O(N log N)
|
Сообщ.
#28
,
|
|
|
Цитата задача сводится к сортировке и имеет сложность O(N log N) Почему именно O(N log N)? Отсортировать можно и за O(N)! |
Сообщ.
#29
,
|
|
|
Цитата AVA12 @ Только в частных случаях, когда на исходные данные накладываются некоторые ограничения.Отсортировать можно и за O(N)! Поразрядная сортировка, кстати, на самом деле тоже не O(N), а O(N log M), где M - разрядность данных. |
Сообщ.
#30
,
|
|
|
Цитата amk @ swf, как уже выяснилось, эта задача сводится к сортировке и имеет сложность O(N log N) А я что-то не поняла. Как доказали, что сортировка даёт оптимальное решение? |