Делаю курсовик.
Задание:
Для каждой страны на географической карте известна стоимость перелёта на самолёте в другие страны, однако для каждой страны авиасообщение имеется напрямую не со всеми странами. Вено ли, что из одной страны, выбранной на карте, можно перелететь в другую выбранную страну не менее, чем N способами, не бывая в странах маршрута повторно, и заплатить при этом не более M $ ?

Преподователь сказала, что это np-полная  задача.

Одногруппник нашёл следующую np-трудную задачу, говорит, что она из книги "вычислительные машины и труднорешаемые задачи" (Сам я её не нашёл - впрочем их там много, мог проглядеть). Вот она:
Задан граф G=(V,E) с двумя выделенными вершинами s, t  V, длина L(e) каждого ребра
eE и положительные числа B и K. Существует ли в G K различных путей от s до t, веса которых не превосходят B?

Она идентична моей. В общем получается, что моя задача np-трудная и должна иметь экспоненциальную временную зависимость, однако я решил её и получил полиномиальную зависимость.

s, t - начальный и конечный пункты путешествия (вершины).
Общая схема алгоритма такая:
1. Инициализация:
    заполнил матрицу смежности w[][] стоимостью перелётов (ребра) либо значением INFINITY, если нет связи между двумя вершинами.
2. В цикле, пока "найден путь из s  в t" и "кол-во путей < N" и "стоимость < M"
    2.1  ищем кратчайший путь с помощью алгоритма Дейкстры
    2.2  если найден, то удаляем из графа все рёбра, выходящие из вершин вершин найденного пути (удаление: w[i][j]=INFINITY)
3. возвращаем результаты

Прикинул временную зависимость алгоритма:
В алгоритме Дейкстры я особо не заморачивался, поэтому его временная сложность O(n^2), где n - количество вершин
Цикл 2. в худшем случае выполняется N раз.
Итого: O(N*(n^2))

Получается обычная P-задача. Нестыковочка. 

Вот мой код:


Это сообщение отредактировал(а) Arks - 11.1.2007, 19:01

Что значит "одной из вершин"? 
Рассмотрим

из s в t есть два пути(s,b,c,t & s,b,d,t). Однако, если удалить вершину B, то они не будут найдены.


Это сообщение отредактировал(а) Mayk - 11.1.2007, 18:06

Нормально. Мы можем проходить через 1 вершину только 1 раз (за искл. s & t), так что все нормально.

Это сообщение отредактировал(а) Arks - 11.1.2007, 18:57

"моя задача np-трудная и должна иметь экспоненциальную временную зависимость"

Конечно же не должна.

Откройте любую книжку по графам и отыщите там задачу комивояжера. Почти такая как у вас.... К нижке же все про сложность и хороший алгоритм найдете.

Поиск по разделу по славам задача коммивояжера и орграфы....Тема поднималась не раз....Конкретно твоя задача по нахождению пути в ориентированном графе. 

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

Сколько лет занимаюсь теорией вычислимости - а о таком загадочном определении не слышал.

Можете ссылочку, или док-во привести?  

esperant0, 

Почему?


SoWa, 
~FoX~, 
У меня неориентированный граф, и задача коммивояжёра никак к моему случаю не относится. Точно вам говорю.

Существует алгоритм Йена, но он ищет минимальные отклонения, а не полностью новый путь. Да и в любом случае у него тоже полиномиальное время работы. Мою же программу преподователь не приняла, так как сказала, что моя задача np-трудная (см. сравнение с np-трудной задачей в первом посте) и соответсвенно её решение не может иметь полиномиальную временную зависимость. А у меня так.

Мне надо выяснить, где ошибка. Либо моя задача получается p-задачей (тогда это надо как-то доказать), либо я не верно посчитал временную зависимость, либо мой алгоритм не верен - с чем я как раз не согласен.


Почему? В "вычислительные машины и труднорешаемые задачи" задача есть - указано, что она p-задача:
кратчайший путь между 
двумя вершинами 
УСЛОВИЕ. Заданы: граф 
G = (V, Е), длины l(e)eZ+ для 
всех е s Е, выделенные вершины 
a, ie7 и положительное целое 
число В. 
ВОПРОС. Существует ли в G 
простой путь из а в Ъ, имеющий 
длину не более В? 

А почему должна -то? Нет такой теоремы что должна и не было. Разве что ВЫ ее доказали?

Arks, Блин, я извиняюсь, это я вопрос не до конца дочитал, с утра не проснулся еще.   

esperant0, ну ладно, уломал. Допустимо ещё псевдополиномиальное время.   
Вот, нашёл я свою задачу в книге, сам. Там есть примечание:
Комментарий. Принадлежность этой задачи классу NP не уста- 
установлена. Аналогичная задача о кратчайших циклах также NP- 
трудна. Обе задачи остаются NP-трудными и тогда, когда 
1(е)= 1 для всех ееЕ. То же самое верно для аналогичных 
задач в ориентированных графах. Однако все варианты этой 
задачи могут быть решены за псевдополиномиальное время 
(т. е. время, ограниченное полиномом от |V|, К и log В) и, 
следовательно, за полиномиальное время при любом фиксиро- 
фиксированном значении числа К- Соответствующие перечислительные 
задачи КР-полны. 

Итак, у меня не полиномиальное время, а псевдополиномиальное. Только вот объясните мне, чем полиноми.. отличается от псевдо..? Псевдо, потому что коэффициент K может быть любым? Потому что не постоянен? Просто, даже если K будет == n (кол-во вершин в графе), то максимум получим n^3 -а это никак не экспоненциальное время (2^d, 3^d, ... ) - всё-таки задачи включаются в np-полные за их сложность.
Что такого особенно в псевдополиноми.. так сказать?

Не вдаваясь в подробности псевдополиномиальное это как эспоненциальное время.

Понятно. Вот, что накопал:
Псевдополиномиальное означает, что с увеличением параметров время растёт экспоненциально.