Жадный алгоритм для выбора заявок

[BredoZavR]

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

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

[Finch]

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

[BredoZavR]

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

[Finch]

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

[BredoZavR]

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

Код:

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]

Буду проверять как говорится по порядку. и добавлять в этот пост по мере проверки.

Код:

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 заявку больше. Так как заявка подсчитывает саму себя

[BredoZavR]

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

[Finch]

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

[BredoZavR]

Тогда не на одну больше,а на одну меньше

[Finch]

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

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

[BredoZavR]

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

[Finch]

Ну начнем с самого конца.
У тебя всего 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]

Я сейчас точно не смогу смодулировать ситуацию. Допустим после сортировки, в твою функцию 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 аудиторию.

Ошибка заключается в том, что ты последуюшие запросы не проверяеш со всеми удовлетворяюшими сопряжению. А только с последним удовлетворяюшим сопряжению.

[BredoZavR]

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

[Finch]

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

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

[BredoZavR]

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

[Finch]

Ну мой вариант. ОН правда построен по другому принципу.

Код:

#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. Под студию, если будеш переносить. Нужно будет подправить кирилицу.

[BredoZavR]

ох.. спасибо, конечно
но проблема доказательства никуда не делась)

[Finch]

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

[Dimka]

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

Пусть есть множество элементов 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]

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

[Dimka]

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

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

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

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

[BredoZavR]

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

[BredoZavR]

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

[Вад]

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

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

[BredoZavR]

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

[Finch]

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

[BredoZavR]

Это понятно, но как доказать? Обосновать?

[BredoZavR]

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

[Finch]

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