Телепортирующийся Путешественник, Проблема оптимальной прибыли с течением времени

Question

Я новичок во всей проблеме коммивояжера, а также в stackoverflow, поэтому дайте мне знать, если я скажу что-то не совсем правильное.

Вступление:

Я пытаюсь закодировать оптимизированный по прибыли / времени алгоритм множественной торговли для игры, в которой задействовано несколько городов (узлов) в пределах нескольких стран (областей), где:

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

---

Параметры вопроса:

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

• Я пытаюсь найти оптимальную прибыль за определенный заданный промежуток времени (т.е.30 минут)
• Акт переезда в новый город фактически происходит одновременно
• Обычно требуется такое же определенное количество времени для перемещения по карте города (т.е.2 минуты)
• Акт инициирования первой или любой новой сделки занимает столько же времени, сколько пересечение одной карты города (т.е.2 минуты)
• Моя отправная точка, возможно, на самом деле не имеет действительной сделки ( мне пришлось бы отправиться в первую / ближайшую / лучшую).

---

Псевдо-Решение До Сих Пор

Оптимизация

Во-первых, я понимаю, что, поскольку у меня есть ограничение на время, которое требуется, и я знаю, сколько времени занимает каждый переход (включая -1 для начала сделки), я могу ограничить график всеми сделками, чьи переходы меньше или равны max_hops=int(max_time/route_time) -1.Я вырезал элементы торговой базы данных, которые не укладываются в этот срок, отсекая города, длина кратчайшего пути которых превышает max_hops.

Я делаю еще одну запись в базе данных trades, которая включает кратчайшие пути между моим текущим городом и городами начала всех существующих сделок, которые не являются моим текущим городом, и даю им возврат в размере 0%.Я бы ограничил их тем, что количество городских переходов меньше, чем max_hops, и я бы также подсчитал, превысит ли текущий город начальный город плюс тот, который торгует переходами по кратчайшему пути max_hops и удалите те, которые превысили этот лимит.

Затем я беру оставшиеся сделки, которые не (current_city->starting_city) и добавьте торговые маршруты с возвратом 0% между всеми городами назначения и отправления, где хмель не превышает max_hops

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

Поиск по графу Я остаюсь с (намного) меньшим графиком сделок, возможных в течение установленного срока (т.е.30 минут).

Поскольку все подключенные узлы являются смежными, все соединения по умолчанию имеют вес 1.Я делю % доходности на количество переходов в сделке, затем беру обратное и добавляю + 1 (это будет означать вес 1,01 для 100% возврата).В случае, когда доходность равна 0%, я добавляю ...2?

Затем он должен вернуться по наиболее выгодному маршруту...

---

Этот Вопрос:

В основном,

1. Как мне добавить возможность выбирать несколько маршрутов, когда у меня остались деньги или место, и сохранить поиск маршрутов через path дискретным для отдельных торговых маршрутов?Из-за характера товаров, продаваемых по разным ценам и в разных количествах в пределах города, было бы много пересекающихся маршрутов.

2. Как я могу наказать за инициирование нового торгового маршрута?

3. Полезен ли вообще поиск по графу в этой ситуации?

На Дополнительном примечании,

3. Какие виды черносливов / оптимизаций графика я должен (или не должен) вносить?
4. Правильный ли мой метод взвешивания?У меня такое чувство, что это придаст мне непропорциональный вес.Должен ли я использовать фактическую доходность вместо процентной доходности?
5. Если я кодирую на python, есть ли такие библиотеки, как python-граф подходит для моих нужд?Или это сэкономило бы мне много накладных расходов (как я понимаю, алгоритмы поиска по графу могут быть трудоемкими с точки зрения вычислений) на написание специализированной функции?
6. Лучше ли мне использовать поиск * ?
7. Должен ли я предварительно вычислять точки кратчайшего пути в торговой базе данных и максимально оптимизировать или мне следует оставить все это поиску по графу?
8. Можете ли вы заметить что-нибудь, что я мог бы улучшить?

Answer 1

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

Одной из целей было бы максимизировать прибыль при ограничении кошелька и товаров.Если путешественник должен вернуться домой, это выглядит как экскурсия, если нет, то это похоже на тропинку.Поскольку вы не требовали, чтобы путешественник посещал КАЖДЫЙ узел, это НЕ TSP.Это хорошо - проблемы с кратчайшим путем, как правило, решать намного проще, чем TSP.

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

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

Вот такой Ссылка к аналогичной проблеме при составлении бюджета капитала.

Удачи !

Answer 2

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

Вместо этого, как насчет простого поиска по ширине?

Создайте список всех городов, отметьте их как не посещенные

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

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O():внешний цикл выполняет города * максимальное время переходов.Внутренний цикл выполняется один раз для каждого города.Выделение памяти не требуется.

Теперь по каждому городу посмотрите, что вы можете купить здесь и продать там.Рассчитывая норму доходности по сделке, помните, что рост является экспоненциальным, а не линейным.Удвоенная прибыль от сделки, которая занимает в два раза больше времени, равна НЕ хорошая сделка!Посмотрите, как рассчитать внутреннюю норму доходности.

Если в текущем городе нет торговли, не утруждайте себя полным анализом, просто просмотрите соседей и вместо этого проведите анализ по ним, добавляя единицу ко времени каждого перемещения.

Если у вас есть свободные циклы процессора (а вы вполне можете это сделать, все, что предназначено для игры человека, будет занимать довольно небольшое пространство данных), вы можете запустить анализ по каждому городу, добавив время, необходимое для того, чтобы добраться до города.

Редактировать:Судя по вашему комментарию, у вас есть тонны доступной мощности процессора, поскольку игра не запущена на вашем процессоре.Я придерживаюсь своего решения:Проверь все.Я сильно подозреваю, что получение маршрута и торговой информации займет больше времени, чем вычисление оптимального решения.