Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Июль 2010   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Академик
Рейтинг: 6671
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Профессионал
Рейтинг: 4511
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2038
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:208
Дата выхода:21.07.2010, 19:00
Администратор рассылки:Гаряка Асмик, Профессионал
Подписчиков / экспертов:64 / 48
Вопросов / ответов:2 / 3

Вопрос № 179508: Добрый день, помогите пожалуйста с решением задачи "О назначении" методом дискретного программирования??? Я подобные задачи всегда решала Венгерским методом или Куна. мне подойдет любой пример с решением, дальше разберусь сама. Очень ...

Вопрос № 179509: Добрый вечер, подскажите пожалуйста, как можно решить "задачу о назначениях" методом динамического программирования??? я всегда решала подобные задачи Венгерским методом. мне подойдет любой решенный пример (дальше разберусь сама). Зар...
Вопрос № 179508:

Добрый день, помогите пожалуйста с решением задачи "О назначении" методом дискретного программирования???
Я подобные задачи всегда решала Венгерским методом или Куна. мне подойдет любой пример с решением, дальше разберусь сама.
Очень жду ответа, заранее спасибо.

Отправлен: 15.07.2010, 19:46
Вопрос задал: lenaka, Посетитель
Всего ответов: 2
Страница вопроса »

Отвечает max123, 4-й класс :
Здравствуйте, lenaka.
Ну поскольку вам нужен любой пример с решением, тогда запишем следующую задачу:
Задача имеет две эквивалентные постановки:
1)Дана квадратная матрица A[1..N,1..N]. Нужно выбрать в ней N элементов так, чтобы в каждой строке и столбце был выбран ровно один элемент, а сумма значений этих элементов была наименьшей.
2)Имеется N заказов и N станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

Решение:

const int INF = 1000*1000*1000;

int n;
vector < vector<int> > a;
vector<int> xy, yx;
vector<char> vx, vy;
vector<int> minrow, mincol;

bool dotry (int i) {
if (vx[i]) return false;
vx[i] = true;
for (int j=0; j<n; ++j)
if (a[i][j]-minrow[i]-mincol[j] == 0)
vy[j] = true;
for (int j=0 ; j<n; ++j)
if (a[i][j]-minrow[i]-mincol[j] == 0 && yx[j] == -1) {
xy[i] = j;
yx[j] = i;
return true;
}
for (int j=0; j<n; ++j)
if (a[i][j]-minrow[i]-mincol[j] == 0 && dotry (yx[j])) {
xy[i] = j;
yx[j] = i;
return true;
}
return false;
}

int main() {

... чтение a ...

mincol.assign (n, INF);
minrow.assign (n, INF);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
minrow[i] = min (minrow[i], a[i][j]);
for (int j=0; j<n; ++j)
for (int i=0; i<n; ++i)
mincol[j] = min (mincol[j], a[i][j] - minrow[i]);

xy.assign (n, -1);
yx.assign (n, -1);
for (int c=0; c<n; ) {
vx.assign (n, 0);
vy.assign (n, 0);
int k = 0;
for (int i=0; i<n; ++i)
if (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) {
int z = INF;
for (int i=0; i<n; ++i)
if (vx[i])
for (int j=0; j<n; ++j)
if (!vy[j])
z = min (z, a[i][j]-minrow[i]-mincol[j]);
for (int i=0; i<n; ++i) {
if (vx[i]) minrow[i] += z;
if (vy[i]) mincol[i] -= z;
}
}
}

int ans = 0;
for (int i=0; i<n; ++i)
ans += a[i][xy[i]];
printf ("%d\n", ans);
for (int i=0; i<n; ++i)
printf ("%d ", xy[i]+1);

}

