Comments 8
На картинке показана cnf форма, а в тексте ничего про сведение к sat не сказано.
Одно время назад столкнулся с одной задачей, что нужно было написать алгоритм расчета позиций в графе. На написание данного алгоритма ушло очень много времени.
Постараюсь объяснить что за алгоритм, но сначала надо объяснить как всё работает. Если коротко, наш граф пытается сравнить свои значения с исходной строкой.
У нас есть граф, не циклический. Каждая его вершина это команда. Команды бывают двух видов, 1й вид это тип, второй вид это значение. Значения могут группироваться в тип. Тип может содержать свойства, всего их 3, это AND, OR и EMPTY.
Пример такого графа:
Так же может быть так:
Или так:
Если на вход подаётся исходная строка, в виде «int apple;», тогда мы входим в вершину int_declaration, после входим в вершину int и уже сравниваем значение «int» с значением из исходной строки «int», если значения равны, мы переходим на следующее слово в исходной строке и на следующую вершину в графе для их сравнения. Если значения где-то не равны, то мы прерываем цепочку сравнения и считаем что это не int_declaration, иначе если мы сопоставили всё верно, то это int_declaration.
В данном случае type int_declaration: { «int» and «apple» and ";"} = root; соответствует «int apple;».
int_declaration обладает свойством AND.
Если мы захотим добавить float или string, мы можем переписать код в следующем виде:
В данном случае var_type обладает свойством OR, а например вершина name со свойством EMPTY.
Для int_declaration теперь возможный исходный текст выглядят так:
«int apple;»
«float apple;»
«string apple;»
Переходим к алгоритму который нужно создать, в данном случае графы полностью детерминированы, а следовательно позиции где одна вершина может находиться в позиции исходного текстам нам могут быть известны и рассчитаны, нужно написать такой алгоритм, который рассчитывает на какой позиции находится вершина в исходной строке.
Например для type int_declaration: { «int» and «apple» and ";"} = root; мы точно знаем что «int» всегда будет на позиции 0, тогда как «apple» на позиции 1 и ";" на позиции 2. Для свойства AND посчитать позиции вершин не сложно, сложно становится когда появляется OR, теперь может возникнуть такие вершины, позиции которых могут находится одновременно в двух и более позициях одновременно.
Например для такого графа:
type main: { e, ";" } = root;
type e: { t1 or d12 };
type t1: { «t1» };
type d12: { «d1» and «d2» };
Позиция значения ";" может быть 1 или 2, ведь решений два:
«t1;»
«d1 d2;»
Постараюсь объяснить что за алгоритм, но сначала надо объяснить как всё работает. Если коротко, наш граф пытается сравнить свои значения с исходной строкой.
У нас есть граф, не циклический. Каждая его вершина это команда. Команды бывают двух видов, 1й вид это тип, второй вид это значение. Значения могут группироваться в тип. Тип может содержать свойства, всего их 3, это AND, OR и EMPTY.
Пример такого графа:
type int_declaration : { "int" and "apple" and ";"} = root;Так же может быть так:
type int : { "int" };
type int_declaration : { int and "apple" and ";" } = root;Или так:
type int : { "int" };
type name : { "apple" };
type int_declaration : { int and name and ";" } = root;
Если на вход подаётся исходная строка, в виде «int apple;», тогда мы входим в вершину int_declaration, после входим в вершину int и уже сравниваем значение «int» с значением из исходной строки «int», если значения равны, мы переходим на следующее слово в исходной строке и на следующую вершину в графе для их сравнения. Если значения где-то не равны, то мы прерываем цепочку сравнения и считаем что это не int_declaration, иначе если мы сопоставили всё верно, то это int_declaration.
В данном случае type int_declaration: { «int» and «apple» and ";"} = root; соответствует «int apple;».
int_declaration обладает свойством AND.
Если мы захотим добавить float или string, мы можем переписать код в следующем виде:
type var_type : { "int" or "float" or "string" };
type name : { "apple" };
type int_declaration : { var_type and name and ";" } = root;
В данном случае var_type обладает свойством OR, а например вершина name со свойством EMPTY.
Для int_declaration теперь возможный исходный текст выглядят так:
«int apple;»
«float apple;»
«string apple;»
Переходим к алгоритму который нужно создать, в данном случае графы полностью детерминированы, а следовательно позиции где одна вершина может находиться в позиции исходного текстам нам могут быть известны и рассчитаны, нужно написать такой алгоритм, который рассчитывает на какой позиции находится вершина в исходной строке.
Например для type int_declaration: { «int» and «apple» and ";"} = root; мы точно знаем что «int» всегда будет на позиции 0, тогда как «apple» на позиции 1 и ";" на позиции 2. Для свойства AND посчитать позиции вершин не сложно, сложно становится когда появляется OR, теперь может возникнуть такие вершины, позиции которых могут находится одновременно в двух и более позициях одновременно.
Например для такого графа:
type main: { e, ";" } = root;
type e: { t1 or d12 };
type t1: { «t1» };
type d12: { «d1» and «d2» };
Позиция значения ";" может быть 1 или 2, ведь решений два:
«t1;»
«d1 d2;»
Небольшой нюанс
Дело в том, что один из подходов может быть в том, что мы создадим для каждой OR вершины новый граф, где позиции будут существовать только относительно каждого случая где появляется OR вершина и для всех верши. Является худшим решением из-за огромного количества клонирования графов.
Еще один из подходов, мы будем содержать позиции в виде списка, где существует информация о каждой возможной позиции вершины, но что если вершин будет скажем так 1000, как долго перебирать все эти списки?
Третий подход будет в том, что мы на самом деле будем рассчитывать минимальную позицию и максимальную позицию для вершины, тогда та же ";" в последнем примере выше минимально всегда в позиции 1, а максимально в позиции 2, осталось только написать алгоритм.
Еще один из подходов, мы будем содержать позиции в виде списка, где существует информация о каждой возможной позиции вершины, но что если вершин будет скажем так 1000, как долго перебирать все эти списки?
Третий подход будет в том, что мы на самом деле будем рассчитывать минимальную позицию и максимальную позицию для вершины, тогда та же ";" в последнем примере выше минимально всегда в позиции 1, а максимально в позиции 2, осталось только написать алгоритм.
Как-то очень странно, столкнувшись с NP-полной задачей, сразу сдаваться и переходить, как рекомендуется в чеклисте, к эвристикам (т.е. алгоритмам без хоть каких-то гарантированных оценок качества оптимизации).
Ведь можно еще
- Проверить, не попадает ли задача в APX-полные? (если да, то плохо с приближенными алгоритмами, да, но тоже не повод бежать в эвристики сразу).
- Если нет — поискать FPTAS или хотя бы PTAS алгоритмы (NP-полный рюкзак можно оптимизировать сколь угодно точно для любого епсилон за n^2/eps, может уже и дешевле).
- Если нет FPTAS, и PTAS — можно поискать оптимизацию к константной точностью, как в алгоритме Кристофидеса для метрической TSP (ну или даже логарифмической — жадный для упаковки например). Имея гарантии, что решение будет не хуже чем в 3/2 или 1/2 раз хуже, а для почти всех нормальных распределений — что-то близкое к оптимальному — очень даже неплохо и очень часто сгодится на практике вместо точного.
- Можно покопать вероятностные алгоритмы — у них могут быть хорошие оценки в среднем (по качеству, по времени), или оценки «для почти всех исходных данных».
- Можно посмотреть на входные данные внимательно, и понять, что экспоненциальные в худшем случае алгоритмы тут будут хороши и доказуемо полиномиальны в среднем (какое-нибудь динамическое программирование, где набор частичных решений окажется в среднем полиномом или константой) …
…
…
И уж если ничего вообще честного не получится, тогда да, умывайте руки и тащите эвристики.
Если глядя на проблему, вы в состоянии провести анализ задачи на степень аппрокисимируемости, сложность вероятностных алгоритмов для распределения средних входных данных или идентифицировать параметрическую сложность задачи и оценить распределение в среднем на своих данных для параметров, то пожалуй вам не нужны вводные гайды «что делать, если ваша задача может быть NP-полной» :)
Нет, я как раз писал коммент для тех, кто совсем не в курсе теории сложности, для кого даже NP-задачи «плохие, потому что НеПэ». Пусть программист-практик не занимается сводимостями, а просто ищет свою задачу в компендиуме, главное помнить, что тут не ситуация с «двумя стульями» (либо решаем маленькую и точно, либо большую, но без гарантий), и для NP-сложных задач можно ожидать эффективных апроксимаций или вероятностных алгоритмов, возможно для этого просто нужно обнаружить в задаче дополнительные условия (ну или чуть-чуть выкрутить ей руки). Например понять, что TSP на реальных картах скорее всего всегда метрическая, и т.п.
Если честно я даже после вашего комментария ничегошеньки не понял :) что значит плохая/хорошая задача? Либо получается решать, либо нет. Ну вот я вики залез. Прочитал что задача упаковки в контейнеры мол плохая потому что трудная. Ну так если у меня 3 контейнера на практике, я всегда полным перебором её решаю и нет проблемы.
И еще можете пояснить про компендиум, как вообще в нем искать что-то? Там названия какие-то все непонятные)
И еще можете пояснить про компендиум, как вообще в нем искать что-то? Там названия какие-то все непонятные)
Тема интересная, но не смог осилить даже половину. Русский язык автора настолько забористый, что иногда невозможно понять, что он имеет в виду.
Sign up to leave a comment.
Заметки Датасатаниста: что делать, если перед вами оказалась NP-полная задача