Командующий продавец отправляет устаревшие товары на разные рынки

Question

Какую эвристику можно использовать для решения следующей задачи?

Компания Quality Blimps Inc. стремится расширить свои продажи в других городах (N), поэтому они наняли вас в качестве продавца, чтобы он летал в другие города для продажи дирижаблей. Блимпы могут быть дорогими, поэтому вам нужно будет определить, сколько дирижаблей брать с собой в каждой поездке и когда возвращаться в штаб-квартиру, чтобы получить больше. Качественные дирижабли имеют неограниченную поставку дирижаблей.

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

https://www.hackerrank.com/codesprint4/challenges/tbsp

Эта задача похожа на стандартную задачу коммивояжера, но с некоторыми дополнительными хитростями: продавец должен отслеживать как свои собственные расходы на проезд, так и дирижабли ". В каждом городе есть разные цены, по которым продаются дирижабли, но эти цены снижаются в течение его путешествия. Какой бы быстрый алгоритм (т.е. n log n) использовать для максимизации прибыли?

Цены на перевозку предметов в пути делают TSP проще. Если продавец находится в городе A и хочет поехать в B, он может сравнить затраты на прямой переход к B с затратами на возвращение в штаб-квартиру, чтобы сначала получить больше пробелов. То есть дешевле ли получить дополнительный дирижабль B через A или вернуться обратно между ними. Эта проверка создаст серию зацикленных поездок, которые продавец может затем пройти в порядке наибольших доходов. Но что было бы хорошим способом определить эти петли в первую очередь?

Answer 1

Это проблема поиска. Предполагая, что сеть больше, чем может быть решена методом перебора, лучшим алгоритмом будет поиск по дереву Монте-Карло.

Answer 2

Алгоритмы для таких задач обычно бывают типа "запусти решение много раз, выбери лучшее". Также, чтобы выбрать, какое решение попробовать дальше, используйте результаты предыдущих итераций.

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

Answer 3

Это похоже на классическую проблему оптимизации, которую, я знаю, можно решить с помощью алгоритма имитации отжига (работая над тем, что, я думаю, было первым коммерческим использованием имитации отжига, программы автоматического размещения САПР Wintek еще в 1980-х годах). Большинство алгоритмов оптимизации могут справиться с проблемами многих переменных, подобных вашей - вопрос заключается в правильной настройке алгоритма пригодности, чтобы вы получили оптимальное решение (в вашем случае, с наименьшей стоимостью).

Стоит взглянуть на другие алгоритмы оптимизации - у меня просто есть опыт реализации алгоритма имитации отжига.

(Если вы пойдете по пути имитации отжига, вам может понадобиться "Имитация отжига: теория и приложения (математика и ее приложения") П. Дж. Ван Лаарховена и Э. Х. Аартса, но вам придется выследить его, так как его нет в печати (это может быть даже книга, которую я использовал еще в 1980-х).)

Answer 4

Я прочитал оригинальную проблему. Поскольку количество городов велико, невозможно получить точный ответ. Алгоритм аппроксимации - единственный выбор. Как упомянул @maniek, существует множество вариантов АА. Если у вас есть опыт работы с АА, это было бы лучше, вы можете выбрать один из тех, с которыми вы знакомы, и получить приблизительный ответ. Однако, если вы раньше не делали АА, возможно, вы можете начать с возврата с обрезки.

Что касается этой проблемы, вы можете легко получить эти правила сокращения:

1. Принесите как можно меньше дирижаблей. Это означает, что когда вы начинаете со штаб-квартиры и посещаете города A, B,C..., а затем возвращаетесь в штаб-квартиру (вы можете рассматривать это как один раунд), количество принесенных вами блимпов совпадает с количеством городов, которые вы посетите,
2. С продажной ценой становится меньше, когда она становится ниже, чем дорожные расходы, город никогда не будет посещен. Это дает окончание метода возврата.

Вы даже можете сначала применить KNN, чтобы объединить несколько городов, расположенных поблизости. Затем начните со штаб-квартиры и посетите каждую группу.

Подводя итог, это действительно открытая проблема. Там нет лучшего ответа. Возможно, в случае 1 использование обратного отслеживания дает лучший ответ, тогда как в случае 2 лучше всего моделируется отжиг. Достаточно просто подсчитать приблизительный ответ, и есть много способов достичь этой цели. В общем, действительно лучший подход - это написать как можно больше AA, а затем сравнить эти результаты и вывести лучший.