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