Помогите с задачей, (хотя бы хорошей идеи).
Дана матрица n*n переводов валют.
надо написать алгоритм который за n переводов даёт макс выгоду.
Пояснение: мы должны выйти из какой-то валюты и за n переводов вернутся в неё же.
Валюта с которой начинаются переводы выбирается произвольно(ну то есть надо отыскать ещё валюту из которой наиболее выгодно надо начинать производить переводы)
Вывести путь выгоднейшего перевода
(n<=20)
----------------------
комбинаторика умирает на n=10((((

это задача Комивояжора которая до сих пор не решена за полиномиальное время .

не.... вояжёр не подходит.... долго....
надо проверять каждую вершину 
(слишком много модификаций в алгоритме делать)

Это сообщение отредактировал(а) Irdis - 22.5.2008, 00:00

За n переводов? Т.е. за линейное время? Если придумаем, то чур нобелевка мне 
А черт, ведь сейчас буду думать.

Если так, своей выдумкой. Придумал вот что: Если необходимо вернуться в исходную точку за n шагов, то можно попробовать построить в твоей матрице все замкнутые пути (1,1)->(1,1) длины n. И их проверять.
Только я не совсем представляю, как выглядит и работает твоя матрица.

я так понимаю что то вроде: 
__1__2_3 
1 x1 x2 x3
2 y1 y2 y3
3 z1 z2 z3
x1:x3 - стоимость покупки $ из рублей(y), гривен(z)
y1:y3 - стоимость покупки рублей(y) из $, гривен(z)
z1:z3 - стоимость покупки гривен(z) из $, рублей(y)

можно апример включить для начала все переводы валют в цикл , а потом повыбрасывать не выгодные ...



Это сообщение отредактировал(а) v2v - 22.5.2008, 07:11

нет конечно. Из линейнго числа переводов вовсе не следует линейности времени алгоритма.

Решение в лоб - n раз запустить комивояжора. А там видно будет.

Метод ветвей и границ говорят не плохо работает в среднем для решения комивояжора.

Кстати в Кормене можно погрепать "арбитраж" - там похожая задача.

Добавлено через 2 минуты и 16 секунд

Что это такое кстати? 200 йен это круче 198 долларов?

Это сообщение отредактировал(а) Mayk - 22.5.2008, 07:51

это типо, когда мы вернёмся в исходную валюту, у нас будет больше денег чем было изначально
-----
короче вечерком протестю вояжёра

Это сообщение отредактировал(а) Irdis - 22.5.2008, 10:07

А дополнительные ограничения есть? штраф за перевод в %... Я думаю нужно выложить матрицу как я понимаю нам надо быть в плюсе... Кстате цены зафиксированы во времени или иатрица постоянно обновляется?

В условиях релаьного рынка сомнительно, что будет работать.
1000 долларов переведем в валюту подороже(а цена продажи всегда ниже покупки). Оттуда еще продадим. А потом задорого покупать. Сомнительно, что будет  Хотя спортивный интерес уже есть

задача чисто по программированию, никого отношения к реальному миру и личной авторской выгоды не имеет  

ну так я и спрашиваю - что такое больше денег? 

Не. Было 1000 рублей.
Перевел в доллары. Из долларов в евро. Из евро в марки. Марки в рубли. Вот по такой цепочке если проходимся, получается 1050 рублей.

тема закрыта
время O(n^4)

Это сообщение отредактировал(а) maxim1000 - 26.5.2008, 10:43

Плюс. Молодец!