Я застрял с одной из задач домашней задачи алгоритма. Кто-нибудь может дать мне подсказку, чтобы решить это? Вот вопрос:
Рассмотрим цепное структурированное вычисление, представленное взвешенным графом G = (V; E), где
V = {v1; v2; ...; vn} и E = {(vi; vi + 1) так, что 1 <= i <= n-1. Нам также дана цепная структура m одинаковых процессоров P = {P1; ...; Pm} (то есть существует линия связи между Pk и Pk + 1 для 1 <= k <= m - 1). </p>
Множество вершин V представляет вычислительные модули, а множество ребер E представляет
связь между двумя модулями. Каждому узлу vi присваивается вес, обозначающий
время выполнения модуля на одном процессоре. Каждому фронту (vi; vi + 1) присваивается вес ci, обозначающий количество времени связи между двумя модулями, если им назначены два разных процессора. Если несколько модулей назначены одному процессору, модули, назначенные одному процессору, должны быть последовательными. Предположим, модули va; в + 1; ..; VB назначены процессору ПК. Затем время Pk, обозначаемое Tk, представляет собой время для вычисления назначенных модулей плюс время для обмена данными между соседними процессорами. Следовательно, Tk = wa + ... + wb + ca-1 + cb. Обратите внимание, что ca-1 = 0, если a = 1, и cb = 0, если b = n.
Задача задачи состоит в том, чтобы найти назначение V для P такое, что max1 <= k <= m Tk
сводится к минимуму, где мы предполагаем, что каждый процессор должен занимать хотя бы один модуль. (Это
предположение можно ослабить, добавив m фиктивных модулей с нулевым весом в вычислительном
и время общения.)
Разработать алгоритм динамического программирования для решения этой проблемы за полиномиальное время (т. Е. O (mn)) </p>
Я пытался найти минимальное время выполнения для каждого Pk, а затем найти максимум, но я сомневаюсь, что мое решение - это динамическое программирование, поскольку нет рекурсивной формулы. Пожалуйста, дайте мне несколько советов!
Спасибо!