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

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

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

« : 28-12-2009 15:46 » 

Задача о заявках (расширенная)
Удовлетворит все заявки в наименьшее количество аудиторий.
Алгоритм написан, реализован
Состоит в том, что заявки сортируются не как при обычном Greedy Activity Selector по окончании, а по количеству совместных с ними (по возрастающей)

Проблема в доказательстве
Нужно доказать правильность работы алгоритма Обосновать. Прошу помощи. Сама уже не справляюсь  С ума сойти...
Надо будет код, вставлю
Записан
Finch
Спокойный
Администратор

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


« Ответ #1 : 28-12-2009 15:48 » 

Ну на пустом месте можно конечно доказать, что 2 равно 0. А Алгоритмы чтоб доказывать. Надо хотя бы знать. Что именно применяется и как реализовано.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #2 : 28-12-2009 15:51 » 

Что именно от меня требуется предоставить, чтобы была возможность рассчитывать на небольшую толику помощи?
Записан
Finch
Спокойный
Администратор

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


« Ответ #3 : 28-12-2009 15:54 » 

Хотя бы устное описание алгоритма. Ну и код того участка, в который алгоритм заложен. Если он не сверх секретный.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #4 : 28-12-2009 16:02 » 

Сортируем заявки по количеству совместных с  ними (по возрастанию). То есть в начале будет заявка с наименьшим количеством совместных, в конце - с наибольшим.
применяем следующий жадный алгоритм: берем заявку с наименьшим количеством совместных с ней, а затем среди оставшихся совместных вновь берем заявку с наименьшим количеством совместных. И так далее.
Во внешнем цикле ведется подсчет количества аудиторий.

Код:
struct claim
{
double begin;
double end;
double length;
bool satisfied;
int comp;
};


void SortByCompatibilities(claim* arr, int num) //Сортирует заявки по возрастанию количества совместных с ними
{
int j;
int tmp;
claim temp;
for(int i=1; i<num; ++i)
{

tmp=arr[i].comp;
temp=arr[i];
j=i-1;
while(j>=0 && arr[j].comp>tmp)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}

}

void GreedySelector(claim *arr, int i, int num) /*Жадный алгоритм, на каждом шаге отбирающий заявку,
имеющую наименьшее количество совместных с ней*/
{
arr[i].satisfied=true;
for(int j=0; j<num; ++j)
{
if((arr[j].begin>=arr[i].end && arr[j].satisfied==false) || (arr[j].end<=arr[i].begin && arr[j].satisfied==false))
{
arr[j].satisfied=true;
i=j;
}
}
}

int CountCompatibilities(claim *arr, int i, int num) //Процедура подсчета совместных с входной заявок
{
int count=0;
for(int j=0; j<num; ++j)
{
if(arr[i].begin>=arr[j].end || arr[i].end<=arr[j].begin)
count++;
}
return count;
}

int _tmain(int argc, _TCHAR* argv[])
{
int num;
p_rus("Введите количество заявок: ");
cin >>num;
claim *arr=new claim[num];
for(int i=0; i<num; ++i)
{
p_rus("Начало заявки: ");
cin >>arr[i].begin;
p_rus("Конец заявки: ");
cin >>arr[i].end;
arr[i].length=arr[i].end-arr[i].begin;
arr[i].satisfied=false;
arr[i].comp=0;
}
for(int i=0; i<num; ++i)
arr[i].comp=CountCompatibilities(arr, i, num);

//Sort(arr, num);
SortByCompatibilities(arr, num);

int audcount=0; //Количество аудиторий
for(int i=0; i<num; ++i) //Подсчет количества необходимых аудиторий
{
if(arr[i].satisfied==false)
{
GreedySelector(arr, i, num);
audcount++;
Print(arr, num);
cout <<endl<<endl;
i=0;
}
}

p_rus("Все заявки были удовлетворены. Количество аудиторий, необходимых для этого: ");
cout <<audcount<<endl;

return 0;
}


Записан
Finch
Спокойный
Администратор

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


« Ответ #5 : 28-12-2009 17:34 » 

Буду проверять как говорится по порядку. и добавлять в этот пост по мере проверки.
Код:
void SortByCompatibilities(claim* arr, int num) //Сортирует заявки по возрастанию количества совместных с ними
{
int j;
int tmp;
claim temp;
for(int i=1; i<num; ++i)
{

tmp=arr[i].comp;
temp=arr[i];
j=i-1;
while(j>=0 && arr[j].comp>tmp)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}

}
Тут ошибка. Ты явно теряеш значения.

