Полный перебор vs. случайный (оптимизация)

[Посторонний]

Требуется оптимизировать расписание.

Полный перебор займет слишком много времени.

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

[Парджеттер]

Посторонний писал(а):

Требуется оптимизировать расписание.

А как его оптимизировать-то?
По каким критериям
Мне вот всегда было это интересно.

[Vovochka]

Парджеттер писал(а):

По каким критериям
Мне вот всегда было это интересно.

...а это смотря что "расписывать" будем, а критериеФ напридумаем...

...можно "Монтекарлить"... (выбирайте критерии, а можно сразу по всем... )

Критерий хи*квадрат Пирсона
Критерий отношения правдоподобия
Точный критерий Фишера
Критерий совместной линейной связи
Коэффициент сопряженности
Фи*статистика
Статистика V Крамера
Статистика t (тау) Гудмэна и Краскела
Коэффициент неопределенности –
симметричный и асимметричный
Статистика k (каппа)
Статистика g (гамма)
Критерий Фридмана
Критерий Q Кокрена
Критерий серий Вальда*Вольфовица
Критерий U Манна*Уитни или критерий W
суммы рангов Уилкоксона
Двухвыборочный критерий Колмогорова*
Смирнова
Критерий маргинальной однородности
Критерий знаковых рангов Уилкоксона
Критерий знаков
Критерий МакНемара
Корреляция Спирмена
Статистика R Пирсона
Статистика D Сомера * симметричная и
асимметричная
Статистика t*b и t*c Кендалла
Коэффициент согласия Кендалла
Критерий Краскела*Уолеса
Критерий медиан
Критерий Джонкхиера*Терпстры
Одновыборочный критерий хи*квадрат
Одновыборочный критерий Колмогорова*
Смирнова
Одновыборочный критерий серий Вальда*
Вольфовица
Биномиальный критерий

С уважением.

[Посторонний]

Парджеттер писал(а):

А как его оптимизировать-то?
По каким критериям

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

для определенности может конкретную задачу взять?

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

[Парджеттер]

Посторонний писал(а):

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

А что, правда такие глупые критерии в реальности? Тогда теперь понятно, почему все всегда недовольны расписанием.
Да и ограничения какие-то странные. Из-за них требуется привязка к конкретным аудиториям и тут уж перебор возникает.

Посторонний писал(а):

Насколько полученный минимум будет отличаться от минимума, полученного полным перебором?

Вестимо это будет от выборки зависеть. А еще надо бы иметь распределение, вы же понимаете. Одно дело, если вам нужен один конкретный вариант, это одна вероятность, она у вас фактически нулевая при вменяемых выборках. А чтобы оценить разбежку с тем единственно оптимальным вариантом $m_{opt}$, надо иметь некоторые числовые значения. Пусть у вас это будет число "окон" $m$. Тогда у вас будет какая-то целочисленная функция $m=m(n)$, где $n$ - какой-то номер варианта. Дискретные случайные величины. Из полного набора вариантов вы берете какие-то $N$. Выбираете из них тот, у которого значение $m_N=\min$. И вам надо определить зависимость $|m_{opt}-m_N|$ от $N$.

Ну вот. А дальше потыкайте. Посмотрите, что получается.

[Vovochka]

Посторонний писал(а):

для определенности может конкретную задачу взять?

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

Добрый день.

...я, конечно, с "критериями" в предыдущем постере не совсем удачно пошутил(это у меня прога всё это делает)

...а по поводу вашей задачи, зачем голову ломать?

http://www.sch297.ru/autor.html

АВТОР-2+ позволяет:
оптимизировать "окна" в расписании;
учитывать требуемый диапазон дней/часов как для классов, так и для преподавателей;
оптимально pазмещать занятия по кабинетам (аудиториям) с учетом особенностей классов, предметов, пpеподавателей и вместимости кабинетов;
учитывать хаpактеp pаботы и пожелания как штатных сотpудников, так и совместителей-почасовиков;
легко соединять ("спаpивать") несколько классов (учебных групп) в потоки пpи пpоведении любых занятий;
pазделять классы пpи пpоведении занятий по иностранному языку, физической культуре, тpуду, информатике (и любым другим предметам) на любое количество подгрупп (до десяти!);
вводить (помимо основных пpедметов) Спецкуpсы и Факультативы;
оптимизировать равномерность и трудоемкость расписания.

...так какой настоящий вопрос?, а то задачка про расписание не совсем убеждает...
...если Вас интересует точность методов (в вашем случае подойдёт) Монте-Карло, то это напрямую зависит от колличества испытаний, погрешность в зависимости от сложности составляет от 5% до 15%.

[Brukvalub]

Посторонний писал(а):

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

Плохой критерий! Он совсем не учитывает интересы преподавателей, а я Вам со знанием дела скажу: преподаватель - он ведь тоже человек! И если ему придётся каждый день приходить в учебное заведение, чтобы провести одно занятие, он от обиды на такое расписание и заболеть может! Так что для начала нужно выработать правильные критерии, учитывающие интересы не только аудиторий, но и преподавателей, а потом уж и расписание составлять!

[Посторонний]

Vovochka писал(а):

...а по поводу вашей задачи, зачем голову ломать?

http://www.sch297.ru/autor.html

АВТОР-2+ позволяет:
оптимизировать "окна" в расписании;
учитывать требуемый диапазон дней/часов как для классов, так и для преподавателей;
оптимально pазмещать занятия по кабинетам (аудиториям) с учетом особенностей классов, предметов, пpеподавателей и вместимости кабинетов;


...так какой настоящий вопрос?, а то задачка про расписание не совсем убеждает...
...если Вас интересует точность методов (в вашем случае подойдёт) Монте-Карло, то это напрямую зависит от колличества испытаний, погрешность в зависимости от сложности составляет от 5% до 15%.

Школа вряд ли купит...

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

[Vovochka]

Посторонний писал(а):

Школа вряд ли купит...

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

Добрый день.

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

...а в Матлабе ваш энтузиаст-программист не пробовал?

...не знаю, будет ли это "справедливо", но на крайний случай, определитесь с критериями и в виде задачи разместите, может быть общими усилиями участники форума алгоритмики и помогут написать

С уважением.

P.S....не думаю, что программа "АВТОР" использует вероятностные методы...

[Парджеттер]

Vovochka писал(а):

P.S....не думаю, что программа "АВТОР" использует вероятностные методы...

Да, вряд ли.

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

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

[Vovochka]

Добрый день.

OFF.

Парджеттер писал(а):

И я немного не понял автора,..

...думаю, его(автора) все не совсем правильно поняли.., вопрос-то был (в принципе) о "точности" вероятностных методов оптимизации...

С уважением.