В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)

@DaskOFF · Регистрация: 02.05.2012

Студворк — интернет-сервис помощи студентам

Есть задачка:

Разработать программу для составления списка заданий для параллельных процессоров. Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения(т.е. задания не могут прерываться или разделяться между процессорами). При i=1,..,M задание i требует ti времени для его выполнения. Определить оптимальный порядок заданий, т.е. такой, который дает возможность завершить все задания в кратчайшее время.

Я прикинул, и у меня есть 2 способа решения задачи, но 1 долгий, а второй рассматривает не все варианты.
1) Полный перебор перестановок, и вывод только тех последовательностей, время выполнения которых минимально, но допустим при 14 задачах мы имеем 87 178 291 200 вариантов последовательностей и они будут очень долго перебираться.

2) Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.

Вопрос в том, правилен ли второй способ(или я что-то упустил)?
И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)?

@Dani · 23.07.2013, 22:18

Сообщение от DaskOFF

Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.

Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.

@DaskOFF · 23.07.2013, 22:27 **[ТС]**

Сообщение от Dani

Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.

процессоры одинаковые, следовательно, очередная задача выполняется одинаковое время на любом из них

Перестановки. Допустим изначальная последовательность загрузки задач следующая: {1, 2, 3, 4, 5}
вот варианты перестановок(всего их будет 5! = 120) : {1, 2, 3, 5, 4} {1, 2, 5, 3, 4} {1, 2, 5, 4, 3} и т.д.

@Dani · 23.07.2013, 22:29

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

@DaskOFF · 23.07.2013, 22:39 **[ТС]**

Сообщение от Dani

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

ну как, получаю перестановку и в этом порядке добавляю задачи на первый освобождающийся процессор

@Dani · 23.07.2013, 22:41

Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?

@DaskOFF · 23.07.2013, 22:50 **[ТС]**

Сообщение от Dani

Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?

ограничений нет, в том то и дело, заданий может быть 100, именно поэтому я и в растерянности, первый находит все варианты, но очень долго для 100 он несколько лет наверно будет подбирать последовательности.

а по моему варианту если будет (N - порядок задач, а T время их выполнения)
N = {3, 4, 1, 2}
T = {8, 8, 4, 3}
то тут уже получается 2 решения
1 - {3, 4, 1, 2}
2 - {4, 3, 1, 2}

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

@Kukurudza · 24.07.2013, 07:03

все не читал, но вроде как второй вариант более правильный. у меня такая идея (вроде как ваша):
сортируем массив заданий по времени выполнения в порядке убывания. идем по этому массиву и очередное задание кидаем в тот процессор у которого общее время выполнения всех его заданий наименьшее. пример:
4 7 2 5 7 9 2 1 5 6 8 3 2 7 8
9 8 8 7 7 7 6 5 5 4 3 2 2 2 1
первый процессор получил: 9 7 4 3 2
второй процессор получил: 8 7 6 2
третий процессор получил: 8 7 5 2 1
вроде не ошибся. тут скорее всего это не оптимально будет с точки зрения распределения (типа можно сбалансировать чуть чуть лучше)

@salam · 24.07.2013, 07:08

ваша задача максимизировать количество таких моментов t_i, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно.
для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени.
то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N²), решается динамикой. N - количество процессов.

@Kukurudza · 24.07.2013, 07:16

Сообщение от salam

это требует O(N2), решается динамикой.

вы уверены в том что нельзя быстрее?

@Thinker · 24.07.2013, 07:56

ваша задача это в точности известная задача о разбиении (о куче камней), в которой известно количество камней и их веса. Требуется распределить камни по n кучам так, чтобы вес самой тяжелой кучи был минимальным.
Посмотрите книгу

Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)

эта задача из темы экстремальных задач на графах.

@salam · 24.07.2013, 13:08

Сообщение от Kukurudza

вы уверены в том что нельзя быстрее?

я дал грубую оценку. сейчас попробую точнее определить сложность решения, которое я подразумевал.
другого, более быстрого, решения этой задачи лично я не вижу. не могу отрицать, что оно существует. но вариант "отсортировать и попорядку..." точно не полностью корректный.

Добавлено через 16 минут

Сообщение от Thinker

Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)
эта задача из темы экстремальных задач на графах.

я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?

@Dani · 24.07.2013, 13:12

Thinker, что значит "экстремальные задачи"? np-полные?

@salam · 24.07.2013, 13:29

Сообщение от Kukurudza

вы уверены в том что нельзя быстрее?

