Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 [2]  Все   Вниз
  Печать  
Автор Тема: Жадный алгоритм для выбора заявок  (Прочитано 59980 раз)
0 Пользователей и 2 Гостей смотрят эту тему.
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #30 : 15-01-2010 15:53 » 

Угу =)
Просто.. я словами то могу объяснить необходимость и достаточность.. но надо как-то более формализованно.. Наверное
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #31 : 15-01-2010 18:40 » 

А я насчёт "конфликтности" заявок не понял. Что это такое? Каждая заявка имеет несколько подходящих аудиторий, но такое соответствие - это вовсе не закрепление заявки за аудиторией, это лишь область допустимых значений на множестве паросочетаний. Поэтому тут конфликта ещё нет. Тогда что есть конфликт, и что есть разрешение конфликта? (Формально) Выбор подмножества паросочетаний, которое в результате даёт сюрьективное, но не инъективное отображение - это выбор неподходящий, потому что в нём есть конфликты. Другое подмножество с биективным отображением подходит, но в нём нет конфликта. Тогда непонятно, как количество праобразов (заявок) для одного образа (аудитории) определяет потребность (в аудиториях).
« Последнее редактирование: 15-01-2010 18:45 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #32 : 17-01-2010 09:45 » 

Мы такими темпами все дальше просто напросто закапываться будем во множества. Давайте абстрагируемся от них и вернемся все ж таки к заявкам?
Даром что у меня тут новый алгоритм поспел =)
Составляется матрица из 0 и 1 размером NxN, где N - количество заявок. Где каждая строка соответствует какой то заявке. 0 - на пересечении совместных заявок(Si включено в [Sj,fj)), 1 - несовместных, включая и саму себя. Соответственно самое большое количество единиц в какой то строке и будет необходимым количеством аудиторий. Затем идем по списку заявок (начиная с той, у которой максимальное колиечство единиц в строке) и раскидываем их по аудиториям, отмечая в матрице  что они уже распределены.
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #33 : 17-01-2010 10:48 » 

BredoZavR, не совсем понятно: тебе нужно просто получить некоторый алгоритм и доказать его полноту? Сначала я думал, что у тебя есть требование придерживаться жадного алгоритма.

Если всё же алгоритм может быть произвольным, то есть ли требования к сложности алгоритма? Новый предложенный алгоритм имеет сложность O(N^2) на несортированных данных, O(N*k) в худшем случае на сортированных (если заявки упорядочены по времени начала), где k - это максимум одновременных заявок. И этот метод не нуждается в таблице - таблица (что-то вроде матрицы смежности) лишь делает подсчёт более наглядным.
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #34 : 17-01-2010 11:12 » 

Цитата: Bredozavr
Давайте абстрагируемся от них и вернемся все ж таки к заявкам?
Перефразируя "Вам шашечки или ехать?": тебе доказательство, или чтобы работало?
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #35 : 18-01-2010 08:46 » 

Вад, есть  требование придерживаться жадного
нам и шашечки, и ехать)
но с шашечками у меня проблем не возникает, а вот с доказательством все заржавело..
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #36 : 18-01-2010 12:21 » 

Цитата: BredoZavR
Соответственно самое большое количество единиц в какой то строке и будет необходимым количеством аудиторий.
А всё же, откуда возникла эта идея?

Пример в лоб:

Пусть 3 заявки: А, Б, В.
Код:
  А Б В
А 1 0 1
Б 0 1 1
В 1 1 1
Матрица, вообще говоря, зеркальна относительно главной диагонали, поскольку если А конфликтует с Б, то и Б конфликтует с А (симметричное отношение). По 3-й строке видно, что нужны 3 аудитории. Давай смотреть на конкретном примере.

Пусть А длится с 12 до 13 часов. Б длится с 13 до 14 часов. В длится с 12 до 15 часов. А и Б не конфликтуют между собой, но и А, и Б конфликтуют с В. Поэтому В мы выделяем одну аудиторию. Во вторую аудиторию помещается вначале А, потом Б. Итого видим, что достаточно лишь 2-х аудиторий, а твой метод показывает на 3.

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

BredoZavR, ты пойми, что методом тыка никакие доказательства не делаются; нужны основания для рассуждений и логика. Для оснований нужна чёткая матмодель твоих заявок и аудиторий. Если она будет, половина ответов на возможные вопросы будет очевидна заранее.
« Последнее редактирование: 18-01-2010 12:46 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #37 : 19-01-2010 04:36 » 

Алгоритм дан преподавателем.. Так как ни один мой его не устроил =/
Так что уж придется вертеться вокруг этого алгоритма.
Записан
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #38 : 19-01-2010 13:30 » 

Матрица то вот как составляется..
в матрицу записывается не совместность, а если заявка длится  [Si,fi), то входит ли Sj в этот участок или нет, то есть конец заявки мы не смотрим
То есть к примеру если у нас заявки 1-3, 2-8, 3-5, 6-7, 6-10 то у 6-7 на пересечении с 2-8 будет стоять 1, так как 6 входит в отрезок 2-8, а у 2-8 неа пересечении с 6-7, не будет, так как 2 не входит  в отрезок 6-7 
и эта матрица вовсе не симметрична относительно главной диагонали
Записан
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #39 : 19-01-2010 17:27 » 

Фу блин, написано, работает, кто-нибудь хочет посмотреть этот чудо-алгоритм? ^_^
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #40 : 19-01-2010 18:03 » 

Давай. Улыбаюсь
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #41 : 19-01-2010 18:31 » 

BredoZavR, ладно, в такой матрице количество единиц соответствует Улыбаюсь
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #42 : 20-01-2010 18:40 » 

Вот доделаю и покажу.. А то я опять недочет заметила
Записан
BredoZavR
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #43 : 20-01-2010 23:05 » 

Вы не поверите.. работает!
Правда у меня ощущение, что, написав это, я сглажу его
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #44 : 21-01-2010 11:48 » 

BredoZavR, Гремлины не дремлют.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #45 : 21-01-2010 12:05 » new

а Дремлины не гремлют Улыбаюсь
Записан

Страниц: 1 [2]  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines