Я работаю с сеткой квадратов, которые имеют два состояния: «ВКЛ» и «ВЫКЛ». У меня есть довольно простой алгоритм маркировки подключенных компонентов , который находит все компоненты «ВКЛ». Обычно, но не всегда, есть только один компонент «ВКЛ».
Я хочу построить алгоритм, который принимает в качестве входных данных матрицу ячеек включения / выключения, маркировку компонента (вероятно, отформатированную как список хэш-наборов ячеек) и список ячеек, которые изменились с момента формирования метки и выведите новую маркировку. Очевидное решение - просто пересчитать с нуля, хотя это неэффективно. В общем, список ячеек, которые изменились, будет небольшим.
В случае, если список изменений состоит только из включенных ячеек, это легко сделать:
Groups G;
Foreach changed cell C:
Group U = emptygroup;
U.add(C);
Foreach Group S in G:
if (S contains a cell which is adjacent to C)
G.Remove(S);
U.UnionWith(S);
G.add(C);
Однако, если изменения содержат какие-либо отключенные ячейки, я не уверен, что делать. Имейте в виду, что все ячейки ON должны быть членами ровно одной группы. Таким образом, одним из решений было бы взять каждую ячейку, которая смежна с новой ячейкой OFF, и посмотреть, связаны ли они друг с другом (например, используя * pathfinding). Это приведет к 1-4 смежным группам (если только ячейка не была единственной ячейкой в своей группе и, следовательно, имеет 0 соседних ячеек для проверки, и в этом случае она дает 0 групп). Тем не менее, это только немного лучше, чем начинать с нуля, так как обычно (но не всегда) соединять эти смежные квадраты примерно так же трудно, как просто найти смежную группу (если у кого-то нет предложений для умного способа сделать это). Кроме того, это немного страшно, если есть много измененных ячеек ... хотя я признаю, что обычно их нет.
Контекст, для тех, кто настаивает на знании, почему я делаю это:
Единственное правило в загадках Nurikabe состоит в том, что у вас может быть только 1 непрерывная группа стен. Упрощение проблемы, которую я пытаюсь решить, чтобы получить увеличенную скорость (и играть с поиском пути) выше. По сути, я хочу проверить наличие смежных стен, не тратя впустую информацию, полученную в результате предыдущих таких испытаний. Я пытаюсь увидеть, сколько мест в моем решателе я могу использовать предыдущую информацию, чтобы повысить скорость, поскольку кажется довольно болезненным использовать алгоритм O (f (N)), когда O (f (Δ)) алгоритма будет достаточно (N - размер головоломки, а Δ - изменения, внесенные с момента последнего запуска алгоритма).
Профилирование означает , что улучшение этого алгоритма будет влиять на время выполнения, но это проект для удовольствия, а не для получения прибыли, так что на самом деле это не имеет большого значения, кроме возможности измерить, оказало ли изменение какое-либо влияние.
Примечание:
Я пропустил объяснение моего текущего алгоритма, но в основном он работает, выполняя основанный на стеке алгоритм Flood Fill для первого найденного квадрата ON, затем проверяет, есть ли еще квадраты ON (что означает, что это более чем одна группа, которую он не удосуживается изучить).
Редактировать : Идея улучшения: предложения Яирчу и Джона Кугельмана кристаллизовались в моей голове в этом улучшении, которое на самом деле не является решением этой проблемы как таковым, но может сделать эту часть кода и несколько другие части кода работают быстрее:
токовая петля:
foreach (Square s in m.Neighbors[tmp.X][tmp.Y])
{
if (0 != ((byte)(s.RoomType) & match) && Retval.Add(s)) curStack.Push(s);
}
Идея улучшения:
foreach (Square s in m.NeighborsXX[tmp.X][tmp.Y])
{
if (Retval.Add(s)) curStack.Push(s);
}
Для этого потребуется поддерживать несколько экземпляров m.NeighborsXX (по одному для каждого типа соответствия, который необходимо улучшить) и обновлять их все при изменении квадрата. Мне нужно было проверить это, чтобы увидеть, действительно ли это помогло, но это похоже на стандартный случай обмена некоторой памяти на некоторую скорость.