Teleporting Traveller, Оптимальная прибыль со временем Проблема

Question

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

Введение

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

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

---

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

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

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

---

Пока псевдо-решение

Оптимизация

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

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

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

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

Поиск по графику У меня остался (намного) меньший график сделок, осуществимых в течение срока (то есть 30 минут).

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

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

---

Вопрос:

Главным образом,

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

2. Как штрафовать за запуск нового торгового маршрута?

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

На боковой ноте

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

Answer 1

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

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

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

Укажите начальный город, отметьте время в пути как ноль

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 (): внешний цикл выполняет города * максимальное количество прыжков. Внутренний цикл выполняется один раз для каждого города. Выделение памяти не требуется.

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

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

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

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

Answer 2

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

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

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

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

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

Удачи!