На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (3) 1 [2] 3  все  ( Перейти к последнему сообщению )  
> Станок выполняет задания со штрафом ожидания. Найти минимальный штраф
    ADD> В предыдущем моем посте в прикрепленном архиве - текстовые файлы. Которые получаются путем перехвата вывода из STDOUT (типа ./myprog > 1). А смотреть и сравнивать нужно вот это:

    user posted image
      JoeUser, это раздел "Алгоритмы", а не "C++". То, что есть исходник программы - это, конечно, хорошо (возможно даже, удастся его скомпилировать и запустить). Но хотелось бы увидеть описание алгоритма (или формулы).
        Цитата 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, только без последнего длинного теста, ибо онлан-компилятор обрубает по времени исполнения.
          Короче говоря, итоговый коэффициент k[i] = (P[i] / T[i]) * (sum(T) - T[i]) / (sum(P) - P[i]), где P - это штрафы, а T - время выполнения. Не совсем понятно, для чего тут нужны суммы. Все, что они делают - это добавляют нелинейности к итоговым коэффициентам, а поскольку нас интересуют только отношения больше/меньше, эта нелинейность ничего не меняет.
            Цитата AVA12 @
            Не совсем понятно, для чего тут нужны суммы.

            Я уже объяснял вой взгляд ранее - посчитал, что каждый параметр вносит свой вклад в расчеты. А как его (вклад) можно определить? Самое простое - разделить его на сумму остальных и оценить долю. Повторюсь - такой метод расчетов просто получился путем догадок! Никаких точных математических обоснований, никаких прочих формул и правил.
              Что-то ТС молчит как рыба об лед! :lol: У меня еще появились идеи ... только мне одному они ни разу не упали.
                Легко можно показать, что решение локально оптимально, если величина 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.
                Сообщение отредактировано: amk -
                  Цитата amk @
                  А правильный ответ почти сразу дал AVA12

                  Прошу его еще раз процитировать/уточнить, чтобы провести замеры.
                    Держи
                    Цитата AVA12 @
                    Кажется, я что-то нащупал.
                    С одной стороны, нужно выполнять задания в порядке убывания возрастания времени выполнения, чтобы простой был минимальным. С другой стороны, нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало. Объединяем оба требования, для каждой задачи вычисляем отношение штраф/время и сортируем их в порядке убывания этого отношения. Получается, вроде бы, неплохо.

                    Ну и конкретно, на что обратить внимание
                    Цитата AVA12 @
                    вычисляем отношение штраф/время
                    Цитата AVA12 @
                    сортируем их в порядке убывания этого отношения

                    Я предложил то же самое отношение, только делил время на штраф, и соответственно, сортировал по возрастанию. У меня в спойлере это отношение даже выводится. Специально потратил десяток минут.
                    Сообщение отредактировано: amk -
                      amk, да, я проверил - у меня вариант хуже. Из 1000 рандомных наборов, у меня около 30 неоптимальные (ошибочные).
                        В списке модельных NP-полных задач из старого Гэри, Джонсона такой нет.
                        Задача, скорее всего, полиномиально сводится к коммивояжеру. Но это, конечно, нужно доказать.
                          swf, как уже выяснилось, эта задача сводится к сортировке и имеет сложность O(N log N)
                            Цитата
                            задача сводится к сортировке и имеет сложность O(N log N)

                            Почему именно O(N log N)? Отсортировать можно и за O(N)!
                              Цитата AVA12 @
                              Отсортировать можно и за O(N)!
                              Только в частных случаях, когда на исходные данные накладываются некоторые ограничения.

                              Поразрядная сортировка, кстати, на самом деле тоже не O(N), а O(N log M), где M - разрядность данных.
                                Цитата amk @
                                swf, как уже выяснилось, эта задача сводится к сортировке и имеет сложность O(N log N)

                                А я что-то не поняла. Как доказали, что сортировка даёт оптимальное решение?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) 1 [2] 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0510 ]   [ 16 queries used ]   [ Generated: 19.03.24, 07:26 GMT ]