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

Динамическое программирование - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
MarkizzZ
0 / 0 / 0
Регистрация: 18.02.2010
Сообщений: 8
18.02.2010, 13:03     Динамическое программирование #1
Задача:
Есть n работников и n работ. Необходимо найти максимальную суммарную производительность. Каждый работник может выполнять только одну работу.
Задаётся задача матрицей nxn где элемент a[i][j] есть показатель производительности i-го работника на j-ой работе.
Сделать это надо динамическим программированием, желательно.

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

PS если нужно смогу привести теорию задачи.
PPS пишу в консоли для простоты в с++
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2010, 13:03     Динамическое программирование
Посмотрите здесь:

C++ Динамическое программирование
Динамическое программирование C++
C++ Динамическое программирование
C++ ДП Динамическое программирование
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.02.2010, 22:04     Динамическое программирование #2
Цитата Сообщение от MarkizzZ Посмотреть сообщение
Главная проблема в том, как выбрать максимальный значения в строке и запомнить адресс выбранного элемена (строку и столбец) и исключить их из дальнейших вычислений.
Это неправильный подход к решению данной задачи. Вот небольшой пример:
На 1-ой работе: показатель производительности 1-го работника 10, а 2-го 9.
На 2-ой работе: показатель производительности 1-го работника 9, а 2-го 1.
Если сделать так как Вы пишите:
Цитата Сообщение от MarkizzZ Посмотреть сообщение
выбрать максимальный значения в строке и запомнить адресс выбранного элемена (строку и столбец) и исключить их из дальнейших вычислений
То получится в первой строке Вы выберете 1 работника на первой работе, соответственно 2-му работнику останется 2-ая работа. В итоге суммарная производительность будет равна 11.
А если сделать наоборот то суммарная производительность будет равна 18.
MarkizzZ
0 / 0 / 0
Регистрация: 18.02.2010
Сообщений: 8
18.02.2010, 22:46  [ТС]     Динамическое программирование #3
valeriikozlov, в этом и есть подвох динамического прорраммирования. то о чём вы говорите реализуется на бумаге венгерским методом или методом потенциалов, а динамическое программирование что-то среднее между перебором и жадным алгоритмом.

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

приведу простой пример
матрица А
5 4 8
7 3 9
6 6 1

первая часть ( первая цифра - означает строку, цифры в фигурных скобках порядковый номер элементов в текущей строке)
В(3, {1}) = 6
В(3, {2}) = 6
В(3, {3}) = 1
=======
В(2, {1*,2}) = max(6 + 3, 7 + 6) = 13
В(2, {1,3*}) = max(6 + 9, 7 + 1) = 15
В(2, {2,3*}) = max(6 + 9, 3 + 1) = 15
* - обозначет перспективные значения
В(1, {1,2,3}) = max(13 + 8, 15 + 4, 15 + 5) = 21
оптимальное назначение a[2][1] + a[3][2] + a[1][3]

могу для ясности (хотя это не поможет несведующим) привести исходные рекурентные соотношения для решения задачи в общем виде.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.02.2010, 23:28     Динамическое программирование #4
MarkizzZ, Алгоритм Ваш понятен. Непонятно только зачем Вам
Цитата Сообщение от MarkizzZ Посмотреть сообщение
исключит в дальнейших вычесления строку и столбец
Вот для данного примера можете показать какую строку и столбец Вы собираетесь исключать в дальнейших вычислениях
MarkizzZ
0 / 0 / 0
Регистрация: 18.02.2010
Сообщений: 8
19.02.2010, 17:05  [ТС]     Динамическое программирование #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вот для данного примера можете показать какую строку и столбец Вы собираетесь исключать в дальнейших вычислениях
да, могу.
В(2, {1,2}) = max(6 + 3, 7 + 6) = 13
В(2, {1,3}) = max(6 + 9, 7 + 1) = 15
В(2, {2,3}) = max(6 + 9, 3 + 1) = 15
======
В(1, {1,2,3}) = max(13 + 8, 15 + 4, 15 + 5) = 21
в последней строке у нас 3 суммы, где нужно выбрать максимальную. 13 сумма a[2][1] и a[3][2] то есть нужно вычеркнуть эти строки и столбцы что бы к сумме этих элементов не добавились элементы из этих строк и столбцов.

вот соотношения:

Исполнители J1, J2.... Jn
Работы R1, R2... Rn
Матрица производительности A = {Aij}
Пошаговое управление некоторой системой:
(s) - работы
(k, s{*n-k+1*}) - система (исполнители, работы), начальное состояние которой (1 {номер исполнителя}, {1,2,3...n} доступные работы)
конечное состояние (n+1, {пустое множество})
Дальше воспользуемся функцией Бэллмана
В(k, s{*n-k+1*}) - мкксимально возможная суммарная производительность оставшихся работников (k, k+1, k+2... n) если между ними распределить оставшиеся работы s{*n-k+1*}
B(1,{1,2,....n}) - оптимальное значения критерия задачи

