Оптимальное распределение задач

@Smipe · Регистрация: 13.10.2020

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

Задача звучит так: У вас есть 2-ядерный процессор и программа, состоящая из n независимых задач, которую нужно максимально быстро выполнить на этом процессоре, распределив задачи между 2 ядрами. Время выполнения задачи j это p_j. Задачи нельзя прерывать во время выполнения. Напишите псевдокод алгоритма, который распределяет задачи по 2 ядрам так, чтобы время завершения всей программы (то есть время завершения последней задачи) было минимально. Покажите, какую вычислительную сложность имеет ваш алгоритм и почему. Считайте, что размер массива p_j, не более 10^3, а его элементы - целые числа от 1 до 10^4

Я пробовал делать так, сортировать все числа за O(nlog n) и жадным алгоритмом распределять время выполнения этих задач за O(n). Например есть массив из 20 элементов:
[13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]. Отсортировав, получаем
[1, 13, 26, 29, 31, 42, 47, 57, 58, 61, 64, 64, 72, 73, 87, 88, 92, 97, 99, 100]. И теперь на каждое ядро поочередно берем максимальное время, то есть
на 1 ядро: 100, 97, 88, 73, 64, 61, 57, 42, 29, 13 - общая сумма времени = 624
на 2 ядро: 99, 92, 87, 72, 64, 58, 47, 31, 26, 1 - общая сумма времени = 577
И теперь попытаться прировнять эти суммы. Будем брать последовательно минимальное число из ядра, у которого сумма времени больше. Проверяем
624 - 13 = 611 и 577 + 13 = 590 разница 21
624 - 29 = 595 и 577 + 29 = 606 разница 11
624 - 42 = 582 и 577 + 42 = 619 разница 37
И в конце смотри уже из 2 ядра, что можно переложить в первое (с учетом того, что мы закинули 11 в 2 ядро)
606 - 1 = 605 и 595 + 1 = 596 разница 9
Время выполнения O(n log n + n + n) = O(n log n). Скорее всего это решение неправильно, подскажите как можно решить такую задачу, какие алгоритмы использовать?

@Mikhaylo · 25.07.2021, 17:19

А если входной массив разделить на две части (два списка), подсчитать две суммы и затем жонглировать?

[13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]

S[13, 64, 61, 88, 1, 58, 47, 31, 97, 42] = 502
S[92, 87, 99, 72, 26, 29, 73, 64, 57, 100] = 699
Задача сводится к тому, чтобы выбрать из первого/второго списка такие числа, которые отнимаются/прибавляются к 502, чтобы получить сумму S, такую что (S-600,5)=min. Или другая формулировка: выбрать из первого/второго списка такие числа, которые отнимаются/прибавляются, чтобы получить сумму S, такую что (S-98,5)=min.

Алгоритм не предложен, только идея.

@vantfiles · 25.07.2021, 18:19

Нужно найти коэффициенты уравнения:

k1*p_j1 + k2*p_j2 + k3*p_j3 + ... kn*p_jn так, чтобы сумма была равна или как можно ближе к половине суммы p_j. (Kn = 0|1)
А это перебор, число циклов равно в худшем случае 2^n

@Mikhaylo · 25.07.2021, 18:27

Задача разбиения множества чисел
https://ru.m.wikipedia.org/wik... 0%B5%D0%BB

мы свели к

Задача о сумме подмножеств
https://ru.m.wikipedia.org/wik... 1%82%D0%B2

@Smipe · 25.07.2021, 18:30 **[ТС]**

vantfiles, когда массив будет из 1000 элементов, довольно долго работать будет. На другом форуме предложили решать через динамическое программирование, со сложностью O(N^2 * W), где W - максимально возможное значение элементов массива

@LegionK · 25.07.2021, 19:27

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

На другом форуме предложили решать через динамическое программирование, со сложностью O(N^2 * W), где W - максимально возможное значение элементов массива

Лучше не получится. Например, в случае, когда можно разбить элементы по группам таким образом, чтобы суммы в группах были равны, даже на проверку этого условия нам придется написать задачу о рюкзаке. Сложность решения которой как раз N*T, где T - вместимость рюкзака. В вашем случае T = (максимальный элемент*N)/2, что и даёт

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

O(N^2 * W)

Берите решение с того форума.

@vrm2 · 31.07.2021, 18:29

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

Я пробовал делать так, сортировать все числа за O(nlog n) и жадным алгоритмом распределять время выполнения этих задач за O(n). Например есть массив из 20 элементов:
[13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]. Отсортировав, получаем
[1, 13, 26, 29, 31, 42, 47, 57, 58, 61, 64, 64, 72, 73, 87, 88, 92, 97, 99, 100]. И теперь на каждое ядро поочередно берем максимальное время,

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

