Помогите пожалуйста найти алгоритм, которым можно было бы решить задачу:
Дано N городов(взвешенный k-близкий граф), в каждом городе продается товар в количестве qi за xi денег/ед и он же покупается за yi. Мы находимся в городе a.
Нужно найти два таких города, что бы (y2*q1-x1*q1)/(d12 + da1) было максимальным.
где x1 — цена покупки в первом городе
y2 — цена продажи во втором городе.
q1 — количество товара доступного для покупки
d12 — вес кротчайшего пути между 1 и 2.
da1 — вес кротчайшего пути между текущим городом и первым городом.
Если говорить словами, то мы сидим в определенном городе и хотим поехать в какой-то город и купить там, что-то, потом поехать в другой и продать там это. Задача: определить путь с максимальной прибылью на 1 километр пути с учетом дороги до пункта покупки (при этом нас не интересует, куда мы поедем после).
Я, к сожалению, лишь поверхностно знаком с методами оптимизации и графами. Укажите в каком направлении копать. Вообще, найденное решение не обязано быть оптимальным, но оно должно быть хорошим. Опять таки сложно сказать, что есть "хорошее" решение, но допустим что-то типа в 95% случаев решение должно быть не менее 90% от оптимального.
Решал задачу в лоб: сортировал вершины по цене продажи и покупки. брал допустим 10000 лучших предложений и там считал расстояния между вершинами. и сортировал по прибыли на единицу расстояния. Проблема, что на границах сети графа разница в ценах очень высокая, но и расстояния огромные. Теряется много решений когда и расстояние очень маленькое и разница цен маленькая, но прибыль на 1км может заметно превышать дальние перевозки.
Нет. Для решения этой задачи можно применить к графу алгоритм Флойда–Уоршелла. После чего по полученной матрице найти в лоб лучшую пару за O(N²). Соответственно, полная сложность решения будет равна сложности алгоритма Флойда–Уоршелла, то есть O(N³).
Здравствуйте, watch-maker, Вы писали:
WM>Нет. Для решения этой задачи можно применить к графу алгоритм Флойда–Уоршелла. После чего по полученной матрице найти в лоб лучшую пару за O(N²). Соответственно, полная сложность решения будет равна сложности алгоритма Флойда–Уоршелла, то есть O(N³).
Да, действительно. Более того расстояния известны заранее и алгоритм Флойда–Уоршелла можно прогнать заранее, а в программе использовать уже готовые данные. Там правда много городов, порядка десятков тысяч, т.е. матрица будет порядка 1-2 гигабайта.
Здравствуйте, ant_katcin, Вы писали:
_>Более того расстояния известны заранее и алгоритм Флойда–Уоршелла можно прогнать заранее, а в программе использовать уже готовые данные. Там правда много городов, порядка десятков тысяч, т.е. матрица будет порядка 1-2 гигабайта.
Ну вроде пара гигабайт — это совсем не много, даже в память разом загрузить обычно можно. Вот со временем хуже. Но если алгоритм Флойда–Уоршелла предназначен для плотных графов, то для разреженных можно использовать более специфические реализации, например такие как алгоритм Джонсона, или даже просто запустить алгоритм A* несколько раз, если получится достать хорошую эвристику (если "города" в задаче соответствуют реальным городам из жизни, то как правило с этим нет проблем).
К сожалению, я не знаком с термином "k-близкий граф", поэтому не могу посоветовать как использовать это свойство.
