Я преподаю курс метаэвристики, и мне нужно создать интересные примеры классических комбинаторных задач для термина «проект». Давайте сосредоточимся на TSP. Мы занимаемся графиками размерностии больше. Я попытался, конечно, сгенерировать график с матрицей затрат со значениями, взятыми из случайногои обнаружил, что (как и ожидалось) гистограмма для стоимости пути (нарисованная путем выборки множества случайных путей) имеет очень узкое нормальное распределение ( является но вокруг ). Это означает, на мой взгляд, что проблема очень проста, так как большинство случайных путей будет ниже среднего, а путь минимальной стоимости очень близок к случайному пути.
Поэтому я попробовал следующий подход: после генерации -матрица, сделайте длинный случайный обход по графику и случайно (Бернулли с ) удвоить или уменьшить вдвое значение ребра. Это имеет тенденцию понижать все значения, в конечном итоге достигая нуля, но если я сделаю только правильное количество шагов, я могу получить распределение с около а также около ,
Мой вопрос, во-первых, это даже хорошее определение для интересной проблемы? В идеале я хотел бы, чтобы экземпляр был мультимодальным (для наиболее распространенных функций соседства) и имел очень мало путей, близких к минимальному значению, так что большинство случайных решений будет очень далеко от оптимального. Второй вопрос, учитывая это описание, как я могу генерировать экземпляры с такими характеристиками?
источник
Ответы:
Один общий подход к созданию более сложных экземпляров заключается в следующем:
Например, для TSP вы можете сделать что-то вроде следующего. Создать случайный экземпляр задачи, выбрав случайныйU(0,1) матрица затрат. Затем настройте экземпляр задачи, чтобы скрыть в нем гораздо лучшее решение: случайным образом выбрать маршрут, который посещает каждую вершину ровно один раз, и уменьшить вес ребер в этом цикле (например, сгенерировать его случайным образом изU(0,c) где c<1 ; уменьшить существующий вес; или изменить существующее ребро с некоторой фиксированной вероятностью). Эта процедура корректировки гарантирует, что оптимальным решением, с большой вероятностью, будет тот специальный тур, который вы выбрали. Если вам повезет, и вы выберете разумное вложение, также будет не так легко узнать, где вы спрятали специальное решение.
Этот подход вытекает из общих идей в криптографии, где мы хотим создать односторонние проблемы с ловушками: где проблему трудно решить без знания секретной ловушки, но со знанием секретной ловушки проблема становится очень простой. Было много попыток внедрить секретные люки в различные сложные проблемы (сохраняя при этом твердость проблемы даже после того, как люк был добавлен), с разными степенями успеха. Но этот общий подход кажется вполне подходящим для ваших целей.
Получающиеся в результате проблемы могут быть сложными , но будут ли они интересны с какой-либо практической точки зрения? Я не знаю. Бьет меня Они выглядят довольно искусственно для меня, но что я знаю?
Если ваша основная цель состоит в том, чтобы выбрать проблемные экземпляры, которые практически актуальны и являются репрезентативными для реальных приложений TSP, я бы предложил совершенно другой подход. Вместо этого начните с обзора реальных приложений TSP, затем найдите репрезентативные экземпляры этих проблем и преобразуйте их в соответствующие экземпляры проблем TSP - так вы работаете с экземплярами проблем, полученными из реальных проблем.
источник
подход, который часто дает вам высокий контроль над природой решений, - это преобразование одной полной задачи NP в другую. теперь вы определяете «интересный» в своем вопросе статистическим способом, но другой аккуратный подход заключается в использовании классических задач из области. мой любимый это факторинг / сат. тривиально найти либо «гладкие» числа с множеством факторов, либо простые числа только с двумя «факторами» (один и простое число). создайте экземпляр SAT для решения факторинга, а решения являются факторами (фактически перестановками факторов, но также не трудно рассчитать заранее).
при таком подходе существует естественное определение «интересных» - трудных случаев, которые не могут быть решены за время P. и этот подход гарантированно приведет к сложным случаям для факторизации негладких чисел, в противном случае он решит главный открытый вопрос в теории сложности, т. е. сложность факторинга .
затем, возможно, перейдите к вашей проблеме, в данном случае TSP. чтобы заполнить этот ответ, было бы неплохо иметь прямое преобразование SAT в TSP, думаю, что они там, но не знакомы с ними. однако в этом вопросе есть некоторые ссылки на факторинг до SAT: сведение задачи целочисленной факторизации к полной проблеме NP
если вам не нравится факторинг, все же может быть предпочтительнее сначала создать экземпляры в SAT по ряду причин. Вы могли бы начать со случайных экземпляров SAT, настроенных по центру в точке перехода легко-трудно-легко, и так далее. или вы можете работать с жесткими экземплярами DIMACS , созданными сообществом. или создавать другие логические "программы" в SAT.
источник