Быстрое решение задачи коммивояжера
Определись плиз, что тебе надо: динамическое программирование или задача коммивояжера?
Задача коммивояжера традиционно решается с помощью алгоритмов глобальной оптимизации.
Оптимизируется (ищется минимум) функция - стоимость пути.
Обычно такие задачи решаются с помощью генетического алгоритма, но существуют и другие.
Я знаю только одну программу под винды, которая это делает - GeneHunter (Она встраивается в Ёксель).
http://neuroproject.ru. Вообще, она платная, но может у кого из форумчан есть...
PS. если дружишь с программированием, могу кинуть свои исходники.
Оптимизируется (ищется минимум) функция - стоимость пути.
Обычно такие задачи решаются с помощью генетического алгоритма, но существуют и другие.
Я знаю только одну программу под винды, которая это делает - GeneHunter (Она встраивается в Ёксель).
http://neuroproject.ru. Вообще, она платная, но может у кого из форумчан есть...
PS. если дружишь с программированием, могу кинуть свои исходники.
Дело в том, что транспортная задача и задача коммивояжера ИМХО не одно и то же. Методы решения их совершенно различны. Вот я и прошу определиться.
Правда, сам я никаких подобных программ не знаю, но другим отвечающим будет проще
Правда, сам я никаких подобных программ не знаю, но другим отвечающим будет проще
ок, мои знания ограничены в этом вопросе. В общем, дано: стоимости перемещения из 7 разных пунктов (матр. 7х7 перемещаться можно в любом порядке, нужно посетить все точки. Требуется: определить маршрут с минимальной стоимостью.
(У нас это называли задачей коммивояжера и решали методами динамического программирования. Т.е. грустным перебором вариантов, другого я не знаю.)
(У нас это называли задачей коммивояжера и решали методами динамического программирования. Т.е. грустным перебором вариантов, другого я не знаю.)
Большое спасибо за отклик. К сожалению, с программированием очень слабо дружу и не думаю, чтобы меня хватило запрогать что-то. Но если ты это можешь в вижуал бейсике под эксель запрогать, то буду очень признателен. Мне неизвестен объем работ, поэтому готов отблагодарить пивом/соком/шоколадкой или деньгами на твой выбор.
Мне как раз в эксель это дело надо, т.к. буду пользоваться не я, а просто отдам файлик. Моя задача в работе - заформализовать условные ограничения, что я и сделал. Но проверить свои наработки не могу, т.к. не знаю алгоритма оптимизации =//
А эти исходники встраиваются в эксель?
Мне как раз в эксель это дело надо, т.к. буду пользоваться не я, а просто отдам файлик. Моя задача в работе - заформализовать условные ограничения, что я и сделал. Но проверить свои наработки не могу, т.к. не знаю алгоритма оптимизации =//
А эти исходники встраиваются в эксель?
(У нас это называли задачей коммивояжера и решали методами динамического программирования. Т.е. грустным перебором вариантов, другого я не знаю.)Точное решение иначе как перебором не получить.
Все быстрые алгоритмы, в т.ч.генетика дают в общем случае приближенный ответ.
Тебя интересует точное или приближенное решение?
Это задача коммивояжера. Решали вы ее полным перебором, как, собственно, и следует ее решать. Единственные слова, которые являются лишними, - "динамическое программирование", т.к. это совсем другое.
Если никто не возьмется, я могу попробовать запрограммировать полный перебор на VBA (очевидно, тебе не нужны всякие навороты с оптимизацией из-за малого размера графа). Правда, я на нем писал первый и последний раз лет 10 назад, но, думаю, справлюсь. Лишь бы там рекурсия была
Если никто не возьмется, я могу попробовать запрограммировать полный перебор на VBA (очевидно, тебе не нужны всякие навороты с оптимизацией из-за малого размера графа). Правда, я на нем писал первый и последний раз лет 10 назад, но, думаю, справлюсь. Лишь бы там рекурсия была
мне достаточно решения с точностью 10-12% (все равно, изначально, данные вводятся с высокой погрешностью)
да, рекурсия там, несомненно, присутсвует
давай я тебе в приват напишу несколько позже, если не смогу найти более легкого решения, типа какой-нибудь готовой программки-алгоритма, ок?
давай я тебе в приват напишу несколько позже, если не смогу найти более легкого решения, типа какой-нибудь готовой программки-алгоритма, ок?
Точное решение иначе как перебором не получить.Где вы достали такую хорошую траву?
Все быстрые алгоритмы, в т.ч.генетика дают в общем случае приближенный ответ.
Целевая функция дискретная, поэтому можно получить точное решение. Задача не очень сложна, поэтому ее можно решить за приемлимое время.
Сам в VB и Ёкселе не секу, да и сижу под *никсами. Если эксель критичен, то GeneHunter - единственный выбор (гугль больше ничего не знает).
Сколько стоит - не знаю, но по ходу немало
я так полагаю, что про траву вопрос не мне? цитата-то не моя, хотя и ответ на мой пост =//
Если немало, то тогда не надо. Хотя я особо не секу в программировании, алгоритм представляю себе достаточно четко. В любом случае, спасибо за комментарии.
Если немало, то тогда не надо. Хотя я особо не секу в программировании, алгоритм представляю себе достаточно четко. В любом случае, спасибо за комментарии.
Да, про траву не тебе, а тов.
Ибо перебор - это жесть.
Если посчитать надо один-два раза, то может кто из форумчан посчитает. Или попробуй сходи в НИИЯФ, в лабу нейросетей и генетических алгоритмов. Может разрешат у них подсчитать.
Ибо перебор - это жесть.
Если посчитать надо один-два раза, то может кто из форумчан посчитает. Или попробуй сходи в НИИЯФ, в лабу нейросетей и генетических алгоритмов. Может разрешат у них подсчитать.
ой, что нашел: http://exsolver.narod.ru/NFP/NFP_salesman.html
ща попробую
ща попробую
Ибо перебор - это жесть.ты с какого факультета, йо?
количество вариантов решения задачи, которые надо перебрать — 7! = 5040. Какая нафиг жесть? какие нейросети? какой ближний восток?
я, конечно, могу ошибаться, но 7х7 должен и мой комп в экселе потянуть (по крайней мере, 5х5 ручками за 3 часа можно легко решить на бумаге). А ты можешь ссылку дать на какой-нибудь хороший ликбез по генетическим алгоритмам?
Я говорил, что эта задача не очень сложна, и ее можно решить перебором.
Но вдруг человеку понадобится решить задачу большей размерности, а 8! или 9! уже много.
Перебор - это не концептуально
Но вдруг человеку понадобится решить задачу большей размерности, а 8! или 9! уже много.
Перебор - это не концептуально
ну, я физически в НИИЯФ сходить не могу, а тут у меня вокруг почвоведы с лесниками.
Где вы достали такую хорошую траву?Кук подкинул.
Задача коммивояжера NP-полна и в общем случае решается только перебором.
При фиксированном размере графа можно, разумеется, построить быстрый алгоритм с предвычислением больших таблиц, но это предвычисление займет, опять же, долгое время и будет являться по сути предварительным перебором вариантов соотношения расстояний в графе.
Генетика дает во многих случаях точный ответ. Может быть, даже при почти всех, надо смотреть литературу.
не слушай ты , он бредит.
если б у меня был установлен excel, я бы написал тебе этот макрос. Он состоит из 10-12 строк и работает мгновенно.
если б у меня был установлен excel, я бы написал тебе этот макрос. Он состоит из 10-12 строк и работает мгновенно.
http://ru.wikipedia.org/wiki/Генетический_алгоритм
А ты можешь ссылку дать на какой-нибудь хороший ликбез по генетическим алгоритмам
http://www.neuroproject.ru/genealg.php
первые две ссылки в гугле =)
Это посерьезнее : http://lib.mexmat.ru/books/8947
Но вдруг человеку понадобится решить задачу большей размерности, а 8! или 9! уже много.до 12! без проблем можно решать на обычном компе.
Перебор - это не концептуальноВдруг война, а я уставший!
Проблемы нужно решать по мере их поступления.
Вдруг война, а я уставший!Война не поинтересуется о твоем самочувствии.
Проблемы нужно решать по мере их поступления.Мне кажется, если решать проблемы решать по мере их наступления, то никогда не настанет момент, когда этих проблем не будет.
Однако, все и такая точка зрения имеет право
спасибо, я тут кажется нашел, как штатными средствами решить, но если что был бы благодарен за формулы к макросу (думаю, заботать сам язык смогу, помнится, когда-то всякую линейную оптимизацию на турбо паскале писал 
). Но я ща сам постараюсь все сделать, чтобы никого особо не напрягать
). Но я ща сам постараюсь все сделать, чтобы никого особо не напрягатьспасибо, почитаю!
спасибо, я тут кажется нашел, как штатными средствами решить, но если что был бы благодарен за формулы к макросу (думаю, заботать сам язык смогу, помнится, когда-то всякую линейную оптимизацию на турбо паскале писал ). Но я ща сам постараюсь все сделать, чтобы никого особо не напрягатьлучше пришли excel с примером таблички с расстояниями. Вроде завтра я буду рядом с ноутом с excel, постараюсь накорябать.
Если вдруг забуду (до 18:00 в этом треде не появится ответа пиши приват.
При фиксированном размере графа можно, разумеется, построить быстрый алгоритм с предвычислением больших таблиц, но это предвычисление займет, опять же, долгое время и будет являться по сути предварительным перебором вариантов соотношения расстояний в графе.Все же раз ОПу надо написать макрос для экселя, то считать явно будут не один раз. Так что эти аргументы — лишние.
Перебор перебором, NP-полнота NP-полнотой, но писать быстрые программы еще никто не запрещал.
а мне всегда казалось, что на мехмате даже оценку снижают (за непрактичность решения если начинаешь из пушки по воробьям палить.
Логично же, что к простым задачам простые решения. Особенно если учесть, что я чайник и про генетические алгоритмы ничего не знаю.
Логично же, что к простым задачам простые решения. Особенно если учесть, что я чайник и про генетические алгоритмы ничего не знаю.
Ну, если макрос будет использоваться не 100 раз, а миллион, и при этом надо, чтобы этот миллион обработался быстро, то надо писать программу, которая сгенерирует быстрый макрос с разбором всех случаев для графа из 7 вершин. Так что замечание вполне справедливое. Только мне кажется, это не тот случай.
а, я не сказал о частоте использования, сорри. Прога не предполагает интенсивного использования. Вообще это будет туристический калькулятор маршрута с несколькими видами транспорта. Облегчает жизнь путешественникам по городам, которым порядок посещения менее важен, нежели цена.
то задача коммивояжера. Решали вы ее полным перебором, как, собственно, и следует ее решать. Единственные слова, которые являются лишними, - "динамическое программирование", т.к. это совсем другое.Вообще-то для n<=25 задачу коммивояжера как раз решают тривиальным динамическим программированием за
Имеется в виду F(x, S) = мин. стоимость поездки из x во все города множества S?
Действительно, просто. Правда, необходимо еще и n*2^n памяти, чего не требует полный перебор. Спасибо, буду знать.
Действительно, просто. Правда, необходимо еще и n*2^n памяти, чего не требует полный перебор. Спасибо, буду знать.
При n=7 естественно перебором решается, так как в книге рекордов Гиннеса есть как я слышал даже рекорд когда перебирают все перестановки при особой технике колокольного звона на 8 колоколах, часов 18 что ли занимает. На компе с 8! вроде до 14! или 15! за разумное время перебором делается.
В общем случае вроде алгоритм имитации отжига, вроде IBM при разводке плат использует. Хотя может и генетический лучше и я не в теме.
Если макрос сделаете или прогу кто-то обещал - может кинете в тему или в приват файлик? Для самообразования.
В общем случае вроде алгоритм имитации отжига, вроде IBM при разводке плат использует. Хотя может и генетический лучше и я не в теме.
Если макрос сделаете или прогу кто-то обещал - может кинете в тему или в приват файлик? Для самообразования.
Почти. F(x,S)= минимальная стоимость пути из 1 в x проходящего по всем городам из S (S должно содержать 1 и x разумеется).
тебе в "сыром" виде требуется? если макрос будет мною получен, и автор макроса будет не против, залью на ближайший файлообменник
Hisstar
Есть матрица 7х7 для решения простейшей транспортной задачи в динамическом программировании. Надо найти оптимальный путь с минимальной ценой.Проблема в том, что меня учили только ручками это делать, а 7х7 как-то очень много ручками писать.
Вопрос: есть ли какая-нибудь программа, умеющая сама без лишних действий с моей стороны посчитать это дело? Может, эксель умеет, а я не знаю?