Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.142.173.166] |
|
Страницы: (3) [1] 2 3 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Есть такая задачка. В нулевой момент времени станку ОДНОВРЕМЕННО поставляют N заданий. Станок может в любой момент времени выполнять только одно задание (задание нельзя прервать, т е, если он начал им заниматься, то пока не закончит, к др.заданию переходить не может). На выполнение каждого задания станку требуется T времени (в часах). Также каждое задание имеет характеристику C (у.е.) - сумма штрафа, взимаемая за каждый час ожидания начала исполнения. Нужно найти такой порядок исполнения заданий, чтобы итоговая сумма штрафов по всем заданиям оказалась минимальной. Получить эту мин.сумму штрафа, а также порядок исполнения заданий станком. ------------------------------------------- На рис.показал пример + результаты работы. Прикреплённая картинка
Я хотел как бы узнать про алгоритм) Мне казалось, что нужно подавать станку задания, имеющие макс.штраф - оказалось не так. Строить граф (вершины - задания), причем полный, т к станок может от любого задания перейти в любое другое. А дальше, что и непонятно. Сортировать задания по полям "Время выполнения" или "штраф", ну, ок, а что потом. Получить какую-то целевую "функцию" по типу f(T, C), которая говорит, мол бери это задание следующим... Или это NP-полная задача, т е нужен ПОЛНЫЙ перебор ВСЕХ возможных вариантов?? Кстати, кол-во заданий может быть велико (под 1 000). Подскажите как быть-то? |
Сообщ.
#2
,
|
|
|
Открыть книгу про теорию игр и прочитать.
|
Сообщ.
#3
,
|
|
|
В задачу не вникал, но похоже, что можно применить динамическое программирование.
|
Сообщ.
#4
,
|
|
|
Тыща заданий разом - это, конечно, мрак. А каково количество возможных значений времени выполнения и штрафа? Если количество возможных комбинаций невелико, то можно построить список отношений (время_выплнения, штраф, количество_заданий, задания[]) и дальше уже колдовать над этим списком.
|
Сообщ.
#5
,
|
|
|
Цитата prografix @ В задачу не вникал, но похоже, что можно применить динамическое программирование. думал об этом, но это не отменяет того, что нужен алгоритм) а лучше вникни, т к там все достаточно просто + великолепная поясняющая картинка есть Цитата AVA12 @ Тыща заданий разом - это, конечно, мрак ну, это как бы ПРЕДЕЛЬНОЕ значение, а так подаваться будет штучек по 20 )) Если количество заданий N очень сильно влияет на АЛГОРИТМ, то давай ограничим N <= 100. Цитата AVA12 @ А каково количество возможных значений времени выполнения и штрафа? тебя интересует, чему равняется T(max), C(max)? В условии об этом не сказано. ну, какое-то разумное значение. Ну, давай сделаем T(max) <= 20, C(max) <= 10. Ну, это число из логики какой-то. Добавлено AVA12, т е задача НЕТРИВИАЛЬНАЯ, да? мне даже подумалось, что здесь что-то совсем простое, просто я слишком слаб в алгоритмике, что не вижу элементарное решение... |
Сообщ.
#6
,
|
|
|
Кажется, я что-то нащупал.
С одной стороны, нужно выполнять задания в порядке |
Сообщ.
#7
,
|
|
|
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, то их можно выполнять В ЛЮБОМ порядке? |
Сообщ.
#8
,
|
|
|
Цитата Станку В ЛЮБОМ случае для выполнения всех заданий потребуется времени 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, так что смотри сам. |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ Или это NP-полная задача, т е нужен ПОЛНЫЙ перебор ВСЕХ возможных вариантов?? Однозначно она. Причём перебор с удачной сортировкой на равномерных данных должен дать наибольшее количество отбрасываемых вариантов и. соответственно, более быструю сходимость. Что до "удачной сортировки"... Задания с максимальным удельным штрафом и с минимальным временем выполнения желательно ставить в начало перебора, так что я бы ратовал за, в первом приближении, сортировку по (штраф/время) по убыванию, наверное. |
Сообщ.
#10
,
|
|
|
Akina, т е способ предложенный AVA12, не совсем точен?
ведь в его варианте нет никакого перебора или я что-то не понимаю относительно этих переборов... Добавлено Цитата Akina @ Причём перебор с удачной сортировкой на равномерных а зачем что-то сортировать, если и так будут всевозможные переборы вариантов? совсем я запутался... |
Сообщ.
#11
,
|
|
|
Цитата FasterHarder @ т е способ предложенный AVA12, не совсем точен? ведь в его варианте нет никакого перебора или я что-то не понимаю относительно этих переборов... Да есть у него всё. Цитата FasterHarder @ а зачем что-то сортировать, если и так будут всевозможные переборы вариантов? Затем, что полный перебор - штука долгая. И не исключено, что ты можешь прервать процесс в середине, если текущее решение тебя в принципе устраивает. А при сортировке вероятность "хороших решений" выскочить раньше - выше. Нет, если нужен абсолютный минимум, то и вправду пофиг на сортировку. |
Сообщ.
#12
,
|
|
|
Цитата Akina @ Да есть у него всё. ок, значит я не до конца понимаю, что такое переборы всех возможных вариантов мне казалось, что {a, b, c} --> {abc, acb, bac, aca, cab, cba}, в его алгоритме вообще переборов вроде НЕТ , ну не знаю... Цитата Akina @ Затем, что полный перебор - штука долгая. И не исключено, что ты можешь прервать процесс в середине, если текущее решение тебя в принципе устраивает. это я тоже не понимаю если для получения ТОЧНОГО ДЕТЕРМИНИРОВАННОГО результата требуется перебрать ВСЕ ВОЗМОЖНЫЕ варианты, то как я могу что-то прервать в середине обработки.. + я вообще не выкупаю, какая связь между ПЕРЕБОРОМ ВСЕХ ВАРИАНТОВ и сортировкой...когда перебираем все, то сортировка ведь совсем не нужна, ну не знаю...не знаю...всякое, конечное, бывает...не знаю... кстати, но одном из форумов дали еще один алгоритм решения, думал там ошибка, но тот ответ заплюсовали, ведать тоже так можно, не знаю... |
Сообщ.
#13
,
|
|
|
Цитата FasterHarder @ Потому что он дал тебе приближённый алгоритм с эмпирическим правилом сортировки. Да, на большинстве данных он даёт оптимальный или близкий к оптимальному результат, но оптимальность его в общем случае не очевидна (а может быть, полученная последовательность и не обязательно оптимальна).мне казалось, что {a, b, c} --> {abc, acb, bac, aca, cab, cba}, в его алгоритме вообще переборов вроде НЕТ Хотя, сдаётся мне, можно доказать локальную оптимальность такой сортировки относительно обменов подпоследовательностей (типа abc...de...fgh<->abe...fc...dgh). А в таком случае может оказаться, что это простое правило даёт оптимальное решение. |
Сообщ.
#14
,
|
|
|
Цитата amk @ (а может быть, полученная последовательность и не обязательно оптимальна). а добиться оптимальности можно лишь полным перебором Цитата Akina @ Однозначно она. самое страшное, что решил еще одну задачку, которая имеет ТАКУЮ ЖЕ СЛОЖНОСТЬ, как эту, примерно за 4-7 мин. (построив мат.модель) и там все прекрасно здесь что-то непонятное происходит..ну не знаю, конечно, всякое бывает... в др.алгоритме (здесь его никто не приводил) работают ЧЕРЕЗ произведения, отбирая нужное задание из оставшихся.... |
Сообщ.
#15
,
|
|
|
Вроде бы нашел интересное решение
Назову его путем "сортировки взвешенных коэффициентов". Предпосылка простая - каждая работа вносит определенный вклад в общий штраф, когда выполняется, и вносит вклад в общее время выполнения. Если как-то соотнести эти "вклады" - можно "взвесить" эти коэффициенты. Соответственно, работы с большими коэффициентами влияния желательно расположить раньше работ с меньшими. Такова была моя гипотеза. И я решил провести ее проверку. Для этого написал несложную программу. Суть которой - создание тестов на случайных данных и их оценка моей методикой и полным перебором. Ну и сравнение, какой суммарный штраф получается путем сортировки взвешенных коэффициентов, и что нам дает точный полный перебор. Вот программа: Скрытый текст #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; } К сообщению прикрепил вывод программы из трех последовательных запусков. Результаты прекрасные, ящетаю! Но есть и ложка "дегтя" ... сами понимаете - алгоритм получен эмпирическим путем, поэтому может быть неточен. И это тоже я проверил. В одном из тестов полный перебор дал минимальный штраф 47 единиц (при мах=540), а мой алгоритм на коэффициентах дал 48. Но это было примерно в одном 1 из 20 запусков. Запускал и проверял руками вывод. Может повезло. И тем не менее! Если "взвешенные коэффициенты" на любых вменяемых диапазонах значений дают такой результат, то на количестве работ 1000 моей методике пока равных нет, пока не найдена лучшая. Для сравнения: полный перебор дает N! вариантов расчета суммарного штрафа, а мой алгоритм N*(N-1) расчета коэффициентов + 1 расчет суммарного штрафа. Что такое 1000! дело понятное. В общем, смотрите, экспериментируйте, критикуйте. Возможно где-то чё-то не так. Прикреплённый файлres.7z (72,56 Кбайт, скачиваний: 728) |