Python

def solve(tasks):
    p1, p1_sum = [], 0
    p2, p2_sum = [], 0
    for t in sorted(tasks, reverse=True):
        if p1_sum <= p2_sum:
            p1.append(t)
            p1_sum += t
        else:
            p2.append(t)
            p2_sum += t
    return p1, p2

Запускаем:

Python

    tasks = [13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]
    p1, p2 = solve(tasks)
    print(f'{p1=} {sum(p1)=}')
    print(f'{p2=} {sum(p2)=}')

Результат:

Код

p1=[100, 92, 88, 73, 64, 61, 47, 42, 26, 13] sum(p1)=606
p2=[99, 97, 87, 72, 64, 58, 57, 31, 29, 1] sum(p2)=595

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

И теперь попытаться прировнять эти суммы

Вообще, у нас нет цели, чтобы суммы были равны. На нужно найти решение, в котором максимум из сумм был минимальным.

@Smipe · 31.07.2021, 22:43 **[ТС]**

vrm2, нет, Вы не совсем правильно поняли задачу. Нам нужно смотреть на максимум из двух сумм x1, x2 (пусть x1 >= x2), потому что последняя задача, которая закончит свое выполнение, будет лежать в этом максимальном числе x1.

Python

    def halfsum(lst):
    halfs = sum(lst) // 2
    best = halfs + 1
    a = [0] * best
    a[0] = -1
    for l in lst:
        for i in range(halfs, l-1, -1):
            if (a[i - l] !=0) and a[i] == 0:
                a[i] = l
                best = min(halfs - i, best)
    id = halfs - best
    b = []
    while (id > 0):
        b.append(a[id])
        id = id - a[id]
    return b
 
print(halfsum([13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]))

> [99, 42, 97, 31, 47, 58, 88, 61, 64, 13]
Это разбиение будет давать суммы 600 и 601
То есть на втором ядре будут задачи с временем выполнения [1, 92, 87, 72, 26, 29, 73, 64, 57, 100]

@Dani_Du · 01.08.2021, 16:16

Наверное самим простим и очень эффективным решением, будет х - задач на ядро(х = сума сложности задач / количество ядер). Дальше просто загрузка на ядро, пока сума сложностей загруженных задач < х, и так по всем ядрам.

Если все-таки надо найти, максимально быстрого распределения задач на выполнения, то это будет комбинаторика(очень затратно).

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

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

Наверное самим простим и очень эффективным решением, будет х - задач на ядро(х = сума сложности задач / количество ядер). Дальше просто загрузка на ядро, пока сума сложностей загруженных задач < х, и так по всем ядрам.

Если все-таки надо найти, максимально быстрого распределения задач на выполнения, то это будет комбинаторика(очень затратно).

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

Кстати если задачи не будут меняться, то комбинаторика становиться оправданной, а так получается что поиск лучшей комбинации занимает больше времени, чем остаток длительности(эффективного решения от лучшей комбинации).

@Smipe 1 / 1 / 0 Регистрация: 13.10.2020 Сообщений: 10
		1
	Оптимальное распределение задач 25.07.2021, 12:32. Показов 1722. Ответов 8 Метки c++, merge sort, жадный алгоритм (Все метки) Задача звучит так: У вас есть 2-ядерный процессор и программа, состоящая из n независимых задач, которую нужно максимально быстро выполнить на этом процессоре, распределив задачи между 2 ядрами. Время выполнения задачи j это p_j. Задачи нельзя прерывать во время выполнения. Напишите псевдокод алгоритма, который распределяет задачи по 2 ядрам так, чтобы время завершения всей программы (то есть время завершения последней задачи) было минимально. Покажите, какую вычислительную сложность имеет ваш алгоритм и почему. Считайте, что размер массива p_j, не более 10^3, а его элементы - целые числа от 1 до 10^4 Я пробовал делать так, сортировать все числа за O(nlog n) и жадным алгоритмом распределять время выполнения этих задач за O(n). Например есть массив из 20 элементов: [13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100]. Отсортировав, получаем [1, 13, 26, 29, 31, 42, 47, 57, 58, 61, 64, 64, 72, 73, 87, 88, 92, 97, 99, 100]. И теперь на каждое ядро поочередно берем максимальное время, то есть на 1 ядро: 100, 97, 88, 73, 64, 61, 57, 42, 29, 13 - общая сумма времени = 624 на 2 ядро: 99, 92, 87, 72, 64, 58, 47, 31, 26, 1 - общая сумма времени = 577 И теперь попытаться прировнять эти суммы. Будем брать последовательно минимальное число из ядра, у которого сумма времени больше. Проверяем 624 - 13 = 611 и 577 + 13 = 590 разница 21 624 - 29 = 595 и 577 + 29 = 606 разница 11 624 - 42 = 582 и 577 + 42 = 619 разница 37 И в конце смотри уже из 2 ядра, что можно переложить в первое (с учетом того, что мы закинули 11 в 2 ядро) 606 - 1 = 605 и 595 + 1 = 596 разница 9 Время выполнения O(n log n + n + n) = O(n log n). Скорее всего это решение неправильно, подскажите как можно решить такую задачу, какие алгоритмы использовать? 0