в общем получается что-то вроде O(N * SumT), где N - количество процессов, SumT - суммарное время их выполнения. в масштабах этой задачи время маленькое.

@Kukurudza · 24.07.2013, 13:37

Сообщение от salam

O(N * SumT)

а что тут делает SumT?
а можно алгоритм увидеть?

Добавлено через 52 секунды
странно просто, если время задач измеряется в секундах то ок, если то же самое только в годах, то что-то не очень

@Thinker · 24.07.2013, 15:03

Сообщение от salam

я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?

пусть имеется n камней (потоков) и m кучек (процессоров). сложность алгоритма $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(mn^2)$ Эта оценка приведена у Стивена Скиена.

Сообщение от Dani

Thinker, что значит "экстремальные задачи"? np-полные?

просто автор так главу назвал. В книге
Стивен Скиена. Алгоритмы.
эта задача в главе "Динамическое программирование"

NP-сложные задачи несколько иные.

@Dani · 24.07.2013, 15:18

Сообщение от Thinker

NP-сложные задачи несколько иные.

это я курсе

Мало ли кто-то доказал, что p = np

@DaskOFF · 24.07.2013, 16:20 **[ТС]**

Спасибо, сейчас почитаю книги, может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач? (про np-полные задачи, прочел на вики, но понял мало)

Сортировка по убыванию и правда не подходит, дали вот такой контрпример, который этот способ не проходит
{10 10 10 10 7 6 6}

Нашел алгоритм, который выполняется ~2 секунды(на моей машине) при 25 задачах, но я не понимаю, как этот алгоритм получен
функция получения следующей последовательности
seq - последовательность задающая порядок задач

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int next(int *seq)
{
  static int t = 1;
  int i = M-2;
  while(i>=0 && seq[i] > seq[i+1])
    i--;
  
  if(i>=0)
  {
    int j = i+1;
    
    while(j<M-1 && seq[j+1] > seq[j])
      j++;
   
    swap(seq+i, seq+j);
   
    for(j=i+1; j<= (M+i-1)/2; j++)
      swap(seq+j, seq+(M-j+i));
  
    return 1;
  }
  else
    return 0;
}

@Thinker · 24.07.2013, 19:43

Сообщение от Dani

это я курсе Мало ли кто-то доказал, что p = np

Не по теме:

ну, да, в 2010 году чуть сенсацией не стала работа индийского математика (выкладываю ссылку, так как сам автор выложил в сеть свою статью)
http://www.win.tue.nl/~gwoegi/... alikar.pdf
ну а в ней нашли прорехи
http://www.open.by/it/33980

теперь непонятно будет ли разрешена эта проблема.

@DaskOFF · 25.07.2013, 20:15 **[ТС]**

Up
может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач?

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	23.07.2013, 22:29
	DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время... 1

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	23.07.2013, 22:41
	Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14? 1

@Kukurudza 106 / 87 / 13 Регистрация: 29.08.2012 Сообщений: 538
	24.07.2013, 07:03
	все не читал, но вроде как второй вариант более правильный. у меня такая идея (вроде как ваша): сортируем массив заданий по времени выполнения в порядке убывания. идем по этому массиву и очередное задание кидаем в тот процессор у которого общее время выполнения всех его заданий наименьшее. пример: 4 7 2 5 7 9 2 1 5 6 8 3 2 7 8 9 8 8 7 7 7 6 5 5 4 3 2 2 2 1 первый процессор получил: 9 7 4 3 2 второй процессор получил: 8 7 6 2 третий процессор получил: 8 7 5 2 1 вроде не ошибся. тут скорее всего это не оптимально будет с точки зрения распределения (типа можно сбалансировать чуть чуть лучше) 1

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	24.07.2013, 07:08
	ваша задача максимизировать количество таких моментов t_i, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно. для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени. то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N²), решается динамикой. N - количество процессов. 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	24.07.2013, 07:56
	Сообщение было отмечено как решение Решение ваша задача это в точности известная задача о разбиении (о куче камней), в которой известно количество камней и их веса. Требуется распределить камни по n кучам так, чтобы вес самой тяжелой кучи был минимальным. Посмотрите книгу Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247) эта задача из темы экстремальных задач на графах. 4

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	24.07.2013, 13:12
	Thinker, что значит "экстремальные задачи"? np-полные? 1

@DaskOFF 113 / 113 / 42 Регистрация: 02.05.2012 Сообщений: 524 Записей в блоге: 1
	25.07.2013, 20:15 [ТС]
	Up может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач? 0

В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)

Решение