Соотношения примут следующий вид (начинаем с конца траектории когда осталься лишь один переход)
B(n,{j}) = a{*nj*}
В(k, s{*n-k+1*}) = max{*q из множетва s{*n-k+1*} *}[a{*kq*} + В(k+1, s{*n-k+1*}\{q})]

в скобочках вида {**} подстрочный текст и индексы

===========
есть мысль поступить немного иначе: найти все возможные суммы в матрице а значения и адресса элементов входящих в сумму в массив, где первый столбец - сумма, а остальные столбцы содержат адреса элементов из исходной матрицы. После по первому столбцу выбрать максимальный элемент и вывести его на экран вместе с адресами элементов.
Я понимаю что это жутко непонятно но поэтому здесь

Добавлено через 4 часа 20 минут
может есть какие идеи обойти приведённые формулы?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.02.2010, 06:14     Динамическое программирование #6
Цитата Сообщение от MarkizzZ Посмотреть сообщение
да, могу.
Цитата:В(2, {1,2}) = max(6 + 3, 7 + 6) = 13
В(2, {1,3}) = max(6 + 9, 7 + 1) = 15
В(2, {2,3}) = max(6 + 9, 3 + 1) = 15
======
В(1, {1,2,3}) = max(13 + 8, 15 + 4, 15 + 5) = 21
в последней строке у нас 3 суммы, где нужно выбрать максимальную. 13 сумма a[2][1] и a[3][2] то есть нужно вычеркнуть эти строки и столбцы что бы к сумме этих элементов не добавились элементы из этих строк и столбцов.
Но эти строки и столбцы все равно нельзя вычеркивать - ведь они нужны будут для вычисления других сумм:
Цитата Сообщение от MarkizzZ Посмотреть сообщение
15 + 4
Цитата Сообщение от MarkizzZ Посмотреть сообщение
15 + 5
Если Вы собираетесь так делать, то у Вас точно ничего не получиться. В первых для примера когда 3 исполнителя и 3 работы можно идти построчно (можно вычислить результат используя сравнение только трех величин). А вот смотрите что получится если 4 работы и 4 исполнителя:
1 2 3 4
4 5 6 7
7 8 9 1
8 5 2 3
В(4, {1}) = 8
В(4, {2}) = 5
В(4, {3}) = 2
В(4, {4}) = 3
=======
В(3, {1,2}) = max(7 + 5, 4 + 8) = 12
В(3, {1,3}) = max(7 + 6, 9 + 4) = 13
В(3, {1,4}) = max(7 + 7, 1 + 4) = 14
В(3, {2,3}) = max(5 + 9, 8 + 2) = 14
В(3, {2,4}) = max(5 + 1, 8 + 3) = 11
В(3, {3,4}) = max(9 + 7, 6 + 1) = 16
Дальше получится вот сколько сравнений:
В(2, {1,2,3})
В(2, {1,2,4})
В(2, {1,3,4})
В(2, {2,3,4})
И в конце последнее:
В(1, {1,2,3,4})
Так вот заметили, если массив больше чем 3*3, то значений бывет больше чем столбцов, и в этот массив Вы их не сможете вставить.
Вообще если делать Вашим алгоритмом, то можно не учитывать значения которые в строках ниже (если вы имели ввиду про их исключение, то это можно делать), но ведь и так понятно, что расчитав например B3, вы в дальнейших вычислениях не будете использовать элементы массива в 3-ей строке и ниже. А вот исключать столбцы нельзя. Сто процентов что любой элемент в первой строке (а значит и любого столбца) нужен будет для вычислений B1.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
20.02.2010, 06:34     Динамическое программирование #7
И что вы фигней страдаете?
Это типовая транспортная задача, только с условием на максимум, а не на минимум.
Примеров в интернете - вагон.
SAMZ
1260 / 703 / 13
Регистрация: 21.12.2009
Сообщений: 2,255
20.02.2010, 07:36     Динамическое программирование #8
Цитата Сообщение от Patch Посмотреть сообщение
И что вы фигней страдаете?
Это не "фигня". Динамическое программирование, основанное на принципе оптимальности Белмана и на соответсвующих рекурентных уравнениях, мощный инструмент решения подобных задач. Но, думаю, форум не место для детального описания реализации подобных алгоритмов. Посмотрите книгу Р.Белмана "Прикладное динамическое прграммирование". Там во вступительной главе обсуждается задача оптимального распределения ресурса по 10 производствам. Алгоритм, который там описан Вам подойдет.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.02.2010, 08:39     Динамическое программирование #9
Patch, насчет
Цитата Сообщение от Patch Посмотреть сообщение
И что вы фигней страдаете?
это Вы зря. Человек хочет определенный принцип (алгоритм) решения задач реализовать (который кстати подходит для решения). Не нужно его отвлекать от решения по этому принципу (алгоритму). Если он хочет, то дойдет до решения именно так как задумал.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
20.02.2010, 09:30     Динамическое программирование #10
да я в курсе, что это такое.
я про то, чем вы тут занимаетесь.
изобретатели велосипедов...
вот ссылка, посмотрите: http://www.nkzu.kz/NKZU/FIT/mat/discretmath/metodZK.htm
MarkizzZ
0 / 0 / 0
Регистрация: 18.02.2010
Сообщений: 8
20.02.2010, 12:59  [ТС]     Динамическое программирование #11
согласен, прмер некоректен. Но по моим умозаключениям получается что скжем при решении задачи 10х10 не имеет смысла хранитт в памяти все получаемые значения и какие-то из них исключаются в ходе решения как непрерспективные.

Вообще если делать Вашим алгоритмом, то можно не учитывать значения которые в строках ниже (если вы имели ввиду про их исключение, то это можно делать), но ведь и так понятно, что расчитав например B3, вы в дальнейших вычислениях не будете использовать элементы массива в 3-ей строке и ниже.
вот не очень понятно как это организовать циклом, поэтому сюда и пришёл.
Цитата Сообщение от Patch Посмотреть сообщение
И что вы фигней страдаете?
Это типовая транспортная задача, только с условием на максимум, а не на минимум.
Примеров в интернете - вагон.
конечно! Это ж гениально! только то о чём вы говорите годится для решения на бумаге, метод потенциалов или Венгерский метод, проблема в том что нужно делать именно динамическим программированием так как от него проше перейти к минимксной или максиминной задаче, а от них к бикритериальноной. За ссылку спасибо, посмотрю детально.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
20.02.2010, 13:10     Динамическое программирование #12
Цитата Сообщение от MarkizzZ Посмотреть сообщение
конечно! Это ж гениально! только то о чём вы говорите годится для решения на бумаге, метод потенциалов или Венгерский метод, проблема в том что нужно делать именно динамическим программированием так как от него проше перейти к минимксной или максиминной задаче, а от них к бикритериальноной. За ссылку спасибо, посмотрю детально.
а ссылка как раз на алгоритм решения методом динамического программирования.
я таких штук 5 разных нашел за 10 минут.
Осталось сесть и реализовать на конкретном языке.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.02.2010, 18:31     Динамическое программирование #13
Цитата Сообщение от Patch Посмотреть сообщение
изобретатели велосипедов...
Ну во первых никто здесь велосипедов не изобретает. SAMZ даже описывает чей алгоритм он пытается реализовать.
Во вторых, та ссылка которую Вы дали, она для решения совсем другой задачи. Тот алгоритм совсем не подойдет для решения этой задачи. А алгоритм который выбрал SAMZ абсолютно подходит для решения его задачи.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
20.02.2010, 19:40     Динамическое программирование #14
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Ну во первых никто здесь велосипедов не изобретает. SAMZ даже описывает чей алгоритм он пытается реализовать.
Во вторых, та ссылка которую Вы дали, она для решения совсем другой задачи. Тот алгоритм совсем не подойдет для решения этой задачи. А алгоритм который выбрал SAMZ абсолютно подходит для решения его задачи.
Значит старею. И торможу.
Ладно, не важно... лишь бы у автора работало как надо.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.02.2010, 19:53     Динамическое программирование #15
Цитата Сообщение от Patch Посмотреть сообщение
лишь бы у автора работало как надо.
это главное
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.05.2010, 20:11     Динамическое программирование
Еще ссылки по теме:

C++ Динамическое программирование
Динамическое программирование C++

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

Или воспользуйтесь поиском по форуму:
MarkizzZ
0 / 0 / 0
Регистрация: 18.02.2010
Сообщений: 8
16.05.2010, 20:11  [ТС]     Динамическое программирование #16
вопрос всё ещё актуален, но в случае динамического программирования.
найти оптимальное назначение не трудно. сложнее выбрать паретооптимальные назначения из них.

Главная проблема - как востоновить назначение, то есть какие элементы матрицы (номера элементов, их координаты в матрице) обеспечивают лучшее из найденных.
Yandex
Объявления
16.05.2010, 20:11     Динамическое программирование
Ответ Создать тему
Опции темы

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