Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Подскажите какой алгоритм использовать

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




То есть, по сути, нам нужно делать обход в глубину от определенной врешины?

446
03 мая 2014 года
Meander
487 / / 04.09.2011
Да. Но, по моему, в случае взвешенного графа есть оптимизированные алгоритмы.
446
03 мая 2014 года
Meander
487 / / 04.09.2011
Возможно следует разработать композитный алгоритм с использованием поиска в ширину, для того чтобы искать маршруты оптимальные по расходу топлива.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог