Перевод на BOINC.RU

Оригинал страницы


The Rectilinear Crossing Number Project

проект поиска минимального числа прямолинейных пересечений

   Много вопросов в вычислительной и комбинаторной геометрии основано на конечных множествах точек на Евклидовой плоскости. Несколько проблем из теории графов также вписываются в эту структуру, когда края графа  ограничены прямым. Типичный вопрос - известная проблема прямолинейного числа пересечения (используемый для решения, например, транспортных проблем и оптимизацию планировок): Каково наименьшее количество пересечений можно получить на рисунку полного плоского графа с вершинами из n точек с прямыми ребрами? Здесь подразумевается законченный граф, в котором любая пара точек связана прямой линией. Кроме того мы принимаем общее правило для точек, что никакие три точки не могут находиться на общей линии.

   Не трудно видеть, что мы можем поместить четыре точки на плоскости так, чтобы никаких пересечений не произошло. Для пяти точек рисунок показывает различные способы их размещения (это варианты различных упорядоченных наборов (введенных Гудманном (Goodman) и Поллаком (Pollack)  в 1983 году.)). Если Вы помещаете пять точек в выпуклые положения тогда есть пять пересечений. Лучшее, что Вы можете сделать, попытаться получить только одно пересечение (нет никакого способа изобразить полный граф из пяти точек без пересечений, даже если Вы соедините вершины кривыми). КСТАТИ: Максимизировать число пересечений просто: Достаточно поместить все n точек  по кругу, чтобы получить максимум пересечений, который равен числу сочетаний из n элементов по 4.

   Для больших количеств точек очень трудно определить наилучшую конфигурацию. Основная причина - то, что число комбинаций различных способов размещения этих точек растет по экспоненте. Например, уже для n=11 имеется 2,334,512,907 различных комбинаций.

   Выдающиеся поиски числа пересечений полного графа были начаты Р. Гаем (R. Guy) в 60-ых годах. К 2000 году были найдены оценки только для n <=9, в 2001 задача была решена для n=10, и в 2004 - для n=11. Основная цель текущего проекта состоит в том, чтобы использовать сложные математические методы (абстрактное расширение упорядоченных наборов), чтобы определить прямолинейное число пересечения для маленьких значений n. Пока мы успешно применяем их для n <= 17. Совсем недавно (даже еще не опубликовано) стали известны математические рассмотрения числа прямолинейных пересечений для n=19 и n=21. Таким образом самая дразнящая проблема теперь состоит в том, чтобы определить истинное значение для n=18, которая и является основной целью этого проекта.

   Обновленный список лучших наборов точек, известных на данный может быть рассмотрен в  http://www.ist.tugraz.at/staff/aichholzer/crossings.html.



Вернуться на BOINC.RU


 

Перевод выполнил AlexA, команда "Russia Team"

С переводом помогли Citerra и Антон(fizik80)