Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.03.2010, 00:15
Новичок

Отправить личное сообщение для Maria_Kap Посмотреть профиль Найти все сообщения от Maria_Kap
 
Регистрация: 01.03.2010
Сообщений: 3

Задача на поиск максимального значения
Дана матрица(слот) 6Х6(кадры).Имеются 32 абонента.Каждый абонент имеет в каждом кадре свою скорость. Нужно найти алгоритм для распределения абонентов по кадрам таким образом,чтобы суммарная скорость в слоте была максимальна.


Рассматривала метод динамического программирования,но он очень невыгоден по затратам.
Подскажите,пожалуйста,боле е эффективный метод.
  #2  
Старый 01.03.2010, 03:31
гость

 
Сообщений: n/a

нихера не понял условие. можно п-та еще раз помедленнее и с примером.
  #3  
Старый 01.03.2010, 06:36
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

это случайно не задача о назначениях?
(венгерским алгоритмом решается)
  #4  
Старый 01.03.2010, 14:03
Новичок

Отправить личное сообщение для Maria_Kap Посмотреть профиль Найти все сообщения от Maria_Kap
 
Регистрация: 01.03.2010
Сообщений: 3

Есть 6 частотных каналов и 6 временных кадров.Каждый из абонентов может передавать информацию на любой частоте и в любом кадре с определенной скоростью. Т.е. получается частотно-временная сетка (ось Х -время,ось У-частота).На каждую ячейку этой сетки надо назначить пользователя так,чтобы сумма всех скоростей в ячейках была максимальна.
Скорости пользователей в ячейках известны (т.е. для каждого пользователя даны 36 скоростей)

Последний раз редактировалось Maria_Kap, 01.03.2010 в 14:07.
  #5  
Старый 01.03.2010, 14:10
Новичок

Отправить личное сообщение для Maria_Kap Посмотреть профиль Найти все сообщения от Maria_Kap
 
Регистрация: 01.03.2010
Сообщений: 3

Сообщение от MBo Посмотреть сообщение
это случайно не задача о назначениях?
(венгерским алгоритмом решается)
Имеется ввиду задача о коммивояжере?
Про венгерский алгоритм не читала, посмотрю.
  #6  
Старый 01.03.2010, 14:29
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Имеется ввиду задача о коммивояжере?
нет, именно задача о назначениях (Assignment problem)
  #7  
Старый 30.07.2010, 11:14
Новичок

Отправить личное сообщение для deosis Посмотреть профиль Найти все сообщения от deosis
 
Регистрация: 30.07.2010
Сообщений: 8

Сообщение от MBo Посмотреть сообщение
>Имеется ввиду задача о коммивояжере?
нет, именно задача о назначениях (Assignment problem)
задача сводится к поиску максимального паросочетания максимального веса
Паросочетание максимального веса
  #8  
Старый 30.07.2010, 18:30
Пользователь

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

Что-то я не вкурил, может ли один абонент пользоваться несколькими ячейками сетки?
1. В первом сообщении нужно было абонентов распределить по ячейкам (каждому абоненту одну свою ячейку в зубы).
2. Во втором сообщении для каждой ячейки нужно назначить абонента (одной ячейке – какого-нибудь абонента).
Но, позвольте, ячеек 36, а абонентов 32. И поэтому верно либо 1, либо 2, но не вместе. Так что нужно то?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача на поиск оптимального значения Eugene86 Математические алгоритмы (другое) 5 23.01.2010 16:10
матрица максимального потока Jt1k Графы 1 09.11.2009 06:32
Быстрый поиск значения в отсортированной матрицы Igor Сортировка и поиск 2 17.02.2008 15:46
Нахождение максимального потока Вадярик Реализация, исходники, языки 0 07.08.2007 21:00
Паросочетание максимального веса гость Графы 5 30.07.2007 11:40