Не совсем понятен принцип свитков. Каждый свиток одноразовый даже если использован на на всю силу? Буду исходить из этого.
Думал бы я примерно так (полный перебор):
1. Рассматривать только имеющиеся в инвентаре свитки. Нет смысла перебирать все возможные варианты.
2. Определить возможное сокращение каждого пути с каждым из свитков. Получится несколько цифр (по количеству типов свитков) для каждого из путей. Это сама по себе не простая задача, т.к. для каждого пути и каждого свитка придётся перебирать варианты, выбирая оптимум для пары путь-свиток.
3 (опционально). Если в следующих пунктах будут проблемы с быстротой счёта, то нужно отобрать только те сокращённые пути, которые максимально отличаются от исходных по длине.
4. Составить все возможные графы из комбинаций путей/сокращённых путей. Их может быть очень много. Сократить тут особо не вижу как - как не крути, нужен перебор всех вариантов (можно с учётом пункта 3 для упрощения, но это риск пропустить оптимум, особенно если есть много слабых свитков). Тут надо не забывать, что свитков ограниченное количество - не имеет смысла рассматривать графы с таким количеством сокращённых путей, на которые не хватит свитков. Кстати, если типов свитков будет меньше, то будет проще.
5. Для каждого из полученных графов решить свою задачу коммивояжёра и выбрать лучший вариант из них.
Примечание: этот вариант не рассматривает использование нескольких свитков на одном пути. Если это надо, то придётся включить во все пункты дополнительное усложнение.
Можно придумать краткий перебор, но он может пропустить оптимум. Зато расчётов намного меньше.
Заочно начать назначать свитки, начиная с самого мощного.
1 (как и в полном переборе). Определить возможное сокращение каждого пути с каждым из свитков. Получится несколько цифр для каждого из путей.
2. Самый мощный заочно отдаётся пути, в котором возможно максимальное сокращение пути.
3. Второй свиток так же отдаётся самому большому сокращению (включая уже сокращённый).
4. И так далее пока все свитки или пути не кончатся.
5. В итоге останется только один граф из путей и сокращённых путей, которые будет или оптимальным или не очень далёким от него. Для него и решаем задачу коммивояжёра.
Примечание: из плюсов то, что в него автоматом встраивается вариант с несколькими свитками за 1 путь.
П.С. Надо ещё понять, насколько нужно оптимальное решение.
Если оно для ИИ-противников, то не будет ли с такими безошибочными ИИ слишком сложно играть?
А для игрока и вовсе интересней ставить задачи, в которых он на основе своего личного скила может оптимизировать пути. Идеальный автопилот может только убить интерес к игре. Разве что такой автопилот будет редким бонусом.