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

Question

Родовыми целями

Скажет, у нас есть «небольшая» 10x10 сетка с некоторыми фиксированными узлами @ размещена в случайных позициях

. . . . . . . . . . 
. . . . . . . . . . 
. . . @ . . . . . . 
. . . @ . . . . . . 
. . . . . . . . . . 
. . . . . @ . . . . 
. . . . . . . . . . 
. . . . . . . @ . . 
. . . . . . . . . . 
. . . . . . . . . . 

И у нас есть ~ 30 узлов, стоимость которых зависит от того, что узлы это рядом (с смежности определяется как любой из 8 пунктов, окружающих место). То есть, если мы рассмотрим узлы А и B размещены на карте

. . . . . . . . . .  . . . . . . . . . . 
. . . . . . . . . .  . . . . . . . . . . 
. . A @ . . B . . .  . . A @ . . . . . . 
. . . @ . . . . . .  . B . @ . . . . . . 
. . . . . . . . . .  . . . . . . . . . . 
. . . . . @ . . . .  . . . . . @ . . . . 
. . . . . . . . . .  . . . . . . . . . . 
. . . . . . . @ . .  . . . . . . . @ . . 
. . . . . . . . . .  . . . . . . . . . . 
. . . . . . . . . .  . . . . . . . . . . 

выход А и В может быть различным в этих двух картах, потому что А и В примыкают во второй, но не в первый.

Наша цель состоит в том, чтобы поместить все узлы на карте таким образом, чтобы сумма всех узлов является максимальным (или по крайней мере очень хорошо.)

Дополнительные ограничения для моей конкретной проблемы

1. Существует около 8 'классов' узлов. Все узлы в каждом классе ведут себя одинаково, поэтому это можно использовать для уменьшения пространства поиска.
2. Определенные узлы доминируют над общим значением, поэтому знание этого позволяет мне оптимизировать вокруг этих основных узлов.
3. У каждого узла обычно есть только два или три других класса узлов, которые увеличивают его значение, когда оно смежно с узлом этих классов.
4. Все значения являются ≥ 0.
5. Я хотел бы найти хорошие припадки в считанные секунды .. так что есть некоторые возможности для вычислений, но довольно хорошее решение в течение 5 секунд лучше, чем идеальное решение в 2 дней.

Наивные жадный подход

Что я делаю сейчас принимает простой жадный подход, то подстройка результат.

Я просматриваю все места на сетке и рассматриваю их для всех узлов, которые я еще не разместил, и выбираю лучшее место размещения, которое я нахожу. Если есть несколько «лучших» позиций, я выбираю их случайным образом. Я делаю это до тех пор, пока не будут размещены все узлы.

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

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

Вопрос

Как я могу сделать лучше, чем этот наивный жадный подход?

Я чувствую, что должно быть гораздо лучшее решение, которое учитывает априорную информацию о смежности, но это ускользает от меня. Любые мысли, ссылки или советы будут очень благодарны!

Answer 1

Я работал над алгоритмом для чего-то подобного-ish недавно.

Идея:

Мы хотим, чтобы ограничить наши возможности для того, чтобы выиграть время вычисления (это была моя проблема, потому что я сделал это в 3D)

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

. p . . . . . 
p @ p p . . . 
. p p @ p . . 
. p @ p . . . 
. p p . . . . 
p @ @ p . p . 
p p p . p @ p 

Initialization:

назовём "кластер" массив, который содержит возможные места. Здесь находится массив со всеми p

Для каждого узла, который вам нужно разместить, вы найдете лучший вариант среди этих p; Таким образом, для каждого нового узла вы получили что-то вроде Node: :(Места & значения)

Iteration:

Вы размещаете лучший узел, который будет удалять 1 возможность в кластере и добавить некоторые (в зависимости от уже окружающие узлы)

Теперь вы хотите обновить лучшее место & значение для каждого узла. Но вы можете работать на несколько модифицированных узлах, потому что каждая другая возможность уже вычислена:

. p . . . . . A : recently placed 
p @ p p . . . C : new possibilities/possible changes 
. p p @ p . . 
. p @ p . . . 
. C A C . . . 
p @ @ p . p . 
p p p . p @ p 

Вот, например, только два вычисления необходимо для каждого узла слева. Если новое значение больше => изменить (значение &)

Iterate.

Возможность ошибок:

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

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

Я не могу найти способ сказать, что на английском языке, но на французском языке я называю этот алгоритм «Алгоритм прогрессирования фронта», который является чем-то вроде «Алгоритм Front-Progress Algorithm». Возможно, вы можете найти что-то на основе этого, но я не сделал этого после быстрого поиска.

Я надеюсь, что это вам помогло.