Сравнение булевых матриц - PullRequest
Новая
       19

Сравнение булевых матриц

3 голосов
/ 21 января 2012

У меня маленькая проблема. Мне нужно сравнить один двумерный массив, заполненный единицами и нулями (давайте назовем это Матрица A - нули фактически представляют собой пустые места, а единицы - позиции футболистов на поле) с множеством других матриц, заполненных по-разному (но опять же, только единицы и нулями) и в результате должно быть указано, какая из матриц наиболее похожа на Матрицу А. Под сходством я подразумеваю сходство в распределении (или позиционировании) игроков на поле, поэтому матрица с расстановкой игроков наиболее похожа на Матрица А будет выбрана для дальнейшего материала.

Может ли кто-нибудь помочь с этой алгоритмической проблемой?

Я пишу это на с ++, но достаточно псевдокода. Проблема только в алгоритме сравнения. Лучше всего, если выходные данные функции сравнения будут выглядеть примерно так: similarity coefficient, которые я могу сохранить в массиве, а затем выбрать наиболее похожую матрицу, используя ее. Но я просто не могу придумать какой-то алгоритм для сравнения подобия.

РЕДАКТИРОВАТЬ: некоторые пояснения о сходстве и алгоритме скопированы из моих комментариев ниже -

Матрица A - Матрица A , Матрица 1 - Матрица1 , Матрица 2 - Матрица2 , У обоих есть 1 изменение по сравнению с Матрицей A, но для меня - матрица 2 должна быть «более похожей» - потому что игрок стоит ближе к своей позиции в матрице A

Матрицы считаются размером около 8х6 или что-то в этом роде, они должны быть достаточно быстрыми - они будут вычисляться каждый игровой цикл (то есть каждые 20 мс или около того), и на каждой стороне будет по 5 игроков.

Ответы [ 3 ]

1 голос
/ 21 января 2012

Матрица ноль / одна не хорошее представление для ваших потребностей.

Вам небезразлично общее количество игроков смещение . Поскольку число игроков является постоянным, можно представить игровое состояние в виде матрицы, строки которой соответствуют игрокам, а столбцы соответствуют координатам поля. Так, например, для двух игроков {{1,0,0}, {0,0,0}, {0,0,1}} будет {{1,1}, {3,3}}. Учитывая две матрицы состояний игры, A, B, вы можете рассматривать их как векторы и вычислять векторное сходство с любой мерой расстояния (, как эти , также см. Библиотека C ++ ). Один простой вариант - косинусное сходство : dot(A,B) (в вашем случае нормы постоянны.)

0 голосов
/ 21 января 2012

Если вы хотите проверить расстояние между 1 с, это будет немного работы.
И два массива, затем сумма - это дает количество позиций, где два 1 имеют расстояние = 0.
Теперь создайте маску, сдвинув оригинал во всех 4 направлениях ИЛИ их вместе, чтобы получить MASK1. И MASK1 затем сумма, чтобы дать количество позиций, где расстояние = 1.
Вы можете создать еще 4 маски для диагональных сдвигов.
Вы можете взвешивать суммы на разных расстояниях.

Например, если ваш исходный массив
0 0 0 0 0<br> 0 0 0 0 0<br> 0 0 1 0 0<br> 0 0 0 0 0<br> 0 0 0 0 0

Тогда MASK1 будет
0 0 0 0 0<br> 0 0 1 0 0<br> 0 1 0 1 0<br> 0 0 1 0 0<br> 0 0 0 0 0

0 голосов
/ 21 января 2012

Идея возможного простого алгоритма, хотя и не очень надежного, но которого может быть достаточно в вашем случае:

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

Это даст вам для каждых двух матриц количество ячеек, которые будут изменены.

В примере, который вы предоставили в комментарии, согласно этому алгоритму Матрица 1 получит оценку 2, а Матрица 2 получит оценку 8, что означает, что Матрица 1 намного больше похожа на A чем Матрица 2.

...