Возможно, кто-то сталкивался...
Есть таблица с прямоугольными ячейками, некоторые из этих ячеек помечены. Если перейти в терминологию задачи коммивояжёра, то левый верхний угол каждой помеченной ячейки — это город, расстояния между городами — реальное расстояние между этими углами (размеры ячеек известны). Есть тестирующий аппарат, который должен остановиться над каждой помеченной ячейкой для её тестирования. Из каждой ячейки можно попасть в любую другую. Задача состоит в том, чтобы протестировать все ячейки с минимальным перемещением тестирующего аппарата.
Особенности:
1) Таблица, то есть не просто разбросанные невесть где точки
2) Начинать нужно с определённой ячейки, но в отличие от классической задачи, здесь совсем не обязательно вернуться в конце в эту же точку. Остановиться можно где угодно.
3) Количество ячеек велико, т.е. от 1 000 до 200 000 (возможно и больше, но критично именно в этих пределах).
Возможно, кто-то может предложить, что в данном случае лучше использовать... Заранее спасибо
...
_bk>Возможно, кто-то может предложить, что в данном случае лучше использовать... Заранее спасибо
Как ты наверняка знаешь, задача коммивояжера является NP-полной, поэтому с таким объемом входных данных решить ее за приемлемое время невозможно.
Так что смотри в сторону приближенных методов. Литературы на эту тему в сети — выше крыши
Здравствуйте Bell, Вы писали:
B>Как ты наверняка знаешь, задача коммивояжера является NP-полной, поэтому с таким объемом входных данных решить ее за приемлемое время невозможно. B>Так что смотри в сторону приближенных методов. Литературы на эту тему в сети — выше крыши
Конечно, я прекрасно понимаю, что пользоваться нужно приближёнными методами. К сожалению, пока не нашёл чего-то, подходящего именно для моего случая. Потому и возник вопрос. Да и с Инетом у меня сейчас напряжёнка, не получается много лазить и искать. Поэтому если всё же удастся предложить что-то конкретное, буду премного благодарен
Здравствуйте _bk, Вы писали:
_bk>Здравствуйте Bell, Вы писали:
B>>Как ты наверняка знаешь, задача коммивояжера является NP-полной, поэтому с таким объемом входных данных решить ее за приемлемое время невозможно. B>>Так что смотри в сторону приближенных методов. Литературы на эту тему в сети — выше крыши
_bk>Конечно, я прекрасно понимаю, что пользоваться нужно приближёнными методами. К сожалению, пока не нашёл чего-то, подходящего именно для моего случая. Потому и возник вопрос. Да и с Инетом у меня сейчас напряжёнка, не получается много лазить и искать. Поэтому если всё же удастся предложить что-то конкретное, буду премного благодарен
Если даш e-mail, то могу выслать статейку с описанием нескольких эвристик. Мож поможет.
Здравствуйте _bk, Вы писали:
_bk>Здравствуйте Bell, Вы писали:
B>>Если даш e-mail, то могу выслать статейку с описанием нескольких эвристик. Мож поможет.
_bk>bk(at)mail.by _bk>И спасибо
