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

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

Вступление:

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

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

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

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

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

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

оптимизация

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

Я делаю еще одну запись в базу данных торгов, которая включает кратчайшие пути между моим текущим городом и стартовыми городами всех существующих сделок, которые не являются моим текущим городом, и дают им возврат 0%. Я бы ограничил их тем, где количество городских max_hops меньше, чем max_hops , и я бы также вычислил, будет ли текущий город стартовым городом плюс то, что торгует shortest-path-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 *?
7. Должен ли я предугадывать точки кратчайшего пути в торговой базе данных и максимизировать оптимизацию, или я должен оставить все это для поиска по графику?
8. Можете ли вы заметить что-нибудь, что я мог бы улучшить?

• Почему это решение не работает для алгоритма смены монет?
• i-й элемент k-й перестановки
• Невозможная ошибка в программе, которая выравнивает богатство в группе (UVA 10137, «The Trip»)
• Найти кратчайший путь между двумя статьями в английской Википедии в Python
• Поиск k-го наименьшего элемента в объединении отсортированных массивов

 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