Остовное дерево на гриде с минимальным числом поворотов

Revision ru1, by shaviava, 2018-08-04 17:36:00

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

Поворотом называется пара ребер, имеющих общий конец и направленных перпендикулярно по отношению друг к другу.

Например, на картинке ниже с гридом 4 x 4 (в данном случае прямоугольном, но может иметь любую форму, если рассматривать только подмножество клеток грида) остовное дерева справа (6 поворотов) лучше, чем остовное дерево слева (14 поворотов)

Tags остовное_дерево, граф

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian shaviava 2018-08-05 10:11:40 2 Мелкая правка: 'о слева (14 поворотов' -> 'о слева (15 поворотов'
ru2 Russian shaviava 2018-08-04 17:38:00 18
ru1 Russian shaviava 2018-08-04 17:36:00 686 Первая редакция перевода на Русский
en6 English shaviava 2018-08-03 16:12:07 10 Tiny change: 'Is there an algorithm' -> 'Is there a polynomial algorithm'
en5 English shaviava 2018-08-03 15:56:05 64
en4 English shaviava 2018-08-03 14:42:41 37 Tiny change: 'cted graph.\n\nFor e' -> 'cted graph (not only rectangles are considered).\n\nFor e'
en3 English shaviava 2018-08-03 13:38:23 0 (published)
en2 English shaviava 2018-08-03 13:18:57 88 (saved to drafts)
en1 English shaviava 2018-08-03 13:00:47 546 Initial revision (published)