Задача коммивояжера в 1С #685478

Народ, скажите кто-нибудь сталкивался с решением задачи коммивояжера в 1С? Надо решать такую задачу на 20 точках, полным перебором 1С не вывезет. Может кто подскажет другие способы?

если не получается перенести готовые алгоритмы на 1с, то ИМХО нужно подумать о смене профессии. Если не получается найти готовые алгоритмы в поисквике - тоже.

а задача о коммивояжере решается полным перебором?

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

Решал задачу генетическим алгоритмом (есть еще из достойных муравьиный) На 1с генетический алгоритм выйдет тормознутым. Я логику генетического алгоритма переносил в ком объект на с#

Маршрут из скольки точек планируется оптимизировать?

почему все такие классные, сразу говорят о смене профессии? Если у человека возникла трудность, зато  в другом бм он хорош. а в чем проблема ? нет алгоритма или перенести в 1с?

просто все 1сники гении которых сразу приносят в род дом в желтых коробках с надписью 1с )

да я тоже смотрю и с людьми общаюсь, все их ненавидят гениев ...

Эх, где мои 17 лет... Задача эта рассматривается на младших курсах ИТ-специальностей. Информации о методах решения в сети - вагон, например можно посмотреть здесь

иди отчёт доделай по 7ке

может и хорош, но здесь не форум садоводов:) проблема автора в нежелании искать и чуть думать

ну ты бы показал свой вариант на 1с, который осиливает 10 (5, 3, 2 или сколько он там у тебя осиливает), но не осиливает 20 (ну, и указал бы пирчину, почему не осиливает)

Я делал используя генетический алгоритм. Правда на Delphi, но по сути можно использовать идею и в 1С. Вот видео того, что получилось:

Делай COM DLL и вперед. На 1С вычисление по таким алгоритмам это долго и муторно.

Ради 10 вообще можно нечего не писать и попросить сделать оптимизацию за вас гугл мэп. На 1с будет осиливать и 200 точек только другой вопрос, в том что считать будет больше часа.

Писал такую программу после института, на квикбейсике. Успешно. Алгоритм придумал сам, как называется не знаю. Вообще, тема рассматривалась в СССР как занимательная задача для школьников среднего возраста. По крайней мере, я читал такую книжку и даже примерно помню условие.

Насчет занимательности для школьников это сильно. Думаю, найдете не одну вполне достойную диссертацию на эту или смежную тему.

Решали подобную задачу(не в точности) - подбор суммы максимально близко к заданной из большого количества мелких сумм. Взяли метод ветвей и границ, перенесли в 1С - все ок. Так что мат методы нормально переносятся в 1С.

не знаю-не знаю насчет школьников.. это была моя курсовая на 3 курсе. В 1С делала такое, но очень давно, и на семерке. + там еще была одновременно "задача рюкзака", т.е. надо было не только максимально оптимально проехать маршрут, но и оптимально загрузить газельку под самую "крышечку". Первая часть решилась успешно (по-моему как раз методом ветвей и границ), вторая на практике оказалась невыполнимой. :(

Че эт на младших курсах? У меня диплом по этой теме был. Думаю да, вот так проще будет, чем генетические алгоритмы на 1С реализовывать. Не известно, что эти 20 точек из себя представляют. Но если граф полный, то можно тупо использовать детерминированный спуск в лучшем направлении. Глобально-оптимальное решение не факт что получите, но даже в 1С хоть на 100 точках просвистит так, что раз не успеете сказать.

Это не коммивояжер, а, скорее, рюкзак.

диплом на тему "реализация алгоритма" быть не может. максимум - курсовик, и именно на младших курсах. В составе диплома может быть решение такой задачи, но это не тема диплома, а кусочек одного из методов решения.

Да естественно, тема диплома не назвалась "Решить задачу коммивояжера". Тема была связана с оптимизацией транспортных перевозок. Название уже забыл.

да ладно, в вышках это рассматривают на первых курсах :)

и в твои 17-лет компьютеры были еще у единиц и каждый первый не занимался программированием :)

Что такое Коммивояжер? О_О

Везёт вам, Ребят.. вы программисты :( А подскажите пожалуйста.. а можно дистанционно выучиться на программиста сейчас?

На самом деле, задача по научному называется "задача на экстремум функционала" - вы описываете критерии, по ним строится функционал, а потом ищите его минимум. Просто, чтобы всё взлетело, нужно правильно описать критерии, особенно, если потом из будут между собой сравнивать. Если точек мало, то можно простым перебором через стек, как это писалось для школьников - то есть мы просто имеем стек маршрута и в каждой точке перенумерованные направления в другие точки, которые мы будем перебирать по мере возрастания (ну и сразу исключая возвраты назад).

Если двадцать точек, то перебрать нужно 20! вариантов, а это очень много, но если сразу отбрасывать маршруты с пересечениями, то будет намного меньше.

сейчас им занимается еще меньше народу, ибо специальность не престижная. Не набирает наша кафедра абитуру... Но задачки подобные решали. Как курсовая были на 1 курсе, кому не досталось, те разбирали на третьем в теме целочисленного  программирования - метод ветвей и границ излучался как раз там.

* изучался

По букве "Я" вторая ссылка

Решал методом ближайшего соседа - прост в реализации , быстр ,достаточно точен с точки зрения практического использования , в среднем порядка 8-12 точек на маршруте

Капец, из 30 постов один полезный. spectre1978 - спасибо за ссылку, то что я хотел. А товарищу  Fragster я бы рыло начистил, жаль нельзя это через интернет сделать.

дружище? ты о чем? о том, что в поиске яндекса вторая ссылка - то, что тебе нужно?

о мой ком объект. Только там в обработке в парсере результата есть ошибка. Сам ком объект работает стабильно

Что-то у меня infostart не открывается, можешь обработку еще куда-нибудь выложить или скинуть в romanryt#mail.ru?

капец. выпускник математического факультета ОмГУ.

да не за что, дружище. Мне яндекс открыть пока еще не влом :)