Приближенный алгоритм

[Snef]

Возникла проблема определения качества приближенного алгоритма для $NP$ задачи.
Алгоритм является $ 3/2$ приближенным, но меня интересует сколько процентов составляет его результат от максимально возможного, в среднем, на случайных входных данных.
Сейчас я нахожу ответ точным переборным решением, затем на этих же данных запускаю приближенную программу,
нахожу процент, повторяю $n$ раз и нахожу средний процент.

Получается очень долго и только для входных данных небольшого размера.
Можно ли сделать как-нибудь "по-умному" ?

[Zealint]

Вы хотите чего-то непонятного. Погрешность приближённого алгоритма, основанного на вероятностных методах, почти всюду равна 100% (существует разве лишь конечное число тестов, на которых погрешность меньше). Почему? Потому что сходятся они все по вероятности, то есть очень слабо. Вы не можете сделать бесконечного (и даже очень большого) числа итераций, поэтому вынуждены заканчивать вычисления раньше. На очень больших тестах мне (в моих задачах) всегда удавалось завалить любые приближенные алгоритмы на 100%-ю погрешность. В конечном итоге получается такая чепуха: для достаточно больших входных данных, чтобы погрешность приближенного алгоритма была приемлемой, нужно чтобы он работал дольше точного метода.

А если у Вас наборы входных данных конечны, то другой разговор.

А ещё бывают комбинированные алгоритмы: что-то среднее между приближенным и точным. Они разрабатываются конкретно под задачу (не являются универсальными). Так у Вас-то что?

[Snef]

Извините, что путаюсь, просто в первый раз сталкиваюсь с решением NP задачи.
Алгоритм (не универсальный) гарантированно дает ответ 66% от наилучшего, но в среднем на случайных данных получаю 95%. И как я понял при увеличении размера входных данных ответ этого алгоритма будет стремится к 66% ? (Или это зависит от алгоритма, и возможно, что на больших входных данных останутся 95% ?)

[Zealint]

Вообще ничего непонятно. Если он гарантированно дает 66%, то откуда у вас 95%? Наверно, 66% гарантируется при каких-то условиях? Или, как это обычно любят говорить чистые математики, не решившие ни одной практической задачи, "в пределе, когда что-то стремиться к чему-то" будет 66%. Давайте конкретно: какой алгоритм, какое у него доказательство оценки погрешности? Надо разбираться, так как по абстрактным описаниям ничего не ясно.

-- Пн апр 30, 2012 13:20:43 --

Ещё быть может, Вы неправильно его реализовали...

[Snef]

Например, существует 3/2 приближенный алгоритм для задачи о коммивояжере, т. е. решение которое он находит составляет не менее 2/3 от оптимального(в любом случае), как я понял. На практике на случайных данных худший случай (66%) возникает редко, и в среднем получается, что алгоритм работает лучше, или я не прав?

[worm2]

Тут 2 проблемы:
1) Производительность. Получение точного решения можно попробовать ускорить путём применения эвристических методов, гарантирующих результат и чаще всего работающих быстрее полного перебора. Например, метод ветвей и границ.
2) Формализация понятия "случайная задача коммивояжёра". Как мы формируем случайный граф? Например, каждые 2 вершины можно соединять или не соединять с вероятностью 1/2, а вес каждого ребра может моделироваться случайной величиной, нормально распределённой на отрезке [0, 1], а Такая формализация имеет право на существование, но она не единственно возможная. Кого-то, возможно, больше устроит геометрическая 2D- или 3D-модель, когда вершины расположены на плоскости или в пространстве, равномерно распределены в некотором прямоугольнике, кубе или шаре, граф полон, а вес каждого ребра пропорционален евклидовому расстоянию между вершинами. Кому-то важны графы с небольшим числом рёбер, а для кого-то непременно требуется, чтобы отношение весов было ограничено сверху заранее заданной константой. Во всех этих случаях статистики получатся разными. Поэтому вопрос о том, как алгоритм ведёт себя "в среднем" для всех возможных приложений, вообще говоря, не имеет однозначного решения. Хотя после уточнения вероятностного пространства — имеет.

[Snef]

Понятно, большое спасибо! Но как тогда различают приближенные алгоритмы? Например, у меня два 3/2 приближенных алгоритма, но один чаще дает ответ гораздо лучше чем второй, и точно не хуже.

[worm2]

Тут мне Кэп подсказывает, что если на любом примере один работает не хуже, чем другой, а на некоторых лучше, то можно сказать, что один лучше чем другой
Если есть пример, на котором другой лучше, то, строго говоря, нельзя так говорить.
Но нестрого, конечно же, можно. У Вас ведь численный эксперимент. Так и напишите: результаты численного моделирования показывают преимущество такого-то метода перед таким-то. Тем более, что доказательства, я так понимаю, у Вас всё равно никакого нет. Это абсолютно нормальная ситуация.

[Zealint]

worm2 в сообщении #565837 писал(а):

"случайная задача коммивояжёра"

и

Цитата:

приближенный алгоритм для задачи о коммивояжере

это разные вещи.

Всё-таки меня в первую очередь интересует как 66% превращаются в 95%. Ошибка в доказательстве или в логике реализации алгоритма? Или в понимании того, что означает это 66?

Цитата:

Так и напишите: результаты численного моделирования показывают преимущество такого-то метода перед таким-то.

Если бы мне на рецензирование попала статья с такой фразой, я бы дал разгромную рецензию. Тут требуются объяснения. Что такое "преимущество", когда именно (при каких условиях) оно проявляется. Какова степень криворукости кодера, которые программировал алгоритм (можете издеваться, но это почти везде - где мне приходилась копаться в чужом коде - решающий фактор). Каковы тесты. Даже фаза луны может сыграть роль, если у вас генератор случайных чисел от неё работает (шутка).

[Snef]

Ошибка в понимании. 66% превращались в 95% потому, что я проверял только на полном графе, и с весами ребер равными rand().

[Zealint]

Snef в сообщении #565971 писал(а):

Ошибка в понимании. 66% превращались в 95% потому, что я проверял только на полном графе, и с весами ребер равными rand().

Тогда объясните мне, пожалуйста, что значит

Snef в сообщении #565829 писал(а):

т. е. решение которое он находит составляет не менее 2/3 от оптимального(в любом случае)

Самому интересно стало.

[Snef]

Извиняюсь, что Вас запутал, алгоритм Кристофидеса неудачный пример, потому что там ищется наименьший цикл и $ H \leq \frac{3}{2}(H^*)$, где $H$ -ответ алгоритма $H^*$ -оптимальное решение.
У меня же в задаче ищется максимальное решение и $A \geq \frac{2}{3}(A^*)$ (это доказано).
Поэтому, наверно, путаница с процентами.