Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 523
Записей в блоге: 1
#1

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

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

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

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

Вопрос в том, правилен ли второй способ(или я что-то упустил)?
И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2013, 21:53     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)
Посмотрите здесь:

Разработать программную систему для имитации процесса обслуживания заданий в вычислительных системах - C++
Для вычислительной системы (ВС) с одним процессором и мультипрограммным режимом выполнения поступающих заданий требуется разработать...

Нужно написать программу для составления расписания - C++
всем привет) нужно сделать программу для составления расписания в универе, к примеру для одной - двух групп на неделю, и все это потом...

Посоветуйте программу для составления блок схем по коду программы. - C++
Здравствуйте, подскажите пожалуйста кто работал с такими программами. Я лично пользовался Code Visual to Flowchart (программа хорошая, но...

Разработать шаблон класса для реализации односвязного списка - C++
Помогите пожалуйста разработать шаблон класса для реализации односвязного списка.

Необходимо разработать программу, в которой выполняется ввод списка записей определенного типа, а затем - обработка списка. - C++
Необходимо разработать программу, в которой выполняется ввод списка записей определенного типа, а затем - обработка списка. Сначала в...

Разработать шаблон класса для работы со стеком реализованным в виде связного списка - C++
Разработать шаблон класса для работы со стеком реализованным в виде связного списка. Тип эле-ментов задается как параметр шаблона. Написать...

Необходимо разработать программу, в которой выполняется ввод списка записей определенного типа, а затем - обработка списка. Сначала в программе должен - C++
Вывести на экран все записи товаров, определенного ценового диапазона. Ценовой диапазон указывается пользователем. ТОВАР: наименование...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:18     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #2
Цитата Сообщение от DaskOFF Посмотреть сообщение
Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.
Хм... Вот если такая ситуация (я не совсем понял про перестановки, поэтому если что, то пиши): 2 процессор занят, освободится через 10 единиц времени (ЕВ). Третий процессор освободится через 2 ЕВ, а первый - только что освободился. Запускаем на первом процесс, длинной 100500 ЕВ (это последний процесс, который надо запустить), но на 3 процессоре он бы выполнился за 100 ЕВ, что значит, что лучше было бы подождать до освобождения третьего, и загрузить его.
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 523
Записей в блоге: 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} и т.д.
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:29     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #4
DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 523
Записей в блоге: 1
23.07.2013, 22:39  [ТС]     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #5
Цитата Сообщение от Dani Посмотреть сообщение
DaskOFF, я в курсе, просто не совсем понял, как ты собираешься их юзать. А... одинаковое время...
ну как, получаю перестановку и в этом порядке добавляю задачи на первый освобождающийся процессор
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:41     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #6
Это в первом случае, а я про второй. Какие ограничения на кол-во процессов? 14?
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 523
Записей в блоге: 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 я не знаю, а если узнаю не факт, что это будет быстро, хотя и быстрее, чем порождать все перестановки
Kukurudza
105 / 86 / 6
Регистрация: 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
вроде не ошибся. тут скорее всего это не оптимально будет с точки зрения распределения (типа можно сбалансировать чуть чуть лучше)
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
24.07.2013, 07:08     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #9
ваша задача максимизировать количество таких моментов ti, что все процессоры включены в работу. проще говоря, нужно так составить процессы, чтобы максимально долгое время процессоры работали одновременно.
для этого достаточно разбить процессы на три группы таким образом, чтобы суммарное время их выполнения в каждой группе было как можно более "одинаковым". понятно, почему так: при таком варианте расписания процессоры и будут задействованы одновременно наибольшее количество времени.
то есть ваша задача: посчитать, можно ли набор t[] разбить на три группы с максимально похожими суммами. это требует O(N2), решается динамикой. N - количество процессов.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 07:16     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #10
Цитата Сообщение от salam Посмотреть сообщение
это требует O(N2), решается динамикой.
вы уверены в том что нельзя быстрее?
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.07.2013, 07:56     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
ваша задача это в точности известная задача о разбиении (о куче камней), в которой известно количество камней и их веса. Требуется распределить камни по n кучам так, чтобы вес самой тяжелой кучи был минимальным.
Посмотрите книгу

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

эта задача из темы экстремальных задач на графах.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
24.07.2013, 13:08     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #12
Цитата Сообщение от Kukurudza Посмотреть сообщение
вы уверены в том что нельзя быстрее?
я дал грубую оценку. сейчас попробую точнее определить сложность решения, которое я подразумевал.
другого, более быстрого, решения этой задачи лично я не вижу. не могу отрицать, что оно существует. но вариант "отсортировать и попорядку..." точно не полностью корректный.

Добавлено через 16 минут
Цитата Сообщение от Thinker Посмотреть сообщение
Романовский И.В. Алгоритмы решения экстремальных задач. (страница 247)
эта задача из темы экстремальных задач на графах.
я быстро закрыл эту книгу... скажите, пожалуйста, какая оценка у решения из книги?
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
24.07.2013, 13:12     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #13
Thinker, что значит "экстремальные задачи"? np-полные?
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
24.07.2013, 13:29     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #14
Цитата Сообщение от Kukurudza Посмотреть сообщение
вы уверены в том что нельзя быстрее?
в общем получается что-то вроде O(N * SumT), где N - количество процессов, SumT - суммарное время их выполнения. в масштабах этой задачи время маленькое.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
24.07.2013, 13:37     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #15
Цитата Сообщение от salam Посмотреть сообщение
O(N * SumT)
а что тут делает SumT?
а можно алгоритм увидеть?

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

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

NP-сложные задачи несколько иные.
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
24.07.2013, 15:18     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #17
Цитата Сообщение от Thinker Посмотреть сообщение
NP-сложные задачи несколько иные.
это я курсе Мало ли кто-то доказал, что p = np
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 523
Записей в блоге: 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;
}
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.07.2013, 19:43     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #19
Цитата Сообщение от Dani Посмотреть сообщение
это я курсе Мало ли кто-то доказал, что p = np

Не по теме:

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

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2013, 20:15     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)
Еще ссылки по теме:

Проверка, пуст ли список, очистка списка, печать списка в направлении от верха к низу - C++
Доброго вечера. Пожалуйста помогите разобраться с заданием на структуры, и подскажите с чего здесь начинать? 1) Кольцевой...

разработать программу для сортировки массивов - C++
1. создать две матрицы 3х3 и организовать их добавления 2. создать две матрицы 2х3 и 3х2 и организовать их умножения 3. создать матрицу...

Разработать программу для обработки данных - C++
Разработать программу для обработки данных во время ввода, которая вычисляет остатки от деления текущего члена последовательности на...

Разработать программу предназнченную для зашифровки текстов - C++
Разработать программу предназнченную для зашифровки текстов. Вывести на экран исходный текст и результат шифровки. Добавлено через 3...

Разработать программу для ведения базы данных - C++
Разработать программу для ведения базы данных, организованной на файлах. Программа должна использовать конфигурационный файл (текстовый) и...


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

Или воспользуйтесь поиском по форуму:
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 523
Записей в блоге: 1
25.07.2013, 20:15  [ТС]     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #20
Up
может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач?
Yandex
Объявления
25.07.2013, 20:15     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)
Ответ Создать тему
Опции темы

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