@Mikhaylo 646 / 522 / 72 Регистрация: 20.09.2014 Сообщений: 3,356
	25.07.2021, 17:19	2
	А если входной массив разделить на две части (два списка), подсчитать две суммы и затем жонглировать? [13, 64, 61, 88, 1, 58, 47, 31, 97, 42, 92, 87, 99, 72, 26, 29, 73, 64, 57, 100] S[13, 64, 61, 88, 1, 58, 47, 31, 97, 42] = 502 S[92, 87, 99, 72, 26, 29, 73, 64, 57, 100] = 699 Задача сводится к тому, чтобы выбрать из первого/второго списка такие числа, которые отнимаются/прибавляются к 502, чтобы получить сумму S, такую что (S-600,5)=min. Или другая формулировка: выбрать из первого/второго списка такие числа, которые отнимаются/прибавляются, чтобы получить сумму S, такую что (S-98,5)=min. Алгоритм не предложен, только идея. 0

@vantfiles 1003 / 1858 / 176 Регистрация: 07.05.2013 Сообщений: 3,894 Записей в блоге: 12
	25.07.2021, 18:19	3
	Нужно найти коэффициенты уравнения: k1p_j1 + k2p_j2 + k3p_j3 + ... knp_jn так, чтобы сумма была равна или как можно ближе к половине суммы p_j. (Kn = 0\|1) А это перебор, число циклов равно в худшем случае 2^n 0

@Mikhaylo 646 / 522 / 72 Регистрация: 20.09.2014 Сообщений: 3,356
	25.07.2021, 18:27	4
	Задача разбиения множества чисел https://ru.m.wikipedia.org/wik... 0%B5%D0%BB мы свели к Задача о сумме подмножеств https://ru.m.wikipedia.org/wik... 1%82%D0%B2 0

@Smipe 1 / 1 / 0 Регистрация: 13.10.2020 Сообщений: 10
	25.07.2021, 18:30 [ТС]	5
	vantfiles, когда массив будет из 1000 элементов, довольно долго работать будет. На другом форуме предложили решать через динамическое программирование, со сложностью O(N^2 * W), где W - максимально возможное значение элементов массива 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	25.07.2021, 19:27	6
	Сообщение было отмечено Smipe как решение Решение Сообщение от Smipe На другом форуме предложили решать через динамическое программирование, со сложностью O(N^2 * W), где W - максимально возможное значение элементов массива Лучше не получится. Например, в случае, когда можно разбить элементы по группам таким образом, чтобы суммы в группах были равны, даже на проверку этого условия нам придется написать задачу о рюкзаке. Сложность решения которой как раз NT, где T - вместимость рюкзака. В вашем случае T = (максимальный элементN)/2, что и даёт Сообщение от Smipe O(N^2 * W) Берите решение с того форума. 0

@Dani_Du 215 / 40 / 0 Регистрация: 31.07.2021 Сообщений: 30
	01.08.2021, 16:16	9
	Наверное самим простим и очень эффективным решением, будет х - задач на ядро(х = сума сложности задач / количество ядер). Дальше просто загрузка на ядро, пока сума сложностей загруженных задач < х, и так по всем ядрам. Если все-таки надо найти, максимально быстрого распределения задач на выполнения, то это будет комбинаторика(очень затратно). Добавлено через 43 минуты Сообщение от Dani_Du Наверное самим простим и очень эффективным решением, будет х - задач на ядро(х = сума сложности задач / количество ядер). Дальше просто загрузка на ядро, пока сума сложностей загруженных задач < х, и так по всем ядрам. Если все-таки надо найти, максимально быстрого распределения задач на выполнения, то это будет комбинаторика(очень затратно). "загрузка на ядро" правильнее будет предложение, загрузка на очередь выполнение ядром. Кстати если задачи не будут меняться, то комбинаторика становиться оправданной, а так получается что поиск лучшей комбинации занимает больше времени, чем остаток длительности(эффективного решения от лучшей комбинации). 0

Оптимальное распределение задач

Решение