Существует сетка размером N х М . Некоторые ячейки представляют собой острова, обозначенные цифрой «0», а другие - воду . На каждой ячейке с водой есть число, обозначающее стоимость моста, построенного на этой ячейке. Вы должны найти минимальную стоимость, по которой можно соединить все острова. Ячейка соединяется с другой ячейкой, если она имеет общее ребро или вершину.
Какой алгоритм можно использовать для решения этой проблемы? Что можно использовать в качестве метода грубой силы, если значения N, M очень малы, скажем, NxM <= 100?
Пример : на данном изображении зеленые ячейки указывают на острова, синие ячейки указывают на воду, а голубые ячейки указывают на ячейки, на которых должен быть построен мост. Таким образом, для следующего изображения ответ будет 17 .
Изначально я подумал о том, чтобы пометить все острова как узлы и соединить каждую пару островов кратчайшим мостом. Тогда проблема может быть сведена к минимальному остовному дереву, но в этом подходе я пропустил случай, когда края перекрываются. Например , на следующем изображении кратчайшее расстояние между любыми двумя островами равно 7 (отмечено желтым цветом), поэтому при использовании минимального связующего дерева ответ будет 14 , но ответ должен быть 11 (отмечен голубым).
Ответы:
Чтобы подойти к этой проблеме, я бы использовал структуру целочисленного программирования и определил три набора переменных решения:
Для затрат на строительство моста c_ij объективное значение, которое необходимо минимизировать, составляет
sum_ij c_ij * x_ij. Нам нужно добавить в модель следующие ограничения:y_ijbcn <= x_ijдля каждой водной локации (i, j). Кроме того,y_ijbc1должно быть равно 0, если (i, j) не граничит с островом b. Наконец, для n> 1y_ijbcnможно использовать только в том случае, если на шаге n-1 использовалось соседнее водное пространство. ОпределяяN(i, j)как соседние квадраты воды (i, j), это эквивалентноy_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1).I(c)местоположения, граничащие с островом c, это можно сделать с помощьюl_bc <= sum_{(i, j) in I(c), n} y_ijbcn.sum_{b in S} sum_{c in S'} l_bc >= 1,.Для примера задачи с K островами, W квадратами воды и заданной максимальной длиной пути N это модель смешанного целочисленного программирования с
O(K^2WN)переменными иO(K^2WN + 2^K)ограничениями. Очевидно, что это станет трудноразрешимым, поскольку размер проблемы станет большим, но это может быть решено для размеров, которые вам нужны. Чтобы получить представление о масштабируемости, я реализую его на Python с помощью пакета pulp. Давайте сначала начнем с меньшей карты 7 x 9 с 3 островами в конце вопроса:Это занимает 1,4 секунды для запуска с использованием решателя по умолчанию из пакета целлюлозы (решателя CBC) и вывода правильного решения:
Затем рассмотрим полную проблему в начале вопроса, которая представляет собой сетку 13 x 14 с 7 островами:
Решатели MIP часто относительно быстро получают хорошие решения, а затем тратят огромное количество времени, пытаясь доказать оптимальность решения. Используя тот же код решателя, что и выше, программа не завершится в течение 30 минут. Однако вы можете предоставить решателю тайм-аут, чтобы получить приблизительное решение:
Это дает решение с объективным значением 17:
Чтобы улучшить качество получаемых решений, вы можете использовать коммерческий решатель MIP (это бесплатно, если вы работаете в академическом учреждении, и, вероятно, не бесплатно в противном случае). Например, вот производительность Gurobi 6.0.4, снова с 2-минутным ограничением времени (хотя из журнала решений мы читаем, что решатель нашел текущее лучшее решение в течение 7 секунд):
Это фактически находит решение с объективной ценностью 16, лучше, чем OP смог найти вручную!
источник
Подход грубой силы в псевдокоде:
В C ++ это можно было бы записать как
// map = linearized map; map[x*n + y] is the equivalent of map2d[y][x] // nm = n*m // bridged = true if bridge there, false if not. Also linearized // nBridged = depth of recursion (= current bridge being considered) // cost = total cost of bridges in 'bridged' // best, bestCost = best answer so far. Initialized to "horrible" void findBestBridges(char map[], int nm, bool bridged[], int nBridged, int cost, bool best[], int &bestCost) { if (nBridged == nm) { if (connected(map, nm, bridged) && cost < bestCost) { memcpy(best, bridged, nBridged); bestCost = best; } return; } if (map[nBridged] != 0) { // try with a bridge there bridged[nBridged] = true; cost += map[nBridged]; // see how it turns out findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost); // remove bridge for further recursion bridged[nBridged] = false; cost -= map[nBridged]; } // and try without a bridge there findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost); }После первого вызова (я предполагаю, что вы преобразовываете свои 2-мерные карты в 1-мерные массивы для упрощения копирования), он
bestCostбудет содержать стоимость лучшего ответа иbestобразец мостов, который его дает. Однако это происходит очень медленно.Оптимизация:
bestCost, потому что нет смысла продолжать поиск после этого. Если не станет лучше, не продолжайте копать.Общий алгоритм поиска, такой как A *, позволяет намного быстрее выполнять поиск, хотя поиск лучших эвристик - непростая задача. Для более специфичного подхода к проблеме использование существующих результатов по деревьям Штейнера , как предлагает @Gassa, является подходящим решением. Обратите внимание, однако, что проблема построения деревьев Штейнера на ортогональных сетках является NP-полной, согласно этой статье Гэри и Джонсона .
Если «достаточно хорошо» достаточно, генетический алгоритм, вероятно, сможет быстро найти приемлемые решения, если вы добавите несколько ключевых эвристик в отношении предпочтительного размещения моста.
источник
2^(13*14) ~ 6.1299822e+54итерации. Если предположить, что вы можете делать миллион итераций в секунду, это займет всего ... ~ 194380460000000000000000000000000000000000` лет. Эти оптимизации очень необходимы.Эта проблема представляет собой вариант дерева Штейнера, называемого взвешенным по узлам деревом Штейнера , специализированным для определенного класса графов. Компактно взвешенное по узлам дерево Штейнера - это, учитывая взвешенный по узлам неориентированный граф, где некоторые узлы являются терминалами, находит самый дешевый набор узлов, включая все терминалы, который порождает связанный подграф. К сожалению, я не могу найти решателей при беглых поисках.
Чтобы сформулировать целочисленную программу, сделайте переменную 0-1 для каждого нетерминального узла, затем для всех подмножеств нетерминальных узлов, удаление которых из начального графа разъединяет два терминала, потребуйте, чтобы сумма переменных в подмножестве была равна минимум 1. Это приводит к слишком большому количеству ограничений, поэтому вам придется применять их лениво, используя эффективный алгоритм для подключения узлов (в основном, максимальный поток) для обнаружения максимально нарушенного ограничения. Извините за отсутствие деталей, но реализовать это будет сложно, даже если вы уже знакомы с целочисленным программированием.
источник
Учитывая, что эта проблема возникает в сетке и у вас есть четко определенные параметры, я бы подошел к проблеме с систематическим устранением проблемного пространства путем создания минимального остовного дерева. При этом для меня имеет смысл подойти к этой проблеме с помощью алгоритма Прима.
К сожалению, теперь вы столкнулись с проблемой абстрагирования сетки для создания набора узлов и ребер ... следовательно, настоящая проблема этого поста заключается в том, как мне преобразовать мою сетку nxm в {V} и {E}?
Этот процесс преобразования, на первый взгляд, кажется NP-трудным из-за огромного количества возможных комбинаций (предположим, что все затраты на водные пути идентичны). Чтобы обрабатывать случаи, когда пути перекрываются, вам следует подумать о создании виртуального острова.
Когда это будет сделано, запустите алгоритм Прима, и вы должны прийти к оптимальному решению.
Я не верю, что здесь можно эффективно выполнять динамическое программирование, потому что нет наблюдаемого принципа оптимальности. Если мы найдем минимальную стоимость между двумя островами, это не обязательно означает, что мы можем найти минимальную стоимость между этими двумя и третьим островом или другим подмножеством островов, которые будут (по моему определению, чтобы найти MST через Prim) связаны.
Если вы хотите, чтобы код (псевдо или иначе) преобразовывал вашу сетку в набор {V} и {E}, пожалуйста, отправьте мне личное сообщение, и я постараюсь объединить реализацию.
источник