Задача коммивояжёра

[квит]

Приобрел таки книжку Ершова, красиво сделано, но сложно написано - чем дальше тем он короче объясняет по коду, сам код не дает, иногда приходится сильно думать)))

Реализовал из его примеров задачу коммивояжера - методом муравьиной колонии

tsp1.JPG

[квит]

Свой вариант - методом случайной парной перестановки

tsp2.JPG

[Ирис]

А чем "задача коммивояжера" отличается от классической "транспортной задачи"??

[квит]

Транспортная задача, упрощенно - есть N складов и M магазинов, надо товары из складов развести по магазинам за минимальную стоимость


Задача коммивояжера - надо обойти все города по минимальному маршруту

https://ru.wikipedia.org/wiki/%D0%A2...B0%D1%87%D0%B0

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида.[1][2] Её можно рассматривать как задачу об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году[4]. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем[5]. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

https://ru.wikipedia.org/wiki/%D0%97...80%D0%BE%D0%B4.

Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так:

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

Вскоре появилось известное сейчас название задача странствующего торговца (англ. traveling salesman problem), которую предложил Хасслер Уитни (англ. Hassler Whitney) из Принстонского университета.

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

Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.

В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M. Johnson), которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии.

Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-трудность задачи коммивояжёра. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.

Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Джованни Ринальди (итал. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашек Хватал (чеш. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжёра различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее, чем на 1 % больше оптимальной.

[BOBA]

Квит, а ты где то программистские задачки решал?

[BOBA]

а что кстати за книжка и из какой системы скрины?

[квит]

Сообщение от BOBA

а что кстати за книжка и из какой системы скрины?

А Фавн давал наводку
http://project.megarulez.ru/forums/s...2&postcount=10

система нетлого

[квит]

Сообщение от BOBA

Квит, а ты где то программистские задачки решал?

в смысле, тут, на форуме, или вообще в принципе???)))

какие то где то решал, да

я даже как то школьников немного пообучал в плане подготовки к егэ и к олимпиадам

[квит]

в планах - запилить коммивояжера жадным алгоритмом, отжигом, генетическим)))

[BOBA]

А. Понятно. Почти вдохновился тоже что то порешать.... Как пойдет.

[BOBA]

Почти интересно, а нейросети на коммивояжера, как то на пускаются?

У нас в МИФИ это проходили математики. А я системотехник.... Это другое. То что не пригодилось.

[Tytgrom]

Сообщение от квит

в планах - запилить коммивояжера жадным алгоритмом, отжигом, генетическим)))

У меня прикладной вопрос. Есть 28 точек разбросанных по карте. Координаты точек есть. Нужен оптимальный маршрут последовательного посещения этих точек. Это оно? Или это другое?
Квиту я как-то координаты кидала, но что-то не задалось.

[квит]

Сообщение от BOBA

Почти интересно, а нейросети на коммивояжера, как то на пускаются?

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

улов негусто

упругая нейросеть
https://cyberleninka.ru/article/n/ko...yazhera/viewer

сеть хопфилда
https://www.sibran.ru/upload/iblock/...kerv9775103610

[квит]

Сообщение от Tytgrom

У меня прикладной вопрос. Есть 28 точек разбросанных по карте. Координаты точек есть. Нужен оптимальный маршрут последовательного посещения этих точек. Это оно? Или это другое?
Квиту я как-то координаты кидала, но что-то не задалось.

Слушай, точно, я забыл(((

А скинь еще раз, щас как то все устаканивается постепенно...

[квит]

Сообщение от Tytgrom

У меня прикладной вопрос. Есть 28 точек разбросанных по карте. Координаты точек есть. Нужен оптимальный маршрут последовательного посещения этих точек. Это оно? Или это другое?

да, это оно, можно даже прям сюда скидывай, будем решать в прямом эфире...

программка уже есть)))

[Tytgrom]

