Разработка бесконфликтного расписания экзаменов эквивалентна раскраске графов. Однако задача раскраски графов принадлежит к классу NP, ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Макконелл Д.N. Основы современных алгоритмов Изд2


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

(cкачать страницу)

Смотреть книгу на libgen

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