среда, 21 января 2015 г.

Эвристический алгоритм решения задачи о минимальном количестве линий для размещения отрезков

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

Давайте рассмотрим такой алгоритм. Будем действовать максимально просто.