На главную Наши проекты:
Журнал   ·   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  все  ( Перейти к последнему сообщению )  
> Станок выполняет задания со штрафом ожидания. Найти минимальный штраф
    Всем хай! Сходу к делу!

    Есть такая задачка.
    В нулевой момент времени станку ОДНОВРЕМЕННО поставляют N заданий. Станок может в любой момент времени выполнять только одно задание (задание нельзя прервать, т е, если он начал им заниматься, то пока не закончит, к др.заданию переходить не может). На выполнение каждого задания станку требуется T времени (в часах). Также каждое задание имеет характеристику C (у.е.) - сумма штрафа, взимаемая за каждый час ожидания начала исполнения.
    Нужно найти такой порядок исполнения заданий, чтобы итоговая сумма штрафов по всем заданиям оказалась минимальной. Получить эту мин.сумму штрафа, а также порядок исполнения заданий станком.

    -------------------------------------------
    На рис.показал пример + результаты работы.
    Прикреплённая картинка
    Прикреплённая картинка


    Я хотел как бы узнать про алгоритм)
    Мне казалось, что нужно подавать станку задания, имеющие макс.штраф - оказалось не так.
    Строить граф (вершины - задания), причем полный, т к станок может от любого задания перейти в любое другое. А дальше, что и непонятно.
    Сортировать задания по полям "Время выполнения" или "штраф", ну, ок, а что потом.
    Получить какую-то целевую "функцию" по типу f(T, C), которая говорит, мол бери это задание следующим...

    Или это NP-полная задача, т е нужен ПОЛНЫЙ перебор ВСЕХ возможных вариантов??
    Кстати, кол-во заданий может быть велико (под 1 000).

    Подскажите как быть-то?
      Открыть книгу про теорию игр и прочитать.
        В задачу не вникал, но похоже, что можно применить динамическое программирование.
          Тыща заданий разом - это, конечно, мрак. А каково количество возможных значений времени выполнения и штрафа? Если количество возможных комбинаций невелико, то можно построить список отношений (время_выплнения, штраф, количество_заданий, задания[]) и дальше уже колдовать над этим списком.
            Цитата prografix @
            В задачу не вникал, но похоже, что можно применить динамическое программирование.

            думал об этом, но это не отменяет того, что нужен алгоритм)
            а лучше вникни, т к там все достаточно просто + великолепная поясняющая картинка есть

            Цитата AVA12 @
            Тыща заданий разом - это, конечно, мрак

            ну, это как бы ПРЕДЕЛЬНОЕ значение, а так подаваться будет штучек по 20 ))
            Если количество заданий N очень сильно влияет на АЛГОРИТМ, то давай ограничим N <= 100.

            Цитата AVA12 @
            А каково количество возможных значений времени выполнения и штрафа?

            тебя интересует, чему равняется T(max), C(max)? В условии об этом не сказано. ну, какое-то разумное значение. Ну, давай сделаем T(max) <= 20, C(max) <= 10. Ну, это число из логики какой-то.

            Добавлено
            AVA12, т е задача НЕТРИВИАЛЬНАЯ, да?
            мне даже подумалось, что здесь что-то совсем простое, просто я слишком слаб в алгоритмике, что не вижу элементарное решение...
              Кажется, я что-то нащупал.
              С одной стороны, нужно выполнять задания в порядке убывания возрастания времени выполнения, чтобы простой был минимальным. С другой стороны, нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало. Объединяем оба требования, для каждой задачи вычисляем отношение штраф/время и сортируем их в порядке убывания этого отношения. Получается, вроде бы, неплохо.
              Сообщение отредактировано: AVA12 -
                AVA12, да, круто у тебя, конечно, получилось! ;) а главное, что так просто: отношение + отсортированный массив.

                но вот кое-что еще.
                Цитата AVA12 @
                нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало

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

                Цитата AVA12 @
                нужно выполнять задания в порядке убывания времени выполнения

                вот тут что-то я на 100% не ухватываю. Станку В ЛЮБОМ случае для выполнения всех заданий потребуется времени T(1) + T(2) + ... + T(N). Какая ему разницы, какое задание выполнять в данный момент времени (на штраф внимания не обращаем сейчас)

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

                вот честно, я вообще не понимаю, почему взял отношение C/T, а не T/C (время/штраф), например.

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

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

                P.S. был уверен на 90%, что тут графы замешаны, оказалось - все проще, хотя, это все очень непросто все равно)

                Добавлено
                и еще такой момент: допустим характеристики {T; C} заданий №7 и №28 такие соот-но {4: 8}, {6; 12}, т е у них РАВНЫЕ отношения = 2/1, то их можно выполнять В ЛЮБОМ порядке?
                  Цитата
                  Станку В ЛЮБОМ случае для выполнения всех заданий потребуется времени T(1) + T(2) + ... + T(N). Какая ему разницы, какое задание выполнять в данный момент времени (на штраф внимания не обращаем сейчас)

                  Станку без разницы, а вот для задач с тикающими счетчиками разница есть. Если твой первый пример выполнять в порядке возрастания T, то общий простой задач будет 1 + (1 + 4) = 6 часов. А если в порядке убывания T, то простой будет уже 10 + (10 + 4) = 24 часа.

                  Цитата
                  допустим характеристики {T; C} заданий №7 и №28 такие соот-но {4: 8}, {6; 12}, т е у них РАВНЫЕ отношения = 2/1, то их можно выполнять В ЛЮБОМ порядке?

                  Ну, в одном случае штраф будет 4 * 12, а в другом 6 * 8, так что смотри сам.
                    Цитата FasterHarder @
                    Или это NP-полная задача, т е нужен ПОЛНЫЙ перебор ВСЕХ возможных вариантов??

                    Однозначно она. Причём перебор с удачной сортировкой на равномерных данных должен дать наибольшее количество отбрасываемых вариантов и. соответственно, более быструю сходимость.
                    Что до "удачной сортировки"... Задания с максимальным удельным штрафом и с минимальным временем выполнения желательно ставить в начало перебора, так что я бы ратовал за, в первом приближении, сортировку по (штраф/время) по убыванию, наверное.
                      Akina, т е способ предложенный AVA12, не совсем точен? :no-sad:
                      ведь в его варианте нет никакого перебора или я что-то не понимаю относительно этих переборов...

                      Добавлено
                      Цитата Akina @
                      Причём перебор с удачной сортировкой на равномерных

                      а зачем что-то сортировать, если и так будут всевозможные переборы вариантов? :huh:

                      совсем я запутался...
                        Цитата FasterHarder @
                        т е способ предложенный AVA12, не совсем точен?
                        ведь в его варианте нет никакого перебора или я что-то не понимаю относительно этих переборов...

                        Да есть у него всё.

                        Цитата FasterHarder @
                        а зачем что-то сортировать, если и так будут всевозможные переборы вариантов?

                        Затем, что полный перебор - штука долгая. И не исключено, что ты можешь прервать процесс в середине, если текущее решение тебя в принципе устраивает. А при сортировке вероятность "хороших решений" выскочить раньше - выше.
                        Нет, если нужен абсолютный минимум, то и вправду пофиг на сортировку.
                          Цитата Akina @
                          Да есть у него всё.

                          ок, значит я не до конца понимаю, что такое переборы всех возможных вариантов
                          мне казалось, что {a, b, c} --> {abc, acb, bac, aca, cab, cba}, в его алгоритме вообще переборов вроде НЕТ :D , ну не знаю...

                          Цитата Akina @
                          Затем, что полный перебор - штука долгая. И не исключено, что ты можешь прервать процесс в середине, если текущее решение тебя в принципе устраивает.

                          это я тоже не понимаю
                          если для получения ТОЧНОГО ДЕТЕРМИНИРОВАННОГО результата требуется перебрать ВСЕ ВОЗМОЖНЫЕ варианты, то как я могу что-то прервать в середине обработки..
                          + я вообще не выкупаю, какая связь между ПЕРЕБОРОМ ВСЕХ ВАРИАНТОВ и сортировкой...когда перебираем все, то сортировка ведь совсем не нужна, ну не знаю...не знаю...всякое, конечное, бывает...не знаю...

                          кстати, но одном из форумов дали еще один алгоритм решения, думал там ошибка, но тот ответ заплюсовали, ведать тоже так можно, не знаю...
                          Сообщение отредактировано: FasterHarder -
                            Цитата FasterHarder @
                            мне казалось, что {a, b, c} --> {abc, acb, bac, aca, cab, cba}, в его алгоритме вообще переборов вроде НЕТ
                            Потому что он дал тебе приближённый алгоритм с эмпирическим правилом сортировки. Да, на большинстве данных он даёт оптимальный или близкий к оптимальному результат, но оптимальность его в общем случае не очевидна (а может быть, полученная последовательность и не обязательно оптимальна).

                            Хотя, сдаётся мне, можно доказать локальную оптимальность такой сортировки относительно обменов подпоследовательностей (типа abc...de...fgh<->abe...fc...dgh). А в таком случае может оказаться, что это простое правило даёт оптимальное решение.
                              Цитата amk @
                              (а может быть, полученная последовательность и не обязательно оптимальна).

                              а добиться оптимальности можно лишь полным перебором
                              Цитата Akina @
                              Однозначно она.


                              самое страшное, что решил еще одну задачку, которая имеет ТАКУЮ ЖЕ СЛОЖНОСТЬ, как эту, примерно за 4-7 мин. (построив мат.модель) и там все прекрасно :lol:
                              здесь что-то непонятное происходит..ну не знаю, конечно, всякое бывает...

                              в др.алгоритме (здесь его никто не приводил) работают ЧЕРЕЗ произведения, отбирая нужное задание из оставшихся....
                                Вроде бы нашел интересное решение :)

                                Назову его путем "сортировки взвешенных коэффициентов". Предпосылка простая - каждая работа вносит определенный вклад в общий штраф, когда выполняется, и вносит вклад в общее время выполнения. Если как-то соотнести эти "вклады" - можно "взвесить" эти коэффициенты. Соответственно, работы с большими коэффициентами влияния желательно расположить раньше работ с меньшими. Такова была моя гипотеза. И я решил провести ее проверку. Для этого написал несложную программу. Суть которой - создание тестов на случайных данных и их оценка моей методикой и полным перебором. Ну и сравнение, какой суммарный штраф получается путем сортировки взвешенных коэффициентов, и что нам дает точный полный перебор.

                                Вот программа:

                                Скрытый текст
                                ExpandedWrap disabled
                                  #include <algorithm>
                                  #include <iostream>
                                  #include <iterator>
                                  #include <locale>
                                  #include <string>
                                  #include <vector>
                                  #include <ctime>
                                  #include <map>
                                   
                                  using namespace std;
                                   
                                  struct JobsElement {
                                    unsigned int Num;
                                    unsigned int Duration;
                                    unsigned int Penalty;
                                    JobsElement(unsigned int iNum, unsigned int iDuration, unsigned int iPenalty):
                                      Num(iNum), Duration(iDuration), Penalty(iPenalty) {}
                                    bool operator<(const JobsElement& rhs) const {
                                      return (Num < rhs.Num);
                                    }
                                  };
                                   
                                  typedef vector<JobsElement> JobsType;
                                  typedef map<unsigned int, double> RatioType;
                                   
                                  // Распечатка вектора
                                  void PrintVector(JobsType& iJobs, string iStr, string iEnd) {
                                    if (iStr.length())
                                      cout << iStr << endl;
                                    for (size_t i = 0; i < iJobs.size(); i++) {
                                      cout << iJobs[i].Num << ": {" << iJobs[i].Duration << "," << iJobs[i].Penalty << "}";
                                      cout << ((i < iJobs.size() - 1) ? ", " : "");
                                    }
                                    if (iEnd.length())
                                      cout << " " << iEnd;
                                    cout << endl;
                                  }
                                   
                                  // Вычисление суммарного штрафа для последовательности работ
                                  auto Penalty(JobsType& iJobs) {
                                    int Ret = 0;
                                    for (size_t i = 0; i < iJobs.size(); i++)
                                      for (size_t j = i + 1; j < iJobs.size(); j++)
                                        Ret += iJobs[i].Duration * iJobs[j].Penalty;
                                    return Ret;
                                  }
                                   
                                  // Вычисление "взвешенных" штрафных коэфициентов
                                  auto CountingRatio(JobsType& iJobs) {
                                    RatioType Ratio;
                                    for (unsigned int i = 0; i < iJobs.size(); i++) {
                                      int sum_r = 0;
                                      int sum_j = 0;
                                      for (unsigned int j = 0; j < iJobs.size(); j++) {
                                        if (i != j) {
                                          sum_j += iJobs[j].Duration;
                                          sum_r += iJobs[j].Penalty;
                                        }
                                      }
                                      double k1 = (iJobs[i].Penalty) / (double) sum_r;
                                      double k2 = (iJobs[i].Duration) / (double) sum_j;
                                      Ratio[i] = k1 / (double)k2;
                                    }
                                    JobsType Ret;
                                    std::copy(iJobs.begin(), iJobs.end(), std::back_inserter(Ret));
                                    std::sort(Ret.begin(), Ret.end(), [&](const JobsElement & iA, const JobsElement & iB)->auto {
                                      return !(Ratio[iA.Num] < Ratio[iB.Num]);
                                    });
                                    return Ret;
                                  }
                                   
                                  // Перебор и оценка вариантов
                                  auto CountingBruteforce(JobsType& iJobs) {
                                    vector<pair<unsigned int, JobsType>> Tmp;
                                    do {
                                      int Pen = Penalty(iJobs);
                                      Tmp.push_back({Pen, iJobs});
                                    } while (std::next_permutation(iJobs.begin(), iJobs.end()));
                                    sort(Tmp.begin(), Tmp.end(), [&](const pair<unsigned int, JobsType>& iA, const pair<unsigned int, JobsType>& iB)->auto {
                                      return iA.first < iB.first;
                                    });
                                    for (auto&& i : Tmp)
                                      PrintVector(i.second, "", to_string(i.first));
                                  }
                                   
                                  // Подготовка нового вектора
                                  void PrepareVector(JobsType& iJobs, const size_t iLen) {
                                    iJobs.clear();
                                    for (unsigned int i = 0; i < iLen; i++)
                                      iJobs.push_back(JobsElement(i, 1 + std::rand() % 9, 1 + std::rand() % 9));
                                  }
                                   
                                  // запуск теста
                                  void RunTest(JobsType& iJobs, const size_t iNum) {
                                    PrintVector(iJobs, "Test #" + to_string(iNum) + ":\n------------------------------------------------------", "");
                                    auto Res = CountingRatio(iJobs);
                                    PrintVector(Res, "Result vector:", "");
                                    cout << "Result penalty: " << Penalty(Res) << endl;
                                    CountingBruteforce(iJobs);
                                    cout << endl;
                                  }
                                   
                                  int main() {
                                    std::srand(unsigned(std::time(0)));
                                    // Тест 1: ручное задание параметров и числа работ
                                    JobsType Jobs = {{0, 1, 1}, {1, 2, 3}, {2, 3, 2}};
                                    RunTest(Jobs, 1);
                                    // Тест 2
                                    PrepareVector(Jobs, 4);
                                    RunTest(Jobs, 2);
                                    // Тест 3
                                    PrepareVector(Jobs, 5);
                                    RunTest(Jobs, 3);
                                    // Тест 4
                                    PrepareVector(Jobs, 6);
                                    RunTest(Jobs, 4);
                                    // Тест 5
                                    PrepareVector(Jobs, 7);
                                    RunTest(Jobs, 5);
                                    return 0;
                                  }

                                К сообщению прикрепил вывод программы из трех последовательных запусков. Результаты прекрасные, ящетаю! :lol:

                                Но есть и ложка "дегтя" ... сами понимаете - алгоритм получен эмпирическим путем, поэтому может быть неточен. И это тоже я проверил. В одном из тестов полный перебор дал минимальный штраф 47 единиц (при мах=540), а мой алгоритм на коэффициентах дал 48. Но это было примерно в одном 1 из 20 запусков. Запускал и проверял руками вывод. Может повезло.

                                И тем не менее! Если "взвешенные коэффициенты" на любых вменяемых диапазонах значений дают такой результат, то на количестве работ 1000 моей методике пока равных нет, пока не найдена лучшая. Для сравнения: полный перебор дает N! вариантов расчета суммарного штрафа, а мой алгоритм N*(N-1) расчета коэффициентов + 1 расчет суммарного штрафа. Что такое 1000! дело понятное.

                                В общем, смотрите, экспериментируйте, критикуйте. Возможно где-то чё-то не так.

                                :thanks:

                                Прикреплённый файлПрикреплённый файлres.7z (72,56 Кбайт, скачиваний: 727)
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0527 ]   [ 20 queries used ]   [ Generated: 19.03.24, 09:24 GMT ]