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

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

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

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

23.07.2013, 21:53. Просмотров 1758. Ответов 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++
всем привет) нужно сделать программу для составления расписания в универе, к примеру для одной - двух групп на неделю, и все это потом...

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Thinker
Эксперт C++
4225 / 2199 / 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
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
24.07.2013, 15:18 #17
Цитата Сообщение от Thinker Посмотреть сообщение
NP-сложные задачи несколько иные.
это я курсе Мало ли кто-то доказал, что p = np
DaskOFF
112 / 112 / 9
Регистрация: 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;
}
Thinker
Эксперт C++
4225 / 2199 / 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

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

DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
25.07.2013, 20:15  [ТС] #20
Up
может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач?
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
25.07.2013, 20:18 #21
Цитата Сообщение от DaskOFF Посмотреть сообщение
может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач?
почитайте о динамическом программировании. до конца жизни будет, чем заняться...)
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
25.07.2013, 21:18  [ТС] #22
Цитата Сообщение от salam Посмотреть сообщение
почитайте о динамическом программировании. до конца жизни будет, чем заняться...)
ну я приметил книгу, которую тут посоветовали ранее (Стивен Скиена. Алгоритмы.) Хороший выбор? Я только 1 курс закончил, но очень переживаю за свое будущее т.к. подобные алгоритмы мне пока даются не очень легко
Я ее пока просто полистал, а прочитал только "Задача о разбиении", но как я понял мне надо разбивать и переставлять, т.к. упорядоченное разбиение мне ничего толком не даст
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
25.07.2013, 21:56 #23
Цитата Сообщение от DaskOFF Посмотреть сообщение
т.к. подобные алгоритмы мне пока даются не очень легко
чтобы понять такие алгоритмы нужно прорешать задач 100. Они (кого я знаю лично) никому легко не давались. Не парься.
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
18.08.2013, 19:22  [ТС] #24
Цитата Сообщение от Thinker Посмотреть сообщение
В книге
Стивен Скиена. Алгоритмы.
эта задача в главе "Динамическое программирование"
Задача разбиения ?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.08.2013, 13:22 #25
Цитата Сообщение от DaskOFF Посмотреть сообщение
Задача разбиения ?
да, разбиение
DaskOFF
112 / 112 / 9
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 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));
    }
  }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2013, 02:25
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.08.2013, 02:25
Ответ Создать тему
Опции темы

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