Быстро двумерное сопоставление с образцом

Question

Быстро двумерное сопоставление с образцом

Рассмотрите двумерную сетку (обычная решетка в плоскости). В моих целях, шаблоне или расположении присвоение номеров 1 и 2 к некоторому связанному подмножеству узлов решетки. Например, следующие шоу три отдельных расположения:

.......1.....1....
.222...2.....12...
.111...2.....2....
.222...22...12211.
.......1....11.1..

Я говорю, что маленький шаблон соответствует большому, если маленький может быть повернут или отражен таким образом, что все его числа меньше, чем числа в большем. Например, рассмотрите этот шаблон:

......
.1212.
....2.
......

Это НЕ соответствует крайнему левому расположению выше, потому что это не может быть повернуто или отражено для вписываний 3x3 квадрат. Это ДЕЙСТВИТЕЛЬНО соответствует среднему расположению, потому что это может быть повернуто и отражено для установки внизу. Это, однако, не соответствует самому правому расположению, потому что однако это повернуто или отражено для помещений в самое правое расположение, число больше в маленьком шаблоне, чем большое расположение. (Если какой-либо из моих примеров неясен, или Вы нуждаетесь в большей информации, просто спрашиваете далеко в области комментариев. Некоторые разъяснения заранее: шаблон не может быть расширен, и он не может быть повернут так, это является диагональным относительно сетки. Это означает, что существует четыре вращения и четыре общих количества отражений, каждый из которых может быть переведен.)

Я задаюсь вопросом о следующих вопросах:

Как я могу быстро протестировать, если маленький шаблон соответствует большому расположению?
Предположим, что у меня есть много маленьких шаблонов. Я могу предварительно обработать их так или иначе, чтобы быстро сказать, соответствует ли по крайней мере один из них расположению?

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

5

algorithm data-structures 2d pattern-matching

задан A. Rex 11 February 2010 в 07:33

1 ответ

Другие вопросы по тегам:

algorithm data-structures 2d pattern-matching

Похожие вопросы:

score 6 · Accepted Answer

Можно использовать модуль heapq .

>>> from heapq import heapify, nlargest
>>> l = [9,1,6,4,2,8,3,7,5]
>>> heapify(l)
>>> nlargest(3, l)
[9, 8, 7]
>>>

-121--1510391-

Решение с помощью sepp2k - это путь. Однако если атрибуты @ никогда не меняются после инициализации и вам нужна скорость, то вы можете сделать это таким образом:

class User
  def initialize
    @attributes = {"sn" => "Doe", "givenName" => "John"}
    @attributes.each do |k,v|
      self.class.send :define_method, k do v end
    end
  end
end

User.new.givenName # => "John"

Это генерирует все методы заранее...

-121--2592723-

2D сверток.
(сложность - n * Log (n), где n в количестве элементов) и может быть хороша для больших матриц.

Сделайте обе матрицы совпадающими и не совпадающими по размеру.

Тестирование для каждого номера отдельно. Пример - номер щеки k В матрице serchung (больше) набор числа > = k на 0 другие значения на 1
В матрице паттерена установлены значения < = k на 1 другом наборе на 0

Где результат свертки 0 попадает и соответствует

Проверьте для каждого вращения и рефлексии (8 итог)

Это означает, что общая совокупность k n регистраций (n) где k - число чисел (в вашем случае 2) и n число элементов большой матрицы)