У меня есть окончательный набор плиток, в которых каждое ребро может иметь четыре цвета.Задача состоит в том, чтобы найти максимально возможную квадратную сборку из заданного (конечного) набора этих плиток.Плитка может вращаться.Мне нужно разработать 3 алгоритма для решения этой задачи.Одна полная и две приблизительные.Очевидно, это моя задача для класса Algorithms, поэтому я не спрашиваю о полных решениях (поскольку это было бы несправедливо), а о некоторых направлениях.Я уже разработал своего рода полный алгоритм (с использованием обратного отслеживания - поиск квадрата размера sqrt (n) - если его не удалось найти, попробуйте найти меньший и т. Д.), Но я понятия не имею, как создавать алгоритмы апроксимации.Я думаю, что кто-то будет глупым, который найдет хороший ответ только в определенных случаях, просто чтобы документально подтвердить, что это не очень хороший подход, но все же мне нужен гораздо быстрее, чем возвращение назад и довольно хороший.Также эта проблема NP-трудная?Мой алгоритм обратного отслеживания является экспоненциальным, но это не означает, что лучшего не может быть ...
РЕДАКТИРОВАТЬ: у меня есть полный алгоритм с экспоненциальным временем, может кто-нибудь дать мне несколько советов, как построить какое-то приближениедля этой проблемы с полиномиальным временем или чем-то лучше экспоненциального?
EDIT2: у меня есть идея, что эту проблему можно заменить на задачу сведения графа к квадратному графу сетки (http://mathworld.wolfram.com/GridGraph.html).Тем не менее, существует проблема, если плитки можно расположить таким образом, чтобы построить сетку, но это может быть хорошим началом.Существуют ли, например, жадные или какие-либо другие алгоритмы апроксимации для приведения графа к графу с квадратной сеткой?