Быстрое решение задачи коммивояжера

Hisstar

Есть матрица 7х7 для решения простейшей транспортной задачи в динамическом программировании. Надо найти оптимальный путь с минимальной ценой.
Проблема в том, что меня учили только ручками это делать, а 7х7 как-то очень много ручками писать.
Вопрос: есть ли какая-нибудь программа, умеющая сама без лишних действий с моей стороны посчитать это дело? Может, эксель умеет, а я не знаю?

shpanenoc

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

medmikhr

Задача коммивояжера традиционно решается с помощью алгоритмов глобальной оптимизации.
Оптимизируется (ищется минимум) функция - стоимость пути.
Обычно такие задачи решаются с помощью генетического алгоритма, но существуют и другие.
Я знаю только одну программу под винды, которая это делает - GeneHunter (Она встраивается в Ёксель).
http://neuroproject.ru. Вообще, она платная, но может у кого из форумчан есть...
PS. если дружишь с программированием, могу кинуть свои исходники.

shpanenoc

Дело в том, что транспортная задача и задача коммивояжера ИМХО не одно и то же. Методы решения их совершенно различны. Вот я и прошу определиться.
Правда, сам я никаких подобных программ не знаю, но другим отвечающим будет проще :)

Hisstar

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

Hisstar

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

vsjshnikova

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

shpanenoc

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

Hisstar

мне достаточно решения с точностью 10-12% (все равно, изначально, данные вводятся с высокой погрешностью)

Hisstar

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

medmikhr

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

Сам в VB и Ёкселе не секу, да и сижу под *никсами. Если эксель критичен, то GeneHunter - единственный выбор (гугль больше ничего не знает).
Сколько стоит - не знаю, но по ходу немало

Hisstar

я так полагаю, что про траву вопрос не мне? цитата-то не моя, хотя и ответ на мой пост =//
Если немало, то тогда не надо. Хотя я особо не секу в программировании, алгоритм представляю себе достаточно четко. В любом случае, спасибо за комментарии.

medmikhr

Да, про траву не тебе, а тов.
Ибо перебор - это жесть.

Если посчитать надо один-два раза, то может кто из форумчан посчитает. Или попробуй сходи в НИИЯФ, в лабу нейросетей и генетических алгоритмов. Может разрешат у них подсчитать.

Hisstar

ой, что нашел: http://exsolver.narod.ru/NFP/NFP_salesman.html
ща попробую

h_alishov

Ибо перебор - это жесть.
ты с какого факультета, йо?
количество вариантов решения задачи, которые надо перебрать — 7! = 5040. Какая нафиг жесть? какие нейросети? какой ближний восток?

Hisstar

я, конечно, могу ошибаться, но 7х7 должен и мой комп в экселе потянуть (по крайней мере, 5х5 ручками за 3 часа можно легко решить на бумаге). А ты можешь ссылку дать на какой-нибудь хороший ликбез по генетическим алгоритмам?

medmikhr

Я говорил, что эта задача не очень сложна, и ее можно решить перебором.
Но вдруг человеку понадобится решить задачу большей размерности, а 8! или 9! уже много.
Перебор - это не концептуально

Hisstar

ну, я физически в НИИЯФ сходить не могу, а тут у меня вокруг почвоведы с лесниками.

vsjshnikova

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

h_alishov

не слушай ты , он бредит.
если б у меня был установлен excel, я бы написал тебе этот макрос. Он состоит из 10-12 строк и работает мгновенно.

medmikhr



А ты можешь ссылку дать на какой-нибудь хороший ликбез по генетическим алгоритмам
http://ru.wikipedia.org/wiki/Генетический_алгоритм
http://www.neuroproject.ru/genealg.php
первые две ссылки в гугле =)
Это посерьезнее : http://lib.mexmat.ru/books/8947

h_alishov

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

medmikhr

Вдруг война, а я уставший!
Война не поинтересуется о твоем самочувствии.


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

Hisstar

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

Hisstar

спасибо, почитаю!

h_alishov

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

Vlad128

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

Hisstar

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

vsjshnikova

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

Hisstar

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

toxin

то задача коммивояжера. Решали вы ее полным перебором, как, собственно, и следует ее решать. Единственные слова, которые являются лишними, - "динамическое программирование", т.к. это совсем другое.
Вообще-то для n<=25 задачу коммивояжера как раз решают тривиальным динамическим программированием за [math]$O(n^2 2^n)$[/math]. Для n=7, впрочем, большой разницы с [math]$O(n!)$[/math] нет.

shpanenoc

Имеется в виду F(x, S) = мин. стоимость поездки из x во все города множества S?
Действительно, просто. Правда, необходимо еще и n*2^n памяти, чего не требует полный перебор. Спасибо, буду знать.

seregaohota

При n=7 естественно перебором решается, так как в книге рекордов Гиннеса есть как я слышал даже рекорд когда перебирают все перестановки при особой технике колокольного звона на 8 колоколах, часов 18 что ли занимает. На компе с 8! вроде до 14! или 15! за разумное время перебором делается.
В общем случае вроде алгоритм имитации отжига, вроде IBM при разводке плат использует. Хотя может и генетический лучше и я не в теме.
Если макрос сделаете или прогу кто-то обещал - может кинете в тему или в приват файлик? Для самообразования.

toxin

Почти. F(x,S)= минимальная стоимость пути из 1 в x проходящего по всем городам из S (S должно содержать 1 и x разумеется).

Hisstar

тебе в "сыром" виде требуется? если макрос будет мною получен, и автор макроса будет не против, залью на ближайший файлообменник
Оставить комментарий
Имя или ник:
Комментарий: