Задача нескольких комивояжеров

Сообщение №477 от Ренат 07 августа 2001 г. 20:19
Тема: Задача нескольких комивояжеров

Приветствую !
Не подскажет ли кто-нибудь, как решить такую проблему:
есть N пунктов (вершин графа), и M коммивояжеров расположенных в произвольных вершинах (задается
в начальных условиях)
как оптимально произвести оповещение всех пунктов
(в одном пункте может побывать не более одного коммивояжера)


Отклики на это сообщение:

> Приветствую !
> Не подскажет ли кто-нибудь, как решить такую проблему:
> есть N пунктов (вершин графа), и M коммивояжеров расположенных в произвольных вершинах (задается
> в начальных условиях)
> как оптимально произвести оповещение всех пунктов
> (в одном пункте может побывать не более одного коммивояжера)

Из каждого пункта, где находится коммивояжер начинаем раздувать
упругую оболочку. Встречая преграду в виде незанятого пункта или
в виде другой оболочки, оболочка фиксируется (отсанавливается.

Т.е это модификация алгоритма эластичной нейронной сети.


А по какому принципу строится оболочка?
Где бы подсмотреть алгоритм работы этой самой эластичной нейронной сети?
А если вес ребра м/д пунктами не расстояние, а время достижения, которое не пропорционально расстоянию (из-за переменной скорости, например) ?


> Приветствую !
> Не подскажет ли кто-нибудь, как решить такую проблему:
> есть N пунктов (вершин графа), и M коммивояжеров расположенных в произвольных вершинах (задается
> в начальных условиях)
> как оптимально произвести оповещение всех пунктов
> (в одном пункте может побывать не более одного коммивояжера)


Что-то на эту тему было в статье Разборова в КТ


> А по какому принципу строится оболочка?
> Где бы подсмотреть алгоритм работы этой самой эластичной нейронной сети?
> А если вес ребра м/д пунктами не расстояние, а время достижения, которое не пропорционально расстоянию (из-за переменной скорости, например) ?

Можно прочитать здесь -

www.univer.omsk.su/~rtf/KOMMIVGR.TEX

более подробно по ссылкам в статье.

Задача ваша интересная, был бы рад познакомиться
с той предметной областью, где она возникла, пишите.


Приветствую !

> Что-то на эту тему было в статье Разборова в КТ

Было да не то, если иметь ввиду упоминание в этой статье "алгоритм С. Ароры (S. Arora) для приближенного решения задачи коммивояжера на плоскости."


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100