_В данной работе рассматривается решение оптимизационной задачи размещение вершин графа на линейке. Проведен анализ и разбор задачи. Предоставлена схема генетического алгоритма. Описаны особенности алгоритма такие как: кодирование решений, оператор рекомбинации и параметры генетического алгоритма. Были проведены экспериментальные исследование по определению эффективности предложенного алгоритма. Исследования позволяют сделать вывод, что предложенный алгоритм может находить оптимальные или квазиоптимальные решения за полиномиальное время._

# Введине

Задача размещения вершин графа на линейке является NP-полной[1]. Это означает то, что на данный момент не существует универсального алгоритма, который мог бы находить решение за полиномиальное время. Данная задача имеет теоретическую ценность теории алгоритмов. Ее ценность заключается в том, что если будет найдет «полиномиально быстрый» алгоритм решение данной задачи, то и любая другая задача из класса NP может быть решена также «быстро», а это в свою очередь докажет равенство классов ![][1] и ![][2]. До недавнего времени не существовало эффективного метода поиска решений NP-полных задач. С появлением эволюционного моделирование стало возможно находить квазиоптимальные решение за «приемлемое время». [Читать дальше →][3]

[1]: //habrastorage.org/files/51e/241/808/51e24180885540a98db70abe00526304.png
[2]: //habrastorage.org/files/bb8/31e/39a/bb831e39a86f47649bba49a604143ca1.png
[3]: http://habrahabr.ru/post/256645/#habracut