Алгоритм выбора групп схожих предметов в 2d массиве

Question

Существует 2d массив элементов (в моем случае они называются Intersections).

Определенный предмет дается в качестве начала. Задача состоит в том, чтобы найти все предметы, прямо или косвенно связанные с этим предметом, которые удовлетворяют определенной функции.

Итак, основной алгоритм такой:

Добавить начало в список результатов. Повторяйте до тех пор, пока не будет внесено никаких изменений: добавьте каждый элемент в массиве, который удовлетворяет функции, и коснитесь любого элемента в списке результатов в списке результатов.

Моя текущая реализация выглядит так:

private IList<Intersection> SelectGroup (
    Intersection start,
    Func<Intersection, Intersection, bool> select)
{
    List<Intersection> result = new List<Intersection> ();

    Queue<Intersection> source = new Queue<Intersection> ();
    source.Enqueue (start);

    while (source.Any ()) {
        var s = source.Dequeue ();
        result.Add (s);

        foreach (var neighbour in Neighbours (s)) {
            if (select (start, neighbour)
                && !result.Contains (neighbour)
                && !source.Contains (neighbour)) {
                source.Enqueue (neighbour);
            }
        }
    }

    Debug.Assert (result.Distinct ().Count () == result.Count ());
    Debug.Assert (result.All (x => select (x, result.First ())));

    return result;
}

private List<Intersection> Neighbours (IIntersection intersection)
{
    int x = intersection.X;
    int y = intersection.Y;

    List<Intersection> list = new List<Intersection> ();

    if (x > 1) {
        list.Add (GetIntersection (x - 1, y));
    }
    if (y > 1) {
        list.Add (GetIntersection (x, y - 1));
    }
    if (x < Size) {
        list.Add (GetIntersection (x + 1, y));
    }
    if (y < Size) {
        list.Add (GetIntersection (x, y + 1));
    }

    return list;
}

(Функция select принимает начальный элемент и возвращает истину, если второй элемент удовлетворяет.)

Это делает свою работу и оказалось достаточно быстрым для обычных размеров массива (около 20 * 20). Тем не менее, я заинтересован в дальнейших улучшениях. Есть идеи?

Пример (X удовлетворяет по отношению к другим X s, . никогда не удовлетворяет):

....
XX..
.XX.
X...

В этом случае есть 2 группы: центральная группа из 4 предметов и группа из одного предмета в левом нижнем углу. Выбор группы (например, с помощью начального элемента [3, 3]) возвращает первый, в то время как последний может быть выбран с использованием исходного элемента и единственного возвращаемого значения [1, 4].

Пример 2:

.A..
..BB
A.AA

На этот раз 4 группы. Группы 3 A не связаны, поэтому они возвращаются как отдельные группы. Большие группы A и B связаны, но A не относится к B, поэтому они возвращаются как отдельные группы.

Answer 1

Шаг 1: тривиальное изменение для огромной выгоды
Простое, немедленное улучшение: и ваше членство result.Contains и source.Contains относится к списочным типам, поэтому они будут O (n) вразмер этих списков не очень эффективен.Поскольку вы действительно не заботитесь о каком-либо конкретном порядке, я бы изменил оба из них на HashSet для поиска в постоянном времени.
Обратите внимание, что вашей текущей реализацией будет O (n ^ 2) в худшем случае,что происходит, когда весь массив действителен (к тому времени, когда вы вставляете последние несколько элементов, вы будете проверять каждый из них по всей остальной части сетки).

Шаг 2: дальнейшая оптимизация
Улучшение структурных изменений: оставьте логический массив visited того же размера, что и ваш массив пересечений, и каждый раз, когда вы смотрите на IntersectionОтметьте его как посещенный.Таким образом, вам не нужно каждый раз проверять, есть ли что-то в result или source, и что еще лучше, вам не нужно переоценивать свой предикат select.Иначе, учитывая что-то вроде этого:

XXX
X.X
XXX

вы бы оценили select по центральной точке четыре раза, что может быть плохо, если это дорого.Таким образом, ваше условие

if (select (start, neighbour)
  && !result.Contains (neighbour)
  && !source.Contains (neighbour))

превращается в: if (!visited(neighbour) && select(start, neighbour), которое будет оценивать select не более одного раза на любом данном перекрестке.
Кроме того, если вы сделаете это, вы не будетедаже нужно делать хэши result и contains, так как вы не будете проверять их.

Answer 2

Основываясь на ответе Цамана, я использовал HashSet. Поскольку очередь не поддерживает хэширование, я обнаружил улучшение, которое требует только поиска в списке результатов вместо списка результатов и источника:

HashSet<Intersection> result = new HashSet<Intersection> ();
result.Add (start); // need to add first item in advance

Queue<Intersection> source = new Queue<Intersection> ();
source.Enqueue (start);

while (source.Any ()) {
    var s = source.Dequeue ();

    foreach (var neighbour in Neighbours (s)) {
        if (select (start, neighbour) && !result.Contains (neighbour)) {
            result.Add (neighbour); // add immediately to hashset
            source.Enqueue (neighbour);
        }
    }
}

Answer 3

Я не очень хорош в C #, но, читая описание вашего алгоритма, я могу предложить вам несколько советов:

1 / Знаете ли вы динамическое программирование или алгоритм Беллмана?Идея состоит в том, что для каждой итерации вы получаете только самый новый результат и продолжаете поиск. Динамическое программирование

Например:

1-я итерация: x1, x2

2-я итерация: x3, x4

третья итерация, вы только ищете и сравниваете обратно с x3 и x4.Это сэкономит вам массу вычислений и итераций процессора

2 / Используйте HashSet для более удобного поиска и получения данных, содержащих