Код:
int CountCompatibilities(claim *arr, int i, int num) //Процедура подсчета совместных с входной заявок
{
int count=0;
for(int j=0; j<num; ++j)
{
if(arr[i].begin>=arr[j].end || arr[i].end<=arr[j].begin)
count++;
}
return count;
}
Тут count должен отдавать на 1 заявку больше. Так как заявка подсчитывает саму себя
« Последнее редактирование: 28-12-2009 17:41 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #6 : 28-12-2009 17:59 » 

Эмм.. как бы.. работает все =)
Правильно работает.. Сортировка точно правильно работает, проверено выводом на экран
и что значит "заявка подсчитывает саму себя"?
Записан
Finch
Спокойный
Администратор

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


« Ответ #7 : 28-12-2009 18:02 » 

А что будет, когда j равно i?
А насчет правильно сортирует. Мне аж стало интересно. Сейчас погоняю код.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #8 : 28-12-2009 18:12 » 

Тогда не на одну больше,а на одну меньше
Записан
Finch
Спокойный
Администратор

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


« Ответ #9 : 28-12-2009 18:33 » 

Кстати, насчет сопряжения я не понял. Вот взял я для примера 5 заявок. Вот что получилось.


Объясни, что там и с кем сопрягается.
Эта картинка сразу после вычсления сопряжений. Без сортировки.

* Screenshot.png (16.46 Кб - загружено 4206 раз.)
« Последнее редактирование: 28-12-2009 18:35 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #10 : 28-12-2009 18:57 » 

Смотри, знать кто с кем именно не надо, надо просто знать количество совместных заявок
то есть нулевая заявка совместна с 2, 3 и 4
первая с 2, 3 и 4
вторая с 0, 1, 5
третья с 0, 1
четвертая с 0, 1, 2
Записан
Finch
Спокойный
Администратор

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


« Ответ #11 : 29-12-2009 06:38 » 

Ну начнем с самого конца.
У тебя всего 5 возможныъ пар сопряжения. По моим подсчетам. Буду показывать на примерах
1) 8-9 10-11
2) 8-9 9-10
3) 8-11 8-10
4) 9-11 8-12
5) 9-12 8-12
Следовательно для этих пар, ты должна показать. Что твой код
Код:
if(arr[i].begin>=arr[j].end || arr[i].end<=arr[j].begin)
count++;
Будет отрабатывться корректно.
Дальше сортировка. Хотя немножко не стандартный алгоритм. Но соответсвует в принципе так называемой Шейкер сортировке. Хотя при плохом раскладе, я думаю по скорости будет Примерно на уровне пузырькового алгоритма. Как примерно показывать корректность сортировок, можно посмотреть в сети. С твоим третьим этапом. Я пока что не разобрался до конца. Хотя вроде понимаю заложенный принцип.
Записан

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

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


« Ответ #12 : 29-12-2009 09:57 » 

Я сейчас точно не смогу смодулировать ситуацию. Допустим после сортировки, в твою функцию GreedySelector пришел такой массив. Покажу только первых три элемента.
Код:
arr[0]
   begin = 10
   end    = 13
   length = 3
   satisfied = false
   comp = 7
arr[1]
   begin = 4
   end    = 9
   length = 5
   satisfied = false
   comp = 8
arr[2]
   begin = 12
   end    = 17
   length = 5
   satisfied = false
   comp = 9
........
По идее говоря, тут нужно заказывать 2 аудитории. Так как 0 и 2 соприкасаются вместе. Твой алгоритм всем им выделит 1 аудиторию.

Ошибка заключается в том, что ты последуюшие запросы не проверяеш со всеми удовлетворяюшими сопряжению. А только с последним удовлетворяюшим сопряжению.
« Последнее редактирование: 29-12-2009 10:00 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #13 : 29-12-2009 20:59 » 

и точно.. но.. я повторюсь.. не надо ошибки искать, а? надо доказать тот момент, что выбирая в первую аудиторию, мы не закрываем путь к глобально оптимальному решению.. ошибки будут искаться потом, на этапе проверки самой лабораторной.. Нашлась бы ошибка.. исправила бы..
а у меня идей нет как доказать
буду сидеть, исправлять) спсибо, что указал, но, все ж, это не первостепенно
хотя все же странно, что алгоритм в итоге работает верно %)
Записан
Finch
Спокойный
Администратор

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


« Ответ #14 : 29-12-2009 21:48 » 

Ладно не буду про ошибку. Хотя я долго вьезжал в таинственный смысл i=j; Улыбаюсь

Ну оптимальное решение я бы искал по другому Улыбаюсь Жадный алгоритм хоть и предназначен для поиска оптимального решения, но встречаются случаи, когда он не срабатывает. Кстати докозательство алгоритма можно найти тут Там как раз расматривают твой случай Улыбаюсь Правда они пошли другим путем.
У тебя на каждом шаге ты ишеш все заявки, если их поместить в одну аудиторию, то они между собой не будут конфликтовать. При этом ты отсекаеш самую насышенную заявку, у которой могут быть наибольшее количество конфликтов.
« Последнее редактирование: 29-12-2009 21:56 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

