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

Я плохо знаком с целой проблемой коммивояжера, а также stackoverflow таким образом сообщают мне, говорю ли я что-то, что не совершенно правильно.

Введение:

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

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

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

Там уже существует база данных в памяти (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. Я делюсь, %return по количеству транзитных участков в торговле затем берут инверсию и добавляют + 1 (это означало бы вес 1,01 для 100%-го маршрута возврата). В случае, где возврат составляет 0%, добавляю я... 2?

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

Вопрос:

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

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

2. Как я штрафую инициирование новый торговый путь?

3. График является поиском, даже полезным в этой ситуации?

На ноте стороны,

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