генерировать последовательность ребер
E1,E2, ... , EN
вычислить количество требуемого топлива
distance = d1 + d2 + ... + dN
fuel = F(distance)
или для каждого ребра в отдельности
fuel = fuel1 + fuel2 + ... + fuelN
если топлива хватает
fuel <= fuel_max
то подсчитываем число контрактов
запомнить последовательность вершин данного маршрута и
соответствующее ему число контрактов
повторять все, пока не исчерпаются маршруты
когда все маршруты найдены найти маршрут с максимальным числом контрактов
Подскажите какой алгоритм использовать
Множество городов, обслуживаемых фирмой X представлено графом, вершины которого соответствуют городам, а ребра – соединяющим их маршрутам, при этом длина ребра определяет расстояние между городами. Каждому городу соответствует целое число – количество контрактов, которые могут быть заключены в этом городе. Определить маршрут, которым должен двигаться коммивояжер так, чтобы заключить максимально возможное число контрактов. Подразумевается, что запаса топлива в машине коммивояжера хватит только на ограниченный маршрут.
Так в курсе дискретной математики это описывается. Во многих учебниках дают словесное описание алгоритма. Как правило это всегда перебор с той или иной стратегией. Сначала выбрать все возможные маршруты на которые хватит топлива, а затем среди них найти маршруты с максимальным числом контрактов.
Вот грубый, топорный алгоритм
Вот грубый, топорный алгоритм
Код:
Цитата: Meander
Так в курсе дискретной математики это описывается. Во многих учебниках дают словесное описание алгоритма. Как правило это всегда перебор с той или иной стратегией. Сначала выбрать все возможные маршруты на которые хватит топлива, а затем среди них найти маршруты с максимальным числом контрактов.
Вот грубый, топорный алгоритм
Вот грубый, топорный алгоритм
Код:
генерировать последовательность ребер
E1,E2, ... , EN
вычислить количество требуемого топлива
distance = d1 + d2 + ... + dN
fuel = F(distance)
или для каждого ребра в отдельности
fuel = fuel1 + fuel2 + ... + fuelN
если топлива хватает
fuel <= fuel_max
то подсчитываем число контрактов
запомнить последовательность вершин данного маршрута и
соответствующее ему число контрактов
повторять все, пока не исчерпаются маршруты
когда все маршруты найдены найти маршрут с максимальным числом контрактов
E1,E2, ... , EN
вычислить количество требуемого топлива
distance = d1 + d2 + ... + dN
fuel = F(distance)
или для каждого ребра в отдельности
fuel = fuel1 + fuel2 + ... + fuelN
если топлива хватает
fuel <= fuel_max
то подсчитываем число контрактов
запомнить последовательность вершин данного маршрута и
соответствующее ему число контрактов
повторять все, пока не исчерпаются маршруты
когда все маршруты найдены найти маршрут с максимальным числом контрактов
То есть, по сути, нам нужно делать обход в глубину от определенной врешины?
Да. Но, по моему, в случае взвешенного графа есть оптимизированные алгоритмы.
Возможно следует разработать композитный алгоритм с использованием поиска в ширину, для того чтобы искать маршруты оптимальные по расходу топлива.