Я даю свой маршрут. Последовательность может меняться первая цифра горизонталь, вторая вертикаль
1. Сэнкчуари 3-4
2. Стоянка грузовиков 4-5
3. Ферма Эбернети 5-4
4. Коммуна 9-3
5. Грейгарден 11-8
6. Станция Оберленд 14-8
7. Переулок висельника 16-11
8. Причал 21-10
9. Сомервиль 25-9
10. Стройплощадка 25-14
11. Убежище 88 24-15
12. Джамейка 21-15
13. Ферма Уорвиков 23-21
14. Спектакль 21-23
15. Замок 19-19
16. Норхаден-Бич 13-21
17. Банкер Хилл 12-16
18. Кантри-кроссинг 10-18
19. Лодочный домик 8-14
20. Альянс 8-13
21. Темпаинс 3-11
22. Форпост 1-12
23. Теплица 5-17
24. Потогонка 5-20
25. Ферма Финча 8-20
26. Особняк 9-25
27. Маяк 6-25
28. Коттедж 2-22

И базовая точка "Ресторан" 7-9 (по идее с неё начинаю и в неё возвращаюсь)

С учетом того, что это просто игрушка и там есть "телепортация", так что оптимизация не критична

[квит]

Надо еще, как расстояние считается в этом мире )))

мы из любой точки в любую можем по прямой дойти? - тогда евклидово расстояние

если как такси, по кварталам, только горизонтально/вертикально можем ехать - манхэттеновская метрика

если извилистые тропинки - то нужен граф дорог

[Tytgrom]

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

Как время при телепортации считается я не очень понимаю, но чем дальше, тем дольше летишь (по игровому времени, реальное время только на загрузку локации)

[квит]

Сообщение от Tytgrom

Я даю свой маршрут.

не самый оптимальный)))

tsp_tytgrom.PNG

база - красный квадрат малевича)))

[квит]

мой вариант - визуально примерно как то так

tsp_tytgrom1.PNG


может правда в левом верхнем углу можно еще пооптимизировать

домой доеду, запущу программку

[квит]

т.е. еще есть варианты - из 15 точки идти в 16, тогда может хвост быть
15 16 26 27 28 24 25 18 17 20 19 23 22 21

или из 15 идти в 17, тогда
15 17 16 26 27 28 24 23 25 18 19 20 23 22 21

[BOBA]

А насколько по жизни этот алгоритм в реале лучше живых диспетчеров? В реале же, пробки, заправки, то и сё....

[Tytgrom]

Сообщение от квит

мой вариант - визуально примерно как то так

Вложение 43432


может правда в левом верхнем углу можно еще пооптимизировать

домой доеду, запущу программку

Блин, я лопухнулась. Неправильно оси дала. У меня нулевая точка верхний левый угол (ну т.е. я шла с запада на восток, потом спускалась южнее и следующий ряд)
1 2 3 4

2

3

4

У меня 17 пункт мешается. При чем по игре тоже. Он последний присоединяется

P1460591.JPG

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

[квит]

Сообщение от BOBA

А насколько по жизни этот алгоритм в реале лучше живых диспетчеров? В реале же, пробки, заправки, то и сё....

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

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

вот к примеру, у нас в городе миллионнике доставка питьевой воды в бутылках - от 1000 до 3000 адресов в сутки надо доставить... собственно, проект возник, когда диспетчера перестали справляться... появилась потребность в автоматизации...)))

и в модель все эти особенности - пробки, заправки, пересменки, обед водителя на маршруте - тоже закладываются, есть норматив, например, на обед и есть допуск плюс-минус, который тоже учитывается, условно 30 мин обед +- 10 мин - с этим уже можно работать

ну и в третьих, к ЗК сводятся не только транспортные задачи, много еще какие есть, где пробок нету, а задачу решать уметь надо)))

[квит]

к задаче коммивояжера (ЗК) сводятся задачи:

- выполнение операций станком с чпу - например сверление отверстий в детали в определенных координатах, или пайка схем, - с минимальным суммарным путем перемещения привода станка

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

- в биоинформатике

Секвенирование ДНК. Здесь города представляют собой фрагменты ДНК, а расстояние представляет собой меру сходства между двумя фрагментами ДНК

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

ну и еще куча всяких приложений из разных предметных областей)))

[квит]

Сообщение от Tytgrom

Блин, я лопухнулась. Неправильно оси дала. У меня нулевая точка верхний левый угол (ну т.е. я шла с запада на восток, потом спускалась южнее и следующий ряд)

так это не принципиально, просто зеркально точки отразить, на расстояниях то это не скажется

[квит]

переделал картинку под оси

tsp_tytgrom2.PNG

еще вариант оптимального маршрута:

0 -> 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 26 27 28 24 25 18 17 20 19 23 22 21 -> 0

[Tytgrom]

Спасибо. Попробую. Картинка хорошая получилась.

[квит]

а что за игра то хоть? и зачем там нужно учитывать длину маршрута?

[Tytgrom]

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

Народ вообще без поселений играет, только воюет А я воюю ради ресурсов дя поселений ....

[BOBA]

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

[квит]

Сообщение от BOBA

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

интересно...)))

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

а как это выглядит, что то типа вики? даже пока представить не могу, как опыт хотя бы одного человека, если он специалист широкого профиля , можно структурировать

[BOBA]

Конкретно у фирмы confluence

Да типа вики. И жира для задач

[квит]

Сообщение от BOBA

Конкретно у фирмы confluence

Да типа вики. И жира для задач

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

для задач использовали трелло, ее тоже атласиан перекупил, но пару месяцев назад они сказали, что из рф акаунты будут блокировать, поэтому постепенно переходим на кайтен, вроде отечественная разработка)))

[квит]

Сообщение от квит

в планах - запилить коммивояжера жадным алгоритмом, отжигом, генетическим)))

продолжаем...

"Жадный алгоритм" - идея простая, и для понимания алгоритма и для его реализации - "идём в ближайший непосещенный город"

На псевдокоде:
1. создаем два списка, в первом - посещенные города, начиная с начальной вершины, во втором - оставшиеся точки, из которых будем выбирать и включать в маршрут
Инициализация, в первый пишем вершина0, во второй остальные
listChoosePoints <- Point0
listRestPoints <- listPoints remove Point0

2. В цикле с кол-вом итераций numPoints-2
2.1 берем текущую точку - это последняя из первого списка
2.2 считаем расстояния от нее до всех из второго списка
2.3 находим минимум и соответствующую ему точку
2.4 включаем эту точку в первый список, исключаем из второго

3. После цикла во втором списке осталась одна точка, включаем ее в конец 1го списка

4. Считаем длину маршрута, из последней точки маршрута делаем еще возврат в точку0

[квит]

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

tsp3.JPG

[квит]

На тех же данных Алгоритм случайной перестановки пары вершин находит лучше решение

его длина маршрута - 99 условных километров против 118 у жадного алгоритма

tsp4.JPG

[квит]

Сообщение от квит

его длина маршрута - 99 условных километров против 118 у жадного алгоритма

причем этот результат можно еще улучшить - если развязать пересечение ребер между 2-12 и 13-0

это делает алгоритм 2-Opt
https://translated.turbopages.org/pr...org/wiki/2-opt

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

т.е. из конфигурации
--A..B--
.. \/
.. /\
--C..D--

переходим в конфигурацию
--A----B--
--C----D--

[квит]

Сообщение от квит

причем этот результат можно еще улучшить - если развязать пересечение ребер

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

[Tytgrom]

Я бы в другую сторону закрутила. из 0 в 5 потом 2, а потом 13, далее против круга и из 12 возврат в 0

Потому что не люблю пересечений

ну или 2 - 12 - 13, а в 0 из 8

[квит]

Сообщение от Tytgrom

Я бы в другую сторону закрутила. из 0 в 5 потом 2, а потом 13, далее против круга и из 12 возврат в 0

Потому что не люблю пересечений

ну или 2 - 12 - 13, а в 0 из 8

Это не важно в какую сторону идти, длина маршрута от этого не меняется)))

Сообщение от Tytgrom

Потому что не люблю пересечений

вот алгоритм 2-опт их тоже не любит)))

[квит]

Добавил возможность формирования начального маршрута - либо отсортированного по порядку (вершины идут по возрастанию их id 0,1,2,...), либо в рандомном порядке

после нескольких запусков алгоритм нашел таки оптимальный вариант
tsp5.JPG

[квит]

Сообщение от квит

после нескольких запусков алгоритм нашел таки оптимальный вариант
Вложение 43447

Есть еще лучше, 94 км против 95))) причесал немного код)))

tsp6.JPG

[Tytgrom]

У тебя очень простая схема точек. Добавь пару-тройку пунктов внутри фигуры. Сразу количество вариаантов возрастет

[квит]

у меня же бегунок - кол-во точек можно менять

я этот набор пока не меняю. хочу на нем же еще пару алгоритмов обкатать

надо бы в файл сохранить, но мне лениво заморачиваться)))

[BOBA]

возможно, алгоритмически похоже на поиск решения в дереве игры.

часть алгоритмов - стохастические . допустим, мы среди возможных продолжений графа отберем 10 ближайших, и для каждого варианта построим N чисто случайных продолжений, среди которых отберем самое короткое (или не чисто случайных - а допустим выбирать будем среди нескольких самых коротких). Так - можно будет отобрать статистически - перспективное продолжение. это возможно даст квазиоптимальное решение.

[квит]

Сообщение от BOBA

возможно, алгоритмически похоже на поиск решения в дереве игры.

часть алгоритмов - стохастические . допустим, мы среди возможных продолжений графа отберем 10 ближайших, и для каждого варианта построим N чисто случайных продолжений, среди которых отберем самое короткое (или не чисто случайных - а допустим выбирать будем среди нескольких самых коротких). Так - можно будет отобрать статистически - перспективное продолжение. это возможно даст квазиоптимальное решение.

да, в чем то похоже... даже наверно как ты делал когда то в калахе...

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

хотя какой то вариант ветвей-и-границ для ЗК тоже разработан... т.е. можно строить оценки и отсекать сразу множества решений по веткам...

[квит]

Сообщение от квит

тут может быть проблема, что целевая функция не монотонна...

... и сильно не унимодальна - т.е. не факт, что ты не скатишься в какой нить локальный оптимум

[Afa]

муравьев напустить. пусть пахнут

[Afa]

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

[квит]

Сообщение от Afa

муравьев напустить. пусть пахнут

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

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

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

так что мне в базовом варианте алгоритма кажется, можно значительно его оптимизировать...

[Afa]

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

[Afa]

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

[квит]

Сообщение от Afa

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

ну, обходить, наверное, не обходят, скорее - из них выбираются... )))

мурашей эрланговских например посмотри

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

[BOBA]

Сообщение от квит

да, в чем то похоже... даже наверно как ты делал когда то в калахе...

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

хотя какой то вариант ветвей-и-границ для ЗК тоже разработан... т.е. можно строить оценки и отсекать сразу множества решений по веткам...

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

[BOBA]

что целевая функция не монотонна

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

[квит]

Сообщение от BOBA

Кстати, в реале, запрет на повторное посещение узла возможно не оптимален. не уверен что нет графа, на котором путь с повторным посещением оптимален

с теоретической т.з. - если задача метрическая, граф планарный, расстояние евклидово, - то тогда в силу неравенства треугольника путь между двумя точками всегда короче, чем через третью, поэтому короче идти сразу куда нужно, не заходя в уже посещенную...

в реале тоже - если например, два клиента живут в одном подъезде, то им экономически выгоднее завезти товар на одной машине, чем две гонять, или потом сюда же возвращаться...

исключение - если еще учитывается временное окно доставки, первый ждет товар с утра, второй вечером - тогда выгоднее вернуться, или приехать двумя ТС

[BOBA]

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

[BOBA]

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

[квит]

Сообщение от BOBA

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

ну да, по графу дорог... и это отдельная интересная задача - по матрице расстояний между точками расположить точки в некотором евклидовом пространстве, её я заведу после этой)))

[квит]

Создал)))
http://project.megarulez.ru/forums/s...81#post1190081

[квит]

Сообщение от Afa

вон мурашей эрланговских например посмотри.

эрланговских или лэнгтоновских???)))

Муравей Лэнгтона — это двумерный клеточный автомат с очень простыми правилами, изобретенный Крисом Лэнгтоном[1]. Муравья можно также считать двумерной машиной Тьюринга с 2 символами и 4 состояниями[2].
https://ru.wikipedia.org/wiki/%D0%9C...BE%D0%BD%D0%B0

[Afa]

Сообщение от BOBA

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

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

[Afa]

Сообщение от квит

эрланговских или лэнгтоновских???)))

написаных на erlang. там кода пара экранов. и на слегка тяжелый граф напрыгивает лям процессов, разгрызая задачку

[BOBA]

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

Как то так...

Не судьба посмотреть сильно ли миллионы процессов выжирают память и процессор.

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

[Afa]

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

процессы у эрланга сильно легковесны. но все процы эрланг под себя займёт. и будет молотить на максимальной скорости. у меня сто тыщ в принципе крутилось, на ноуте. норм.

[Afa]

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

[квит]

Сообщение от Afa

написаных на erlang. там кода пара экранов. и на слегка тяжелый граф напрыгивает лям процессов, разгрызая задачку

поискал

нашел что то типа такого
https://www.onworks.net/ru/software/...-for-qtcreator

Это приложение для Linux под названием Erlang Ant Library, последнюю версию которого можно загрузить как erlang_antlib_0.2.14-src.zip. Его можно запустить онлайн на бесплатном хостинг-провайдере OnWorks для рабочих станций.

Загрузите и запустите онлайн это приложение под названием Erlang Ant Library с OnWorks бесплатно.

правильно я понимаю, что там в основном за счет распараллеливания решается? или алгоритмы особые тоже есть?

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

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

[квит]

Сообщение от квит

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

вот придумал модификацию жадного алгоритма - двусторонний жадный)))
не знаю, был ли раньше где то...

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

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

[Afa]

эм. для кютэ? плагин? слушай, даж разбираться не хочу.

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

[квит]

Сообщение от Afa

эрланговские процессы это эквивалент инстансов объектов. эдакий ооп для процесника а не результатника. они легковесны. потому вся фигня что разбивается на много параллельных кусочков собсна и есть особые алгоритмы.

посмотрю, если когда руки дойдут)))
пока пилю свою вариацию жадного)))

[Afa]

Сообщение от квит

посмотрю, если когда руки дойдут)))
пока пилю свою вариацию жадного)))

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

[BOBA]

Квит, просто интересно, на чем в основном пишете?

[квит]

Сообщение от Afa

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

я почитал про эрланг, да, реально надо вникать, я пока на процедурном

[квит]

Сообщение от BOBA

Квит, просто интересно, на чем в основном пишете?

если ты про игрушку, в которой сейчас балуюсь - это нетлого, я ее в учебных целях для себя разбираю, решил на примере ЗК расколбасить)))

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

[Afa]

Сообщение от квит

я почитал про эрланг, да, реально надо вникать, я пока на процедурном

ну вообще двух недель хватает чтобы привыкнуть. тестилось на непривычном к функциональщине

[квит]

Сообщение от Afa

ну вообще двух недель хватает чтобы привыкнуть. тестилось на непривычном к функциональщине

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

[Afa]

енумераторы ковыряй. https://ruby-doc.org/core-3.0.1/Enumerable.html например. или монады - dry-rb monads

[Tytgrom]

Я тут нашла игру, которая наглядно демонстрирует геометрическу прогрессию и ценность секунд

Конечно, там не 64 клетки, но и степенная функция не 2ки, а тройки. Т.е. ряд 3 - 9 - 27 -81 и т.д. до 12 го уровня, где уже больше полмиллиона. Я дотерпела до 8го уровня (в принципе можно было до 9го дойти) и то с бонусами

Реально жесть