« Ответ #15 : 31-12-2009 05:16 » 

Таинственная строчка i=j взята из родного жадного алгоритма выбора заявок Greedy Activity Selector =))
В том то и дело, что и на вики,  и в некоторых других источниках задача сформулирована несколько иначе. В классическом варианте нужно выбрать максимальное количество заявок в одну аудиторию. А мне нужно в минимальное количество аудиторий. Доказательство обычного тут не подходит, к сожалению. Мы уже пытались идти таким путем.
Записан
Finch
Спокойный
Администратор

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


« Ответ #16 : 31-12-2009 07:19 » 

Ну мой вариант. ОН правда построен по другому принципу.
Код:
#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::sort;

struct claim {
double begin;
double end;
int audit;
bool operator < (const claim & val) const {return begin < val.begin;}
};

typedef vector<claim> listClaim;
typedef listClaim::iterator itrClaim;

void print(listClaim &val) {
int count=1;
for(itrClaim i=val.begin(); i != val.end(); ++i) {
  cout << count++ << ". " << i->begin << "-" << i->end << " Аудитория:" << i->audit << endl;
}
}

int assignment(listClaim &val) {
   listClaim room;
   itrClaim itr;
  for(itrClaim i=val.begin(); i != val.end(); ++i) {
     itr=room.begin();
     while((itr != room.end()) && (i->begin < itr->end)) ++itr;
     if (itr != room.end()) {
        i->audit = itr->audit;
        *itr = *i;
     }
     else {
     i->audit=room.size()+1;
     room.push_back(*i);
     }
   }
  
   return room.size();
}

int main() {
int num;
cout << "Введите количество заявок: ";
cin >>num;
listClaim arr;
claim temp;
int i=0;
while (i<num)
{
cout << "Заявка # " << i+1 <<endl;
cout <<"Начало заявки: ";
cin >>temp.begin;
cout << "Конец заявки: ";
cin >>temp.end;
temp.audit=-1;
if (temp.begin < temp.end) {
i++;
arr.push_back(temp);
}
else cout << "Неправильно введено время заявки. Введите еше раз\n";
}
sort(arr.begin(), arr.end());
cout << "Запрос на обшее количество аудиторий:" << assignment(arr) << endl;
print(arr);
return 0;
}
Я отсортировал все заявки по времени начала. Затем иду по списку отсортированных заявок. И отслеживаю конфликты времени. Т. е. Если есть несколько заявок, которые конфликтуют между собой по времени. Значит им нужно дать отдельные аудитории.

Я делал эту прогу в GCC. Под студию, если будеш переносить. Нужно будет подправить кирилицу.
« Последнее редактирование: 31-12-2009 07:21 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

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

ох.. спасибо, конечно
но проблема доказательства никуда не делась)
Записан
Finch
Спокойный
Администратор

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


« Ответ #18 : 02-01-2010 18:38 » 

Ну я могу только доказать, что он в отдельных случаях  будет не самым оптимальным Улыбаюсь
Простой пример. Тебе на разбор, после сортировки приходят такие заявки,
8-12, ....... , 4-7, ........, 4-6, 6-8, ......
Твой алгоритм скорее всего выбирет
4-7, 8-12 Хотя иногда наверно выгоднее было бы 4-6, 6-8, 8-12
Конечно понимаю, что это все анти доказательства. Но в принципе все теоремы рассыпаются именно на анти доказательствах.
Записан

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

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

« Ответ #19 : 02-01-2010 19:12 » 

Можно ли задачу переформулировать на аналогичную на множествах и отношениях между ними, чтобы предмет доказательства был не замутнён ненужными деталями?

Пусть есть множество элементов X и множество элементов Y, а также отображение F : X -> Y.

Как известно, отображение может быть сюрьективным (на каждый y ссылаются какие-то x), инъективными (все x ссылаются на разные y) или биективным (и то, и другое одновременно). В данном случае никто не гарантирует ни первого, ни второго, ни, тем более, третьего. Однако можно рассмотреть частный случай, когда имеем сюрьективное отображение.

Пусть у нас есть множество заявок X = {1, 2, ...} и множество аудиторий Y = {А, Б, ...}. Соответственно, мы можем построить отображение заявок на аудитории по их сочетаемости (по каким-то признакам, которые нас в данном вопросе не интересуют). Пусть задана оценочная функция w(x), сообщающая для каждой заявки, сколько аудиторий для неё подходит (если я правильно понял принцип сортировки заявок для обработки).

