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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
DaskOFF
 Аватар для DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 521
Записей в блоге: 1
23.07.2013, 21:53     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #1
Есть задачка:
Разработать программу для составления списка заданий для параллельных процессоров. Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения(т.е. задания не могут прерываться или разделяться между процессорами). При 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++ Необходимо разработать программу, в которой выполняется ввод списка записей определенного типа, а затем - обработка списка.
C++ Нужно написать программу для составления расписания
C++ разработать программу для работы со строками
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
25.07.2013, 20:18     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #21
Цитата Сообщение от DaskOFF Посмотреть сообщение
может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач?
почитайте о динамическом программировании. до конца жизни будет, чем заняться...)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DaskOFF
 Аватар для DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 521
Записей в блоге: 1
25.07.2013, 21:18  [ТС]     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #22
Цитата Сообщение от salam Посмотреть сообщение
почитайте о динамическом программировании. до конца жизни будет, чем заняться...)
ну я приметил книгу, которую тут посоветовали ранее (Стивен Скиена. Алгоритмы.) Хороший выбор? Я только 1 курс закончил, но очень переживаю за свое будущее т.к. подобные алгоритмы мне пока даются не очень легко
Я ее пока просто полистал, а прочитал только "Задача о разбиении", но как я понял мне надо разбивать и переставлять, т.к. упорядоченное разбиение мне ничего толком не даст
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
25.07.2013, 21:56     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #23
Цитата Сообщение от DaskOFF Посмотреть сообщение
т.к. подобные алгоритмы мне пока даются не очень легко
чтобы понять такие алгоритмы нужно прорешать задач 100. Они (кого я знаю лично) никому легко не давались. Не парься.
DaskOFF
 Аватар для DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 521
Записей в блоге: 1
18.08.2013, 19:22  [ТС]     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #24
Цитата Сообщение от Thinker Посмотреть сообщение
В книге
Стивен Скиена. Алгоритмы.
эта задача в главе "Динамическое программирование"
Задача разбиения ?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.08.2013, 13:22     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #25
Цитата Сообщение от DaskOFF Посмотреть сообщение
Задача разбиения ?
да, разбиение
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2013, 02:25     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
DaskOFF
 Аватар для DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 521
Записей в блоге: 1
28.08.2013, 02:25  [ТС]     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров) #26
Задачу вроде решил, помогите с контр примерами, чтобы уж наверняка
Если пройдет тест на контр примерах, то выложу код

Добавлено через 1 час 42 минуты
ну вроде как решил, для 30 задач ответ выдает мгновенно.
Код я еще исправлю и сделаю все аккуратно, кому не сложно посмотрите, а то может есть какие-нибудь ошибки, о которых мне следует знать
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
 
#define NUMBER_PROBLEMS 30
#define NUMBER_PROCESSORS 3
 
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
 
typedef struct {
  int s;  //Свободно
  int z;  //Занято
} processor;
 
processor pr[NUMBER_PROCESSORS];
int formS[NUMBER_PROBLEMS];  //Формируемый вектор разбиений
int bestS[NUMBER_PROBLEMS];  //Лучший вектор
int bestTime = -1;           //Лучшее время
int allTime  = -1;  //Общее время выполнения всех задач на 1 процессоре
int svobTime = -1;  //Свободное время на процессор
int vloj = -1;  //Вложенность рекурсии
int Z[NUMBER_PROBLEMS] = {8, 4, 3, 2, 1, 5, 8, 9, 4, 4, 2, 7, 6, 1, 15, 10, 53, 2, 1, 10, 3, 2, 5, 3, 16, 13, 6, 7, 15, 15}; //Время выполнения заданий
int flag = -1;  //Найдено решение или нет
 
//Функции
void qSort(int *, int, int);    //Быстрая сортировка(по убыванию)
int summ(int *, int);           //Суммирование элементов массива
int work();                     //
int maxVect(int *, int);        //Возвращает максимальный элемент массива
void start();                   //распределяет время выполнения задач по процессорам
 
int main()
{
  setlocale(LC_ALL, "");
  for(int i=0; i<NUMBER_PROBLEMS; i++)
    formS[i]=bestS[i] = -1;
 
  allTime = summ(Z, NUMBER_PROBLEMS);
  svobTime = allTime / 3;
  (allTime % 3 > 0) ? (svobTime++):(svobTime);
  if(maxVect(Z, NUMBER_PROBLEMS) > svobTime) svobTime = maxVect(Z, NUMBER_PROBLEMS);
  qSort(Z, 0, NUMBER_PROBLEMS-1);
  //Вывод отсортированного массива
  for(int i=0; i<NUMBER_PROBLEMS; i++)
    printf("%4d", Z[i]);
  printf("<<<\n");
 
  //Пока не будет найдено решение
  while(work())
    svobTime += 1;
 
  //Выводим лучшее время
  printf("Best Time = %d\n", bestTime);
 
  fflush(stdin);
  getchar();
  return 0;
}
//Определения------------------------------------------------
//Общая
int work()
{
  flag = -1;
 
  razb(0, 0);
  if(flag == 1) return 0;
  return 1;
}
 
//Сумма элементов вектора
int summ(int *array, int size)
{
  int res = 0;
  for(int i=0; i<size; i++)
    res += array[i];
  return res;
}
 
//Макс вектора
int maxVect(int *array, int size)
{
  int max = array[0];
  for(int i=1; i<size; i++)
    if(max < array[i]) max = array[i];
  return max;
}
//Быстрая сортировка
void qSort(int *array, int left, int right)
{
  int x = array[(left+right) / 2],
      size = right;
  do {
    while(array[left] > x) left++;
    while(array[right] < x) right--;
 
    if(left <= right) {
      int tmp = array[left];
      array[left] = array[right];
      array[right] = tmp;
      left++; right--;
    }
  } while(left <= right);
 
  if(right > 0) qSort(array, 0, right);
  if(left < size) qSort(array, left, size);
}
 
//Проверка
int check(int number)
{
  for(int i=0; i<number; i++)
    if(pr[i].s < 0) return 1;
  return 0;
}
 
//Добавление задач в процессор
void start()
{
  for(int i=0; i<NUMBER_PROCESSORS; i++) {
    pr[i].s = svobTime;
    pr[i].z = 0;
  }
 
  int i = 0;
  while(i <= vloj)
  {
    if(formS[i]>-1 && formS[i] < 4){
        pr[formS[i]-1].s -=Z[i];
        pr[formS[i]-1].z +=Z[i];
    }
    i++;
  }
}
 
//Все разбиения
void razb(int i, int p)
{
  vloj = i;
  int b = (NUMBER_PROBLEMS-i+1 > NUMBER_PROCESSORS-p+1) ? 1 : p+1;
 
  int minn = min(p+1, NUMBER_PROCESSORS);
  for(int x=b; x<=minn; x++)
  {
    if(flag == 1) continue;
    formS[i] = x;
    for(int j=i+1;j<NUMBER_PROBLEMS;j++)
        formS[j]=-1;
 
    start();                          //
    if(check(NUMBER_PROCESSORS)){     //
      continue;                       //
    }                                 //
 
    if(i == NUMBER_PROBLEMS-1)
    {
      for(int i=0; i<NUMBER_PROBLEMS; i++)
        printf("%4d", formS[i]);
      printf("\n");
      start();
      if(max(pr[0].z, max(pr[1].z, pr[2].z)) < bestTime) bestTime = max(pr[0].z, max(pr[1].z, pr[2].z));
      for(int i=0; i<NUMBER_PROBLEMS; i++) {
        bestS[i] = formS[i];
        formS[i] = -1;
      }
      flag = 1;
    }
    else
    {
      razb(i+1, max(x, p));
    }
  }
}
Yandex
Объявления
28.08.2013, 02:25     В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)
Ответ Создать тему
Опции темы

Текущее время: 16:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru