Плоскостность
Компьютерная игра-головоломка с планарными графами

Planarity — компьютерная игра-головоломка 2005 года , созданная Джоном Тантало, основанная на концепции Мэри Рэдклифф из Университета Западного Мичигана . [1] Название происходит от концепции планарных графов в теории графов; это графы, которые можно вложить в евклидову плоскость так, чтобы ни одно ребро не пересекалось. По теореме Фари , если граф плоский, его можно нарисовать без пересечений, так что все его ребра будут отрезками прямых линий. В игре Planarity игроку предоставляется круговая схема планарного графа , в которой все вершины размещены на одной окружности и имеют множество пересечений. Цель игрока — устранить все пересечения и построить прямолинейное вложение графа, перемещая вершины одну за другой в лучшие позиции.

История и версии

Игра была написана на Flash Джоном Тантало из Университета Кейс Вестерн Резерв в 2005 году. [2] Популярность в Интернете и местная известность, которую он приобрел, сделали Тантало одним из самых интересных людей Кливленда в 2006 году. [3] [4] Это, в свою очередь, вдохновило Криса Монтгомери из Xiph.org на создание версии GTK+ , которая обладает дополнительными алгоритмами генерации уровней и возможностью манипулировать несколькими узлами одновременно. [5]

Алгоритм генерации головоломки

Определение головоломки планарности не зависит от того, как генерируются планарные графы в головоломке, но исходная реализация использует следующий алгоритм:

  1. Создайте набор случайных линий на плоскости так, чтобы никакие две линии не были параллельны и никакие три линии не пересекались в одной точке.
  2. Рассчитайте пересечения каждой пары линий.
  3. Создайте граф с вершиной для каждого пересечения и ребром для каждого отрезка линии, соединяющего два пересечения ( расположение линий).

Если граф сгенерирован из линий, то граф будет иметь ровно вершины (каждая линия имеет вершины, и каждая вершина является общей с одной другой линией) и ребра (каждая линия содержит ребра). Первый уровень планарности построен из линий, поэтому он имеет вершины и ребра. Каждый последующий уровень генерируется на одну линию больше, чем предыдущий. Если уровень был сгенерирован из линий, то следующий уровень имеет больше вершин и больше ребер. Л {\displaystyle L} ( Л 2 ) = Л ( Л − 1 ) 2 {\displaystyle {\tbinom {L}{2}}={\tfrac {L(L-1)}{2}}} Л − 1 {\displaystyle L-1} Л ( Л − 2 ) {\displaystyle L(L-2)} Л − 2 {\displaystyle L-2} Л = 4 {\displaystyle L=4} Л ( Л − 1 ) / 2 = 6 {\displaystyle L(L-1)/2=6} Л ( Л − 2 ) = 8 {\displaystyle L(L-2)=8} Л {\displaystyle L} Л {\displaystyle L} 2 Л − 1 {\displaystyle 2L-1}

Наиболее известные алгоритмы из вычислительной геометрии для построения графов линейных расположений решают задачу за время, [6] линейное по размеру графа, который нужно построить, но они несколько сложны. Альтернативно и более просто, можно индексировать каждую точку пересечения парой линий, которые пересекаются в этой точке, сортировать пересечения вдоль каждой линии по их -координатам и использовать этот отсортированный порядок для генерации ребер планарного графа за почти оптимальное время. После того, как вершины и ребра графа сгенерированы, их можно равномерно разместить по окружности с помощью случайной перестановки . О ( Л 2 ) {\displaystyle O(L^{2})} х {\displaystyle x} О ( Л 2 бревно ⁡ Л ) {\displaystyle O(L^{2}\log L)}

Задача определения того, является ли граф планарным, может быть решена за линейное время , [7] и любой такой граф гарантированно имеет прямолинейное вложение по теореме Фари , которое также может быть найдено из планарного вложения за линейное время. [8] Таким образом, любая головоломка может быть решена компьютером за линейное время. Однако эти головоломки не так просты для решения людьми.

В области вычислительной геометрии процесс перемещения подмножества вершин в графе встраивания для устранения пересечений ребер изучался Пахом и Тардосом (2002), [9] и другими, вдохновленными головоломкой планарности. [10] [11] [12] [13] Результаты этих исследователей показывают, что (теоретически, предполагая, что поле игры представляет собой бесконечную плоскость, а не ограниченный прямоугольник) всегда можно решить головоломку, оставив входные вершины зафиксированными на месте в их исходных положениях, для константы , которая не была определена точно, но лежит между 1/4 и немного меньше 1/2. Когда планарный граф, который нужно распутать, является циклическим графом , большее количество вершин может быть зафиксировано на месте. Однако определение наибольшего количества вершин, которые можно оставить на месте для конкретной входной головоломки (или, что эквивалентно, наименьшего количества ходов, необходимых для решения головоломки), является NP-полной задачей . н ϵ {\displaystyle n^{\epsilon}} н {\displaystyle n} ϵ {\displaystyle \epsilon}

Вербицкий (2008) показал, что рандомизированная круговая схема , используемая для начального состояния планарности, является почти наихудшей из возможных с точки зрения количества пересечений : независимо от того, какой планарный граф должен быть запутан, ожидаемое значение количества пересечений для этой схемы находится в пределах трехкратного значения наибольшего количества пересечений среди всех схем. [14]

В 2014 году математик Дэвид Эппштейн опубликовал статью [15], в которой предложил эффективный алгоритм решения планарных графов, созданных с помощью оригинальной игры Planarity, основанный на специфике алгоритма генерации головоломок.

Ссылки

  1. ↑ Арар, Ярдена (1 августа 2005 г.), «Колыбель для кошки на стероидах», Today @ PC World, PCWorld , архивировано из оригинала 2009-06-04
  2. ^ Мэсси, Лора (2005-06-20). «Студент из Кейса разрабатывает процветающую онлайн-игру». Центр новостей Университета Кейс Вестерн Резерв . Получено 30 сентября 2007 г.
  3. ^ Кастро, Лора (18.11.2005). "Студентка из Кливленда — одна из самых интересных людей"". The Observer. Архивировано из оригинала 8 сентября 2006 года . Получено 30.09.2007 .
  4. ^ "Самые интересные люди 2006" (пресс-релиз). Cleveland Magazine. Январь 2006. Получено 2015-05-19 .
  5. ^ "gPlanarity домой".
  6. ^ Шазелл, Б.; Гибас , Л. Дж.; Ли , Д. Т. (1985), «Сила геометрической дуальности», BIT , 25 (1): 76–90 , doi :10.1007/BF01934990
  7. ^ Мельхорн, К.; Мютцель , П. (1996), «О фазе встраивания алгоритма проверки планарности Хопкрофта и Тарьяна», Algorithmica , 16 (2): 233–242 , doi : 10.1007/s004539900046 , hdl : 11858/00-001M-0000-0014-B51D-B , MR  1394503
  8. ^ de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1990), «Как нарисовать планарный граф на сетке», Combinatorica , 10 : 41–51 , doi :10.1007/BF02122694, MR  1075065
  9. ^ Пах, Янош ; Тардос, Габор (2002), «Распутывание многоугольника», Discrete & Computational Geometry , 28 (4): 585–592 , doi : 10.1007/s00454-002-2889-y
  10. ^ Бозе, Просенжит ; Дуймович, Вида ; Уртадо, Ферран ; Лангерман, Стефан ; Морин, Пэт ; Вуд, Дэвид Р. (2008), «Полиномиальная граница для распутывания геометрических планарных графов», Дискретная и вычислительная геометрия , 42 (4): 570–585 , arXiv : 0710.1641 , doi : 10.1007/s00454-008-9125-3
  11. ^ Цибулка, Йозеф (2009), «Распутывание многоугольников и графов», Дискретная и вычислительная геометрия , 43 (2): 402– 411, arXiv : 0802.1312 , doi : 10.1007/s00454-009-9150-x
  12. ^ Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander (2009), «Распутывание планарного графа», Discrete & Computational Geometry , 42 (4): 542– 569, arXiv : 0709.0170 , doi : 10.1007/s00454-008-9130-6
  13. ^ Кано, Хавьер; Тот, Чаба Д.; Уррутия, Хорхе (2014), «Конструкции верхних границ для распутывания планарных геометрических графов», SIAM Journal on Discrete Mathematics , 28 (4): 1935–1943 , doi :10.1137/130924172, MR  3277216
  14. ^ Вербицкий, Олег (2008), «О сложности обфускации планарных графов», Теоретическая информатика , 396 ( 1– 3): 294– 300, arXiv : 0705.3748 , doi : 10.1016/j.tcs.2008.02.032 , MR  2412266
  15. ^ Эппштейн, Дэвид (2014), «Рисование графов расположения в небольших сетках, или как играть в планарность», Журнал алгоритмов графов и приложений , 18 (2): 211– 231, arXiv : 1308.0066 , doi : 10.7155/jgaa.00319 , MR  3213195
  • Planarity.net — оригинальная Flash-игра
  • Система NetLogo — Включена как пример программы (игры) в систему NetLogo
  • Planarity — версия с использованием SVG и библиотеки JavaScript d3
  • Multitouch Planarity — многопользовательская версия с поддержкой мультитач, написанная на Python с использованием libavg.
Взято с "https://en.wikipedia.org/w/index.php?title=Планарность&oldid=1235979006"