Найти функцию приоритета / алфавитный порядок для отношения элементов высшего порядка

Question

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

У нас есть массив элементов a1,a2,...aN из алфавита E. Предполагая, |N| >> |E|.

Для каждого символа алфавита мы определяем уникальный целочисленный приоритет = V(sym). Давайте определим V{i} := V(symbol(ai)) для простоты.

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

Count(i)->MIN |   V{i} > V{i+1} <= V{i+2}

Другими словами, мне нужно найти приоритеты / перестановку алфавита, для которых количество позиций i, удовлетворяющих условию V{i}>V{i+1}<=V{i+2}, минимально.

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

Учитывая матрицу знаков B размера MxK (в основном B[i,j] из набора {<,>,<=,>=}), найдите функцию приоритета V, для которой:

Sum(for all j in range [1,M]) {Count(i)}->EXTREMUM | V{i} B[j,1] V{i+1} B[j,2] ... B[j,K] V{i+K}

В качестве примера найдите функцию приоритета V, для которой число i, удовлетворяющее V{i}<V{i+1}<V{i+2} или V{i}>V{i+1}>V{i+2}, является минимальным.

Answer 1

Моя интуиция заключается в том, что все варианты этой проблемы окажутся NP-сложными.Поэтому я бы начал искать эвристику, которая дает разумные ответы.Это может потребовать проб и ошибок.

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

Имитация отжига обеспечивает более сложную версию этого подхода, см. Описание http://en.wikipedia.org/wiki/Simulated_annealing.Может потребоваться некоторое экспериментирование, чтобы найти набор параметров, которые, кажется, сходятся относительно хорошо.

Другая идея состоит в том, чтобы искать генетический алгоритм.Основываясь на быстром поиске в Google, похоже, что стандартный способ сделать это - попытаться превратить NP-полную проблему в проблему SAT, а затем использовать генетический алгоритм для этой проблемы.Этот подход потребовал бы превращения этого в проблему SAT некоторым разумным способом.К сожалению, для меня не очевидно, как можно было бы сделать это сокращение.Действительно, в первой версии, которая у вас была, ваша проблема была тесно связана с классической NP-трудной проблемой.Тот факт, что он обозначен как NP-hard, а не NP-complete, свидетельствует о том, что люди не нашли хорошего способа превратить его в проблему SAT.Поэтому, если неясно, как превратить простую версию в проблему SAT, то вряд ли вы тоже решите сложную задачу.

Но вы все равно можете попробовать некоторые варианты генетических алгоритмов.Мутация довольно проста, просто поменяйте местами некоторые элементы.Один из способов объединения элементов состоит в том, чтобы взять 3 перестановки и использовать быструю сортировку, чтобы найти комбинацию следующим образом: сделать произвольный поворот, а затем использовать «большинство выигрышей», чтобы разбить элементы на большие и меньшие.Отсортируйте каждую половину одинаково.

Извините, что не могу просто дать вам подход и сказать: «Это должно сработать».У вас есть что-то похожее на открытый исследовательский проект, и лучшее, что я могу сделать, - это дать вам несколько идей о том, что вы можете попробовать, и это может работать достаточно хорошо.