03.03.2024, 21:54 | #1 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Задача коммивояжёра
Приобрел таки книжку Ершова, красиво сделано, но сложно написано - чем дальше тем он короче объясняет по коду, сам код не дает, иногда приходится сильно думать)))
Реализовал из его примеров задачу коммивояжера - методом муравьиной колонии tsp1.JPG
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
04.03.2024, 07:19 | #3 |
Нетолерантный социопат
Регистрация: 12.04.2008
Адрес: Центр циклона
Сообщений: 21,801
|
А чем "задача коммивояжера" отличается от классической "транспортной задачи"??
__________________
Сочту за честь называть себя русским. (с) Я Я не участвую в войне. Война - участвует во мне. (с) Зеркала & Отражения, Nota Bene! |
04.03.2024, 16:58 | #4 | ||
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Транспортная задача, упрощенно - есть N складов и M магазинов, надо товары из складов развести по магазинам за минимальную стоимость
Задача коммивояжера - надо обойти все города по минимальному маршруту Цитата:
Цитата:
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! Последний раз редактировалось квит; 04.03.2024 в 17:09. |
||
05.03.2024, 16:01 | #5 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Квит, а ты где то программистские задачки решал?
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
05.03.2024, 16:05 | #6 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
а что кстати за книжка и из какой системы скрины?
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
05.03.2024, 20:15 | #7 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
05.03.2024, 20:18 | #8 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
в смысле, тут, на форуме, или вообще в принципе???)))
какие то где то решал, да я даже как то школьников немного пообучал в плане подготовки к егэ и к олимпиадам
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
05.03.2024, 20:21 | #9 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
в планах - запилить коммивояжера жадным алгоритмом, отжигом, генетическим)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
05.03.2024, 21:55 | #10 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
А. Понятно. Почти вдохновился тоже что то порешать.... Как пойдет.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
05.03.2024, 22:00 | #11 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Почти интересно, а нейросети на коммивояжера, как то на пускаются?
У нас в МИФИ это проходили математики. А я системотехник.... Это другое. То что не пригодилось.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
05.03.2024, 22:11 | #12 | |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Цитата:
Квиту я как-то координаты кидала, но что-то не задалось.
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
|
06.03.2024, 06:54 | #13 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
пока не особо... но технологии прут, может через несколько лет и тут нарисуется прорыв...
улов негусто упругая нейросеть https://cyberleninka.ru/article/n/ko...yazhera/viewer сеть хопфилда https://www.sibran.ru/upload/iblock/...kerv9775103610
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
06.03.2024, 06:56 | #14 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
А скинь еще раз, щас как то все устаканивается постепенно...
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
06.03.2024, 07:07 | #15 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
программка уже есть)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
06.03.2024, 13:00 | #16 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Я даю свой маршрут. Последовательность может меняться первая цифра горизонталь, вторая вертикаль
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 (по идее с неё начинаю и в неё возвращаюсь) С учетом того, что это просто игрушка и там есть "телепортация", так что оптимизация не критична
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
06.03.2024, 14:13 | #17 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Надо еще, как расстояние считается в этом мире )))
мы из любой точки в любую можем по прямой дойти? - тогда евклидово расстояние если как такси, по кварталам, только горизонтально/вертикально можем ехать - манхэттеновская метрика если извилистые тропинки - то нужен граф дорог
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
06.03.2024, 14:16 | #18 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
По прямой. Там дороги есть, но почти везде можно пройти напрямки и плавать через водные преграды я умею.
Как время при телепортации считается я не очень понимаю, но чем дальше, тем дольше летишь (по игровому времени, реальное время только на загрузку локации)
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
06.03.2024, 15:49 | #19 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
06.03.2024, 16:03 | #20 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
мой вариант - визуально примерно как то так
tsp_tytgrom1.PNG может правда в левом верхнем углу можно еще пооптимизировать домой доеду, запущу программку
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
06.03.2024, 16:07 | #21 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
т.е. еще есть варианты - из 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
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
06.03.2024, 18:51 | #22 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
А насколько по жизни этот алгоритм в реале лучше живых диспетчеров? В реале же, пробки, заправки, то и сё....
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
06.03.2024, 19:20 | #23 | |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Цитата:
Блин, я лопухнулась. Неправильно оси дала. У меня нулевая точка верхний левый угол (ну т.е. я шла с запада на восток, потом спускалась южнее и следующий ряд) 1 2 3 4 2 3 4 У меня 17 пункт мешается. При чем по игре тоже. Он последний присоединяется P1460591.JPG Вов, сейчас вроде бы навигаторы отслеживают пробки. И есть навигаторы, которым можно задать несколько точек в которые хочется попасть. Проблема в том, что он любит перестраивать маршрут, если ему в голову взбредет, что так можно минуту сэкономить, а то и две. Поэтому мы предпочитаем оптимизацию по расстоянию (если не совсем пробка)
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. Последний раз редактировалось Tytgrom; 06.03.2024 в 19:26. |
|
07.03.2024, 06:12 | #24 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
во вторых, диспетчера тоже нормально решить не могут, особенно с ростом количества точек - это даже по примеру Тутгром видно, а когда точек больше... вот к примеру, у нас в городе миллионнике доставка питьевой воды в бутылках - от 1000 до 3000 адресов в сутки надо доставить... собственно, проект возник, когда диспетчера перестали справляться... появилась потребность в автоматизации...))) и в модель все эти особенности - пробки, заправки, пересменки, обед водителя на маршруте - тоже закладываются, есть норматив, например, на обед и есть допуск плюс-минус, который тоже учитывается, условно 30 мин обед +- 10 мин - с этим уже можно работать ну и в третьих, к ЗК сводятся не только транспортные задачи, много еще какие есть, где пробок нету, а задачу решать уметь надо)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! Последний раз редактировалось квит; 07.03.2024 в 11:17. |
|
07.03.2024, 06:30 | #25 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
к задаче коммивояжера (ЗК) сводятся задачи:
- выполнение операций станком с чпу - например сверление отверстий в детали в определенных координатах, или пайка схем, - с минимальным суммарным путем перемещения привода станка - есть промышленное оборудование, которое может выпускать несколько типов изделий, задача определения оптимальной последовательности выпуска изделий с минимальным временем переналадки оборудования - сводится к ЗК - в биоинформатике Цитата:
ну и еще куча всяких приложений из разных предметных областей)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
07.03.2024, 06:34 | #26 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
так это не принципиально, просто зеркально точки отразить, на расстояниях то это не скажется
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
07.03.2024, 11:26 | #27 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
переделал картинку под оси
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
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
07.03.2024, 13:15 | #28 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Спасибо. Попробую. Картинка хорошая получилась.
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
07.03.2024, 13:57 | #29 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
а что за игра то хоть? и зачем там нужно учитывать длину маршрута?
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
07.03.2024, 14:04 | #30 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Игра Фаллаут -4. Учитывать длину маршрута на фиг не надо, но мне удобнее посещать поселения в определенном порядке (поселенцы обижаются, если к ним долго не приходить, ну и потом надо их одеть, что-то им построить, сами они только фермерствовать могут). По алфавиту неудобно - приходилось прыгать по всей карте. По порядку присоединения тоже. Поэтому я решила сделать последовательность по территориальному признаку (если нет перегруза, то я пешком иду, если с грузом, то телепортируюсь). Оптимизация моя личная блажь
Народ вообще без поселений играет, только воюет А я воюю ради ресурсов дя поселений ....
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
07.03.2024, 20:40 | #31 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Скажи, Квит. А ты в конторе или лично у себя какую то базу знаний ведешь? Ты ж поди не рядовой сотрудник, а уже задумываешься о трансляции опыта от кого то к кому то?
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
08.03.2024, 06:05 | #32 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
ну пока вживую передаем, молодым , при личном общении, а вот чтоб как то зафиксировать, даже не задумывался))) а как это выглядит, что то типа вики? даже пока представить не могу, как опыт хотя бы одного человека, если он специалист широкого профиля , можно структурировать
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
08.03.2024, 10:16 | #33 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Конкретно у фирмы confluence
Да типа вики. И жира для задач
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
08.03.2024, 12:13 | #34 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
вики ведем, но это больше в разрезе проектов, а не в плане передачи опыта от спецов молодняку, поделись, если делали, как это выглядит
для задач использовали трелло, ее тоже атласиан перекупил, но пару месяцев назад они сказали, что из рф акаунты будут блокировать, поэтому постепенно переходим на кайтен, вроде отечественная разработка)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
10.03.2024, 10:41 | #35 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
"Жадный алгоритм" - идея простая, и для понимания алгоритма и для его реализации - "идём в ближайший непосещенный город" На псевдокоде: 1. создаем два списка, в первом - посещенные города, начиная с начальной вершины, во втором - оставшиеся точки, из которых будем выбирать и включать в маршрут Инициализация, в первый пишем вершина0, во второй остальные listChoosePoints <- Point0 listRestPoints <- listPoints remove Point0 2. В цикле с кол-вом итераций numPoints-2 2.1 берем текущую точку - это последняя из первого списка 2.2 считаем расстояния от нее до всех из второго списка 2.3 находим минимум и соответствующую ему точку 2.4 включаем эту точку в первый список, исключаем из второго 3. После цикла во втором списке осталась одна точка, включаем ее в конец 1го списка 4. Считаем длину маршрута, из последней точки маршрута делаем еще возврат в точку0
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! Последний раз редактировалось квит; 10.03.2024 в 10:47. |
|
10.03.2024, 10:45 | #36 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Алгоритм простой, но не оптимальный - сначала он ищет "локально оптимальные" решения, но на последней точке, или нескольких последних - возникает "плата за жадность" - когда вариантов выбора мало или совсем не остается, остаются длинные ребра в графе, которые вынуждены включать в маршрут
tsp3.JPG
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
10.03.2024, 10:54 | #37 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
На тех же данных Алгоритм случайной перестановки пары вершин находит лучше решение
его длина маршрута - 99 условных километров против 118 у жадного алгоритма tsp4.JPG
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
10.03.2024, 11:04 | #38 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
это делает алгоритм 2-Opt https://translated.turbopages.org/pr...org/wiki/2-opt его смысл - развязать пересечение двух ребер, доказано, что такая перестановка всегда улучшает длину маршрута т.е. из конфигурации --A..B-- .. \/ .. /\ --C..D-- переходим в конфигурацию --A----B-- --C----D--
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! Последний раз редактировалось квит; 10.03.2024 в 11:15. |
|
10.03.2024, 11:12 | #39 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
почему при перестановках этот вариант не находит - не могу пока понять, либо очень редкий вариант, и на него за заданное кол-во итераций не выходит, либо что-то накосячил в реализации, и поэтому на какие-то видимо граничные варианты не выходит
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
10.03.2024, 14:22 | #40 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Я бы в другую сторону закрутила. из 0 в 5 потом 2, а потом 13, далее против круга и из 12 возврат в 0
Потому что не люблю пересечений ну или 2 - 12 - 13, а в 0 из 8
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
10.03.2024, 15:57 | #41 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
вот алгоритм 2-опт их тоже не любит)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
10.03.2024, 19:07 | #42 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Добавил возможность формирования начального маршрута - либо отсортированного по порядку (вершины идут по возрастанию их id 0,1,2,...), либо в рандомном порядке
после нескольких запусков алгоритм нашел таки оптимальный вариант tsp5.JPG
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
10.03.2024, 19:57 | #43 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
tsp6.JPG
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
10.03.2024, 20:13 | #44 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
У тебя очень простая схема точек. Добавь пару-тройку пунктов внутри фигуры. Сразу количество вариаантов возрастет
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |
10.03.2024, 20:41 | #45 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
у меня же бегунок - кол-во точек можно менять
я этот набор пока не меняю. хочу на нем же еще пару алгоритмов обкатать надо бы в файл сохранить, но мне лениво заморачиваться)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 15:22 | #46 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
возможно, алгоритмически похоже на поиск решения в дереве игры.
часть алгоритмов - стохастические . допустим, мы среди возможных продолжений графа отберем 10 ближайших, и для каждого варианта построим N чисто случайных продолжений, среди которых отберем самое короткое (или не чисто случайных - а допустим выбирать будем среди нескольких самых коротких). Так - можно будет отобрать статистически - перспективное продолжение. это возможно даст квазиоптимальное решение.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 15:43 | #47 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
тут может быть проблема, что целевая функция не монотонна - т.е. не факт, что идя в том направлении, ты будешь всегда улучшать результат хотя какой то вариант ветвей-и-границ для ЗК тоже разработан... т.е. можно строить оценки и отсекать сразу множества решений по веткам...
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.03.2024, 15:45 | #48 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
... и сильно не унимодальна - т.е. не факт, что ты не скатишься в какой нить локальный оптимум
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 15:47 | #49 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
муравьев напустить. пусть пахнут
__________________
... Survivors will be shot again. |
11.03.2024, 15:50 | #50 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
и отсекать вышедших за достигнутый минимум. то бишь не на раннем этапе а на каждом шаге только к улучшению идти
__________________
... Survivors will be shot again. |
11.03.2024, 15:56 | #51 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
муравьев делал - см. самый первый пост, показалось медленно и слишком избыточно реализовано...
т.е. живых мурашей понять можно - они бегут по запаху, где быстрее испарился феромон, ту дорогу забыли и бегут по короткой но в проге нам не надо ждать, пока куча пробежит по маршруту, чтобы понять какой короче - мы из двух вариантов сможем сразу посчитать длину и понять какой хранить, какой отбросить... так что мне в базовом варианте алгоритма кажется, можно значительно его оптимизировать...
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 16:08 | #52 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
ты мультитредный вариант смотри. тебе через пару десятков итераций принесут первый короткий и ты сразу отбросишь кучу деревьев. и дальше пошла чистая оптимизация маршрута. то бишь не отброс на ранних стадиях в приоритет воткнуть а ускорение оптимизации найденного маршрута
мультитредность - вон мурашей эрланговских например посмотри.
__________________
... Survivors will be shot again. |
11.03.2024, 16:16 | #53 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
а, чо я за мурашей т вспомнил - локальные ямки они обходят
__________________
... Survivors will be shot again. |
11.03.2024, 16:20 | #54 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
ну, обходить, наверное, не обходят, скорее - из них выбираются... )))
Цитата:
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.03.2024, 16:45 | #55 | |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Цитата:
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
|
11.03.2024, 16:50 | #56 | |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Цитата:
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
|
11.03.2024, 16:57 | #57 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
в реале тоже - если например, два клиента живут в одном подъезде, то им экономически выгоднее завезти товар на одной машине, чем две гонять, или потом сюда же возвращаться... исключение - если еще учитывается временное окно доставки, первый ждет товар с утра, второй вечером - тогда выгоднее вернуться, или приехать двумя ТС
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.03.2024, 17:29 | #58 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
ну допустим если по факту город на 2 сторонах реки а мост один, то его хочешь или нет проедешь 2 раза. если на графе вершины в принципе связаны все со всеми - те хоть както но можно доехать - то тут все зависит от того, как устроена метрика цены на переход по графу ....
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 19:41 | #59 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
В реальной жизни расстояние ведь неевклидово. Самый кратчайший путь не по прямой, а по дороге....
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 20:17 | #60 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
ну да, по графу дорог... и это отдельная интересная задача - по матрице расстояний между точками расположить точки в некотором евклидовом пространстве, её я заведу после этой)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 20:26 | #61 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 21:32 | #62 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
эрланговских или лэнгтоновских???)))
Цитата:
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.03.2024, 22:35 | #63 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
в задаче коммивояжера нет проходных точек. есть на мосту точка получения груза? нет? моста нет, есть два разных пути между точками. есть? ты так и так проедешь. бо путь ведет через, без разгрузки или с. а смотреть, пересекаются ль пути нам не надо, не усложняй задачу, чай не тополог
__________________
... Survivors will be shot again. |
11.03.2024, 22:37 | #64 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
написаных на erlang. там кода пара экранов. и на слегка тяжелый граф напрыгивает лям процессов, разгрызая задачку
__________________
... Survivors will be shot again. |
11.03.2024, 23:08 | #65 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Вспоминал на днях про эрланг, но что то под винду его нынче развернуть не банально. Что то там надо пару компиляторов одно одним второе другим смешать и не взбалтывать... Лень.
Как то так... Не судьба посмотреть сильно ли миллионы процессов выжирают память и процессор. А задача коммивояжера может решаться как на полном графе, так и на неполном, части которого пересекаются на одной вершине например.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. Последний раз редактировалось BOBA; 11.03.2024 в 23:12. |
12.03.2024, 02:11 | #66 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
а под винду серверные языки и не хотят делать особо. elixir посмотри. та ж вм, синтаксис облагородили и может инсталяху сделали
процессы у эрланга сильно легковесны. но все процы эрланг под себя займёт. и будет молотить на максимальной скорости. у меня сто тыщ в принципе крутилось, на ноуте. норм.
__________________
... Survivors will be shot again. |
12.03.2024, 02:15 | #67 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
а вообще вов, хочешь ся современные - глянь на раст. вроде решили безопасность тредов, и без сборки мусора. нормальный язык под написание ядра.
__________________
... Survivors will be shot again. |
12.03.2024, 14:18 | #68 | ||
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
нашел что то типа такого https://www.onworks.net/ru/software/...-for-qtcreator Цитата:
у меня сейчас задачка алгоритмы всякие покрутить, для решения комбинаторной оптимизации, коммивояжер больше как стенд, на котором можно наглядно посмотреть, как что работает т.е. нет потребности конкретно ЗК решить, потом к ней будет другая задача сводиться, уже с модификацией алгоритмов - и там надо ориентироваться на простые алгоритмы, не будет мощных суперкомпьютеров... может даже на аппаратном уровне придется...
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
||
12.03.2024, 14:30 | #69 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
вот придумал модификацию жадного алгоритма - двусторонний жадный)))
не знаю, был ли раньше где то... суть алгоритма - выбираем две ветки, по одной будем выходить из базы, по второй возвращаться, в каждую ближайшую добавляем из пула нераспределенных... если вдруг две ветки претендуют на одну и ту же вершину (одновременно является ближайшей для обеих веток) - тут есть разные варианты действий, например: 1) исключаем ее временно, ищем ближайшие из оставшихся, включаем вершину обратно 2) рандомно разыгрываем ее, в какую из веток отправить, в оставшуюся находим из нераспределенных 3) считаем сколько точек ближе к первой ветке, сколько ко второй, точку добавляем в ту ветку, где этих точек меньше (из соображений, что в большей ветке по-любому еще найдется) 4)... еще можно придумать другие варианты
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
12.03.2024, 15:02 | #70 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
эм. для кютэ? плагин? слушай, даж разбираться не хочу.
ты ж про шаблон акторы слышал? если грубо плодится куча процессов получающих сигнал и отрабатывающих. эрланг вокруг него и построен. количество машинков в сворме эрлангу пофиг, можно вообще распределенный кластер на распберри собирать а не морочиться мощным железом в каком там амазоноблаке. ну и - эрланговские процессы это эквивалент инстансов объектов. эдакий ооп для процесника а не результатника. они легковесны. потому вся фигня что разбивается на много параллельных кусочков собсна и есть особые алгоритмы.
__________________
... Survivors will be shot again. |
12.03.2024, 16:01 | #71 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
пока пилю свою вариацию жадного)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
12.03.2024, 18:05 | #72 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
ты эт, учитывай шо функциональщина требует переформатирования мозгов. окамл кста можно смотреть, вполне вкусная игрушка. и очень шустрая
__________________
... Survivors will be shot again. |
12.03.2024, 18:14 | #73 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,459
|
Квит, просто интересно, на чем в основном пишете?
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
12.03.2024, 18:51 | #74 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
я почитал про эрланг, да, реально надо вникать, я пока на процедурном
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
12.03.2024, 19:02 | #75 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
если ты про игрушку, в которой сейчас балуюсь - это нетлого, я ее в учебных целях для себя разбираю, решил на примере ЗК расколбасить)))
а если вопрос про реальные задачи, то там разные могут быть платформы и средства, и команды соответственно могут собираться/подбираться под нужное...
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
12.03.2024, 19:21 | #76 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
ну вообще двух недель хватает чтобы привыкнуть. тестилось на непривычном к функциональщине
__________________
... Survivors will be shot again. |
12.03.2024, 19:31 | #77 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,007
|
Цитата:
правда по хэлпам и по примерам, но лиха беда начало)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
12.03.2024, 19:42 | #78 |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,271
|
енумераторы ковыряй. https://ruby-doc.org/core-3.0.1/Enumerable.html например. или монады - dry-rb monads
__________________
... Survivors will be shot again. |
19.03.2024, 23:12 | #79 |
реал зовет
Регистрация: 08.10.2007
Сообщений: 83,554
|
Я тут нашла игру, которая наглядно демонстрирует геометрическу прогрессию и ценность секунд
Конечно, там не 64 клетки, но и степенная функция не 2ки, а тройки. Т.е. ряд 3 - 9 - 27 -81 и т.д. до 12 го уровня, где уже больше полмиллиона. Я дотерпела до 8го уровня (в принципе можно было до 9го дойти) и то с бонусами Реально жесть
__________________
Некоторые материалы в интернете могут содержать недостоверную информацию. Пожалуйста, будьте внимательны. |