Ответ отправил: max123, 4-й класс
Ответ отправлен: 15.07.2010, 21:11
Номер ответа: 262555

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 262555 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Отвечает Гордиенко Андрей Владимирович, Академик :
    Здравствуйте, lenaka.

    Здесь на с. 38 - 42 Вы можете рассмотреть пример решения задачи о назначениях методом ветвей и границ.

    С уважением.
    -----
    Пусть говорят дела

    Ответ отправил: Гордиенко Андрей Владимирович, Академик
    Ответ отправлен: 17.07.2010, 10:26
    Номер ответа: 262572

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 262572 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Вопрос № 179509:

    Добрый вечер, подскажите пожалуйста, как можно решить "задачу о назначениях" методом динамического программирования???
    я всегда решала подобные задачи Венгерским методом. мне подойдет любой решенный пример (дальше разберусь сама).
    Заранее спасибо.

    Отправлен: 15.07.2010, 21:52
    Вопрос задал: lenaka, Посетитель
    Всего ответов: 1
    Страница вопроса »

    Отвечает max123, 4-й класс :
    Здравствуйте, lenaka.

    Рассмотрим задачу о ранце с четырьмя предметами.
    5x(1)+7x(2)+6x(3)+3x(4) → max,
    2x(1)+3x(2)+5x(3)+7x(4) ≤ 9,

    x(i) ∈ {0,1}, i=1,2,3,4.

    Все параметры задачи целые неотрицательные числа.
    Обозначим через Z(k,p) - задачу, при условиях, что
    предметов k, k ≤ m (для нашей задачи m=4), а вместимость
    ранца p, p ≤ v(0) (для нашей задачи v(0)=9 ). Пусть R(k,p) -
    оптимум задачи Z(k,p). Тогда оптимум исходной задачи
    совпадает с оптимумом задачи Z(m,v(0)) и равен R(m,v(0)).
    Для определения величин R(m,v(0)) построим следующие
    рекуррентные соотношения:

    R(k+1,p) = R(k,p) , если v(k+1) > p,
    (1)
    R(k+1, p) = max { R(k,p), c(k+1) + R(k, p- v(k+1)}, если p>
    v(k+1) + 1.

    Эти рекуррентные соотношения, с учетом граничных
    условий

    R(1,p) = 0, если с(1) > p, (2)
    R(1,p) = c(1), если c(1) < p+1,

    будем использовать для решени я исходной задачи о ранце.
    Результаты вычислений по рекуррентным соотношениям
    будем представлять в виде таблицы с m=4 строками и
    v(0)=9 столбцами , в которой приводятся значения
    соответственных величин R(k,p). Для того чтобы решить
    исходную задачу о ранце необходимо заполнить клетку
    таблицы с координатами: m=4 , v(0)=9. Для этого не
    требуется заполнить все клетки таблицы, а лишь те,
    которые используются для вычисления значений величины
    R(4,9).



    Таблица заполняется следующим образом.
    R(4,9)=max { R(3,9), c(4)+ R(3,9-v(4))}= max { R(3,9), c(4)+
    R(3, 9 - 7}=
    max { R(3,9), c(4)+ R(3,2}. Таким образом, для заполнения
    ячейки (4,9) необходимо заполнить ячейки (3,9) и (3,2). В
    свою очередь для заполнения этих ячеек необходимо
    заполнить другие ячейки. Первой заполняется ячейка (1,1).
    В ней, согласно граничным условиям (2), значение
    R(1,1)=0. Затем, используя рекуррентные соотношения (1)
    заполняются остальные ячейки, пока ячейка с номером (4,9)
    не будет заполнена. Решение задачи о ранце, согласно
    содержанию ячейки (4,9), будет иметь вид:
    x’(1)=0, x’(2)=1, x’(3)=1, x’(4)=0. Значение оптимума
    задачи F(x’)=13.
    Активирован BBCode изображения
    -----
    ∙ Отредактировал: Химик CH, Модератор
    ∙ Дата редактирования: 16.07.2010, 11:23 (время московское)

    Ответ отправил: max123, 4-й класс
    Ответ отправлен: 16.07.2010, 08:47
    Номер ответа: 262556

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 262556 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2010.6.16 от 26.05.2010
    В избранное