@Igorh1997

Здравствуйте
Мне необходимо написать программу которая будет находить кратчайший маршрут между заданными точками и возвратом обратно ( но конечно лучше что бы возврат и не возврат тоже был настраиваем) ( но в отличии от относительно легкой задачи коммивояжёра тут я могу проходить через вершину больше чем один раз ( естественно если этот путь становится более оптимален) и если получится то поставить ограничения на порядок (ну к примеру есть 10 вершин и мне надо посетить все начиная с 1 но 5 вершину я смогу посетить только после 6)) и всё это было реализованно черех нейронную сеть которая будет обучаться через эвристический алгоритм ( генетический или муравьиный как по мне самый эффективный)

извиняюсь что не очень ( а скорее очень неструктурированно и спонтанно) читаемо написал

понимаю что это непростая задачка от вас хотел бы в помощи хотя бы в указании где читать по тому как это решается ибо всё что мне нужно для решения я уже нашел ( или загуглить за 10 мин можно) а вот как эту задачу решить да так что бы можно было ходить по вершинам больше одного раза я найти не смог

заранее спасибо

0

@VTsaregorodtsev

ИМХО, для возможных циклов (петель, т.е. прохода через точку более одного раза) - см на эластичные сетки. На двумерную плоскость с точками бросается "резиновое" кольцо, которое затем растягивается так, чтобы и по точкам пройти, и свою длину при этом минимизировать.
http://www.nature.com/nature/j... 689a0.html
Статья 30летней давности, с тех пор получила почти 1000 цитирований в научной литературе, так что вполне можно найти цитирующую работу, где идея будет вполне нормально изложена (если вдруг исходная статья после регистрации бесплатно отдаваться не будет).
Методы решения системы уравнений-ограничений - могут быть разными. От решения системы диффуров до решения задачи оптимизации с ограничениями (в т.ч. - решения такой задачи градиентным методом).

Для задачи с невозвратом - при любом методе решения (в т.ч. и для обычными для комми алгоритмами решения классической задачи) нужно будет просто потом отрезать самое длинное исходящее из исходного пункта ребро. Или самое длинное из рёбер - если начальный пункт может быть произвольным.

1

@Igorh1997

Просмотрел статью но с английским я на вы и шёпотом так что не сильно помогло.

Почитал по эластичные сети: там точно есть возможность повторного посещения? Ибо я не увидел пока этого.

Почитал про сети Кохонена но там тоже не нашёл что прям точно точно возможны повторные посещения. Я не шибко умный и нейтронными сетями буду в первый раз заниматься поэтому хотел бы точно знать что буду читать то что надо.

И эластичные сети про которые вы говорили это тоже что тут пишут? http://www.intuit.ru/studies/c... 567?page=3

Заранее Спасибо.

0

@VTsaregorodtsev

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

А Кохонен тут вообще никаким местом.

Ага, но их (вернее, оптимизируемые штрафные функции) по-разному можно задавать.
ИМХО, исходный вариант - совсем не самый лучший (очень быстро - на научной конференции в конце 1987г - другими буржуинами были предложены и иная формулировка, и чисто оптимизационный=градиентный способ решения задачи с ограничениями, ну и потом народ тоже не только использовал старое, но и думал над новым).

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

И ещё коммент. За 30 лет могла сильно сдвинуться терминология (и сейчас эласт.сетками вполне может называться нечто иное), ну и горе-переводчики могут часто по-разному переводить буржуинские научные термины.

1

@Igorh1997

Благодарю, пойду изучать.

0