Составление школьного расписания

From: Boris Rudakov (2:5054/9.4)
To: Andrey Belyakov (2:5054/9)
Date: 2000-02-25T11:41:32Z
Area: RU.ALGORITHMS
Hello Andrey!

24 Feb 00 12:43, Andrey Belyakov wrote to All:

 AB> From: "Andrey Belyakov" <andrejb@care.lv>

 AB> Hi, Boris Rudakov !

 >>  >>> Никто субж не пробовал делать? У меня уже немного бошка
 >>  >>> съехала при попытках это организовать...
 >>  AB>> Если найдешь общее решение - пиши - куплю.
 >>  VP> Ага, это можно сразу за диссертацию садиться, эту задачу не
 >>  VP> могут решить даже подвинутые профессора и программисты.
 >> Не надо преувеличивать. Задача в основном сводится к топологической
 >> сортировке, а основные сложности связаны с обработкой притиворечий
 >> (циклов) и как правило заключаются лишь в том как выбрать наименее
 >> неправильное из всех неправильных решений в ситуации когда
 >> правильного решения нет :)
 AB> Собственно об этом и разговор. Как отбросить на этапе нахождения
 AB> решения те из неправильных решений, которые не нужно проверять
 AB> в процессе решения?
Если не проверять, то как узнать что они неправильные ? :)
Нет, на самом деле можно придумать легкую оптимизацию и отсекать неправильные решения на ранней стадии рассмотрения. А вообще, это должно решаться путем не очень сложной рекурсии: нужно разработать систему оценок нарушений (исходя из предметной области) и путем обычного рекурсивного обхода выбрать N решений с наилучшим рейтингом. Оптимизация может лишь помочь отсекать особоплохие решения не анализируя их до конца.

 AB> Я согласен потратить месяц
Ты шутишь - за месяц можно отрендерить чуть ли не половину графики для крутого голливудского фильма, а там вычислительные задачки не в пример серьезней :)

 AB> на крутой (4 процессора + 1Гб RAM) персоналке считая предварительные
 AB> данные, с тем чтобы потом задача гарантированно решалась за пару
 AB> секунд.
Ты точно шутишь :)
* Разрабатываемый алгоритм не может опираться ни на какие "предварительные данные" - ввел данные в законченную программу, нажал кнопку и через некоторое время получил N решений, из которых L правильных и M - наилучших неправильных.
* На такой машинке про которую ты говоришь, любой хоть сколько-то разумный алгоритм решения ДАННОЙ ЗАДАЧИ, при разумном с точки зрения практики количестве данных, должен работать чуть ли не мгновенно :) Особенно если ты дашь себе труд его распаралелить чтобы воспользоваться многопроцессорностью (это совсем несложно).

В общем, пробегись по алгоритму топологической сортировки (быстро и на пальцах - у Вирта, сложно но исчерпывающе - у Кнута, только том не помню). Потом определись с оценочной функцией (рейтингами нарушений) и напиши рекурсивный алгоритм оценки некорректных решений. Чисто в свободное время можешь ого оптимизировать и распаралелить. Одним словом, если предметная область четко очерчена (т.е. есть приемлимое ТЗ) то определиться с рейтингами и UI можно очень быстро и на всю работу уйдет не более 1-2-х месяцев (я имею в виду уже не алгоритм, а полноценный программный продукт).

 AB> Андрей.

Борис Рудаков,               Как увидишь Сникерс - ты не ешь его,
BBR                          он с самим Манделлой цвета одного...

--- Be happy: BBR is looking at you !
 * Origin: АлкАголь малыми дозами безвреден в любых количествах (2:5054/9.4)