Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
1

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

23.07.2013, 21:53. Показов 2647. Ответов 25
Метки нет (Все метки)

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

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

Вопрос в том, правилен ли второй способ(или я что-то упустил)?
И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.07.2013, 21:53
Ответы с готовыми решениями:

Разработать программу для составления списка неуспевающих студентов
Разработать программу для составления списка неуспевающих студентов. Текст документа я написал а...

Разработать программу для составления итоговой ведомости, в которой итоговая оценка по предмету равна средне-арифмитической по трем циклам
Разработать программу для составления итоговой ведомости, в которой итоговая оценка по предмету...

Разработать приложение для автоматизации составления тестов
Разработать приложение для автоматизации составления тестов: Пароль: 123 Помогите пожалуйста...

Разработать программу для сохранения списка покупателей бытовой техники в виде файла
#8 с файлами у меня проблемы, а написать нужно. Помогите, пожалуйста. Правила Форума:...

25
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 22:18 2
Цитата Сообщение от DaskOFF Посмотреть сообщение
Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.
Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.
1
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
23.07.2013, 22:27  [ТС] 3
Цитата Сообщение от 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} и т.д.
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 22:29 4
DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...
1
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
23.07.2013, 22:39  [ТС] 5
Цитата Сообщение от Dani Посмотреть сообщение
DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...
ну как, получаю перестановку и в этом порядке добавляю задачи на первый освобождающийся процессор
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 22:41 6
Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?
1
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
23.07.2013, 22:50  [ТС] 7
Цитата Сообщение от 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 я не знаю, а если узнаю не факт, что это будет быстро, хотя и быстрее, чем порождать все перестановки
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 07:03 8
все не читал, но вроде как второй вариант более правильный. у меня такая идея (вроде как ваша):
сортируем массив заданий по времени выполнения в порядке убывания. идем по этому массиву и очередное задание кидаем в тот процессор у которого общее время выполнения всех его заданий наименьшее. пример:
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
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
24.07.2013, 07:08 9
ваша задача максимизировать количество таких моментов ti, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно.
для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени.
то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N2), решается динамикой. N - количество процессов.
1
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 07:16 10
Цитата Сообщение от salam Посмотреть сообщение
это требует O(N2), решается динамикой.
вы уверены в том что нельзя быстрее?
1
Эксперт С++
4259 / 2233 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.07.2013, 07:56 11
Лучший ответ Сообщение было отмечено как решение

Решение

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

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

эта задача из темы экстремальных задач на графах.
4
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
24.07.2013, 13:08 12
Цитата Сообщение от Kukurudza Посмотреть сообщение
вы уверены в том что нельзя быстрее?
я дал грубую оценку. сейчас попробую точнее определить сложность решения, которое я подразумевал.
другого, более быстрого, решения этой задачи лично я не вижу. не могу отрицать, что оно существует. но вариант "отсортировать и попорядку..." точно не полностью корректный.

Добавлено через 16 минут
Цитата Сообщение от Thinker Посмотреть сообщение
Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)
эта задача из темы экстремальных задач на графах.
я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?
1
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
24.07.2013, 13:12 13
Thinker, что значит "экстремальные задачи"? np-полные?
1
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
24.07.2013, 13:29 14
Цитата Сообщение от Kukurudza Посмотреть сообщение
вы уверены в том что нельзя быстрее?
в общем получается что-то вроде O(N * SumT), где N - количество процессов, SumT - суммарное время их выполнения. в масштабах этой задачи время маленькое.
1
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 13:37 15
Цитата Сообщение от salam Посмотреть сообщение
O(N * SumT)
а что тут делает SumT?
а можно алгоритм увидеть?

Добавлено через 52 секунды
странно просто, если время задач измеряется в секундах то ок, если то же самое только в годах, то что-то не очень
1
Эксперт С++
4259 / 2233 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.07.2013, 15:03 16
Цитата Сообщение от salam Посмотреть сообщение
я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?
пусть имеется n камней (потоков) и m кучек (процессоров). сложность алгоритма https://www.cyberforum.ru/cgi-bin/latex.cgi?O(mn^2) Эта оценка приведена у Стивена Скиена.

Цитата Сообщение от Dani Посмотреть сообщение
Thinker, что значит "экстремальные задачи"? np-полные?
просто автор так главу назвал. В книге
Стивен Скиена. Алгоритмы.
эта задача в главе "Динамическое программирование"

NP-сложные задачи несколько иные.
1
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
24.07.2013, 15:18 17
Цитата Сообщение от Thinker Посмотреть сообщение
NP-сложные задачи несколько иные.
это я курсе Мало ли кто-то доказал, что p = np
1
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
24.07.2013, 16:20  [ТС] 18
Спасибо, сейчас почитаю книги, может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач? (про 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;
}
0
Эксперт С++
4259 / 2233 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.07.2013, 19:43 19
Цитата Сообщение от Dani Посмотреть сообщение
это я курсе Мало ли кто-то доказал, что p = np

Не по теме:

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

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

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

Разработать иерархию не менее 2 классов, и программу Разработать программу для реализации игры пятнашки. Разработать 2-3
Составить описание класса многочленов от одной переменной, задаваемых степенью многочлена и...

Разработать приложение для генерации (проверки) заданий типа А13
Подскажите, как решить это задание? Наиболее интересует используемая таблица. Разработать...

Направьте, пожалуйста, в правильном направлении
На данный момент в Java я нахожусь только на начальном уровне, до Java EE ещё не добрался....

Волшебный пинок в правильном направлении
Помогите разобраться с ошибкой, я учусь пока и мои потуги не смогли решить проблему и что делать я...

Олимпиадные задачки. Натолкните в правильном направлении
Необязательно помогать со всеми(но я был бы вам очень благодарен). Можете помочь с одной или двумя,...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.