Например, пусть X = {1, 2}, Y = {А, Б}, F = {1->А, 1-Б, 2->А}. Как видим по множеству F, w(1)=2, w(2)=1, поэтому заявки нужно обрабатывать в порядке 2, 1. Тогда 2->А, и остаётся 1->Б. Работает.

Спрашивается, можно ли подобрать контрпример, который приводит к неразрешимой ситуации? Это сделать несложно.

Пусть X = {1, 2, 3}, Y = {А, Б}, F = {1->А, 2->Б, 3->А, 3->Б}. Имеем w(1)=1, w(2)=1, w(3)=2, поэтому обрабатываем заявки в порядке 1, 2, 3. Удовлетворив 1 и 2 заявки, получим, что заявка 3 не может быть удовлетворена.

Но эту ситуацию можно было определить сразу, поскольку количество заявок (мощность X) больше количества аудиторий (мощность Y).

Можно наложить дополнительное условие на исходные данные, но, как мне кажется, в том и заключается искусство математика, чтобы точно определить условия решаемой задачи - правильная формулировка проблемы содержит половину решения.

BredoZavR, в общем, завтравку для подхода к доказательству я сделал, дальше попробуй рассуждать сама.
Записан

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

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

« Ответ #20 : 14-01-2010 14:12 » 

Погоди, погоди.. При чем здесь количество заявок больше количества аудиторий? Конечно, оно больше.. В том и суть, чтоб удовлетворить все заявки в наименьшее количество аудиторий..
Я совсем запуталась, чтоб эту задачу..
Записан
Dimka
Деятель
Команда клуба

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

« Ответ #21 : 14-01-2010 22:20 » 

BredoZavR, теперь я не понял. Как несколько заявок может быть удовлетворено одной аудиторией одновременно? Если речь про разнесение по времени, то я говорил лишь об "одномоментном" случае, и время у меня в рассуждениях не фигурирует, если внимательно посмотришь.

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

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

В общем случае количество заявко-часов должно быть меньше или равно количество аудиторий-часов, иначе задача нерешаема. С этим-то согласна? Или тоже неочевидно?
Записан

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

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

« Ответ #22 : 15-01-2010 06:17 » 

Тут ВУЗ не совсем хороший пример.. Заявки различные по длительности.. то есть просто какие то отрезки времени случайным образом раскиданы по временной шкале..
То есть если в классическй задаче о заявках мы удовлетворяем как млжно большее число в одну аудиторию, то тут мы удовлетворяем все в как можно меньшее количество аудиторий.. %)
Записан
BredoZavR
Интересующийся

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

« Ответ #23 : 15-01-2010 14:46 » 

В результате преподаватель сказал, что "возможно, Ваш алгоритм довольно сложен для доказательства, сделайте по другому"
Теперь что то типа как предложил Finch =)
Тут, я надеюсь, докажу своими силами.. хотя кто знает =/
Может паника на фоне сессии отшибает последний ум
Записан
Вад
Модератор

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

« Ответ #24 : 15-01-2010 14:57 » 

Может, я где-то упускаю постановку задачи. На всякий случай, уточню:

1. Верно ли, что для любой заявки подходит любая свободная аудитория, то есть, нет дополнительных условий типа вместимости и т.п.?
2. Если п.1, то правильно ли я понимаю, что суть задачи сводится к тому, что есть некий набор временных отрезков, и для него нужно найти, каково максимальное число одновременно пересекающихся временных отрезков, т.е., заявок, требующих аудитории?
Записан
BredoZavR
Интересующийся

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

« Ответ #25 : 15-01-2010 15:23 » 

Так точно..
Слушайте.. Сразу можно сказать необходимое количество аудиторий: это максимальное количество одновременных несовместных заявок.. У Finch'a как раз примерно так и возвращает по сути.. Почему это количество аудиторий необходимо - понятно, но а вот почему достаточно?
Записан
Finch
Спокойный
Администратор

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


« Ответ #26 : 15-01-2010 15:27 » 

BredoZavR, Не совсем понял, насчет достаточно? Если тебе не требуется больше аудиторий, чтоб удовлетворить все заявки, я думаю, то необходимое количество будет достаточно. Конечно можно вводить дополнительные условия. Алгоритм вполне это допускает. Нужно только добавить условия выбора.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
BredoZavR
Интересующийся

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

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

Это понятно, но как доказать? Обосновать?
Записан
BredoZavR
Интересующийся

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

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

Я, конечно, могу заявить: "Ну тут же видно что этого количества достаточно!!"
Но, боюсь, такое доказательство не примут)
Записан
Finch
Спокойный
Администратор

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


« Ответ #29 : 15-01-2010 15:47 » 

У меня в программе ишится максимум конфликтных заявок. Естественно больше аудиторий, чем максимум конфликтных заявок не нужен. Следовательно этот максимум достаточен для удовлетворения запроса. Но это уже пошла философия.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines