2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение23.08.2014, 16:40 


17/11/10
19
Прошу помощи у коммунити.
Окончательно зашел в тупик, при решении топик-задачи, хочется однозначного понимания, дает ли вышеупомянутый метод оптимальное решение, или всё таки решение данным методом правильное, но не является оптимальным.
Алгоритм брал здесь:Алгоритм Литтла (уже упоминал этот ресурс), тестировал там-же. Решая задачу, описанную здесь, получаю результат, явно не соответствующий оптимальному (как ни странно, полученному решением "жадным" методом). Контрольный пример могу привести. У кого есть возможность помочь - с меня пиво.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение23.08.2014, 18:28 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Алгоритм Литтла даёт оптимальное решение.
Так что либо задача не та решается, либо алгоритм неверен. Во всяком случае, то, что описано по ссылке - это точно не алгоритм Литтла, хотя и "нечто по мотивам". Он вообще не "ветвей и границ", в нём ничего не ветвится и, соответственно, не нужны границы отсечения.

(Оффтоп)

Жил был на свете один добрый мальчик. И пошел он как-то в лес погулять. Ходит он, любуется деревьями, птичками и цветочками. И вдруг видит маленького ежика под кустом. Ежик был очень хилым и голодным. Стало мальчику его жалко и решил он его взять с собой. Принес его домой, напоил молоком, накормил сметаной, смастерил домик с теплой ватой и опилками. И так мальчик ухаживал тщательно и с любовью за ежиком месяц. Все что только ежику было нужно - все мальчик ему предоставил.
Но через месяц ежик стал меняться: у него отвалились иголки, вместо симпатичной мордочки отросла пасть с огромными клыками, язык вытянулся и стал раздвоенным как у змеи, ноги вытянулись и покрылись чешуей, между пальцев выросли плавательные перепонки, вырос лопатообразный хвост, как у бобра и выросли большие оперенные крылья, а на голове у него выросли оленьи рога...
Неожиданно мальчик понял, что принес он домой не ежика, а ФИГ ЗНАЕТ ЧТО!

Вот более вменяемое описание
http://www.lib.tsu.ru/mminfo/000349342/ ... 20-078.pdf

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение24.08.2014, 09:12 


17/11/10
19
Спасибо,пошел учиться :D

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение24.08.2014, 13:32 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Очень краткое и поверхностное описание алгоритма:
Это метод класса "ветвей и границ". То есть в нём делаются ветвления, в данном случае выбирается включать ли в маршрут переход i->j или не включать, что порождает две ветви, которые затем тоже делятся, и в худшем случае число ветвей растёт экспоненциально, но при этом для каждой ветви строится оценка "снизу", и если она оказывается хуже уже достигнутого решения, данная ветка сразу исключается без дальнейшего ветвления. Обход делается так, чтобы быстро получить некое "хорошее" решение, что позволит исключать ветки, для которых оценка хуже. В качестве оценки используется сумма минимальных значений по строкам и минимальных (после вычитания минимума по строкам) значений по столбцам, поскольку при любом обходе меньше названной величины не получится. Для поиска "хорошего" решения используется некоторая эвристика: для включения в обход выбирается тот элемент, для которого сумма минимумов в содержащих его строке и столбце максимальна (то есть если на самом деле надо было включать другой элемент, то его вклад будет не меньше этой суммы, так что если она максимальна, то шанс, что надо было брать иной нулевой элемент - минимален). Выбрав такой элемент - ветвимся, одна ветвь с переходом i->j, в ней мы можем сразу убрать всю i-тую строку и j-тый столбец, а также запретить переход j->i, вторая ветвь - в которой запрещён только переход i->j. Обход делаем "в глубину", всё время выбирая левую ветвь, пока не получим допустимое (и, надеемся, хорошее) решение, а потом начинаем обходить остаток дерева, отсекая те ветви, где оценка хуже уже достигнутого решения, а где получено решение лучше достигнутого ("рекорда") - используем новый "рекорд". Пока всё дерево не обойдём - не будем уверены в том, что нашли оптимум.
Алгоритм, который по Вашей ссылке - часть настоящего. Собственно, это движение по одной ветке в глубину, а отсечения и перебора не видать.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение24.08.2014, 15:04 


17/11/10
19
Евгений Машеров
Большое спасибо за разъяснения и потраченное время. Буду разбираться, поскольку решение действительно необходимо. По результату разбирательства отпишусь здесь, или буду докучать вопросами...
Ещё раз спасибо.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение25.08.2014, 09:15 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Да, и вдогонку.
Запрет делается присвоением данному переходу "бесконечной стоимости" (обычно используют не IEEE-шный +INF, а просто очень большое, заведомо большее всех стоимостей реальных переходов число).
В связи с этим вызывает сомнение рекомендация в алгоритме по Вашей ссылке - вычислять длину пути i->j и её принимать за значение для запрета. Вообще совершенно неадекватное описание алгоритма (и возникает сомнения в том, что прочие алгоритмы на сайте изложены без фатальных ошибок).

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение25.08.2014, 14:44 


17/11/10
19
Да, теперь понятно, что ветвление не реализовано во взятом за основу алгоритме, и обход велся только по левой ветви.
В приведенном примере, к сожалению, не встретился момент, когда оценочное значение 2-й (правой) ветви будет предпочтительнее, чем левой. Не ясно, что делать, если на n-ом шаге в матрице, после запрета i->j перехода, оценочное значение будет меньше ,а следовательно - предпочтительнее (оно ведь может быть меньше, иначе теряется суть обхода по правой ветви). Нужно вернуться к (n-1)-му шагу, i->j переход не включать в порядок обхода, а искать новый (при этом оставляя запрет i->j перехода)?
Если что-то не то говорю, уж не взыщите...

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение25.08.2014, 15:05 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Сравнивать надо не оценочные значения ветвей, левой и правой, а оценочное значение каждой ветви с рекордом. Если для данной ветви оценочное значение лучше рекорда (если хуже - её сразу можем "зарубить"), то, идя по этой ветви далее, мы можем придти к лучшему решению, а можем и не придти. То есть по ней надо ветвиться. Опять выбирать включаемый переход k->l и делать две ветки - с включением его и с запретом. И так далее.
Обычный обход дерева, поиск в глубину. Просто надо обходить не все мыслимые ветви дерева, некоторые удаётся обрубить без ветвления. Но если оснований рубить нет, оценка для этой ветви лучше рекорда, то рубить мы не вправе. Надо ветвиться, в надежде найти лучшее решение (и уточнить рекорд) или обрубить плохие ветки (в худшем случае - обойти всё дерево).

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение25.08.2014, 16:22 


17/11/10
19
Хорошо. Предположим, запретив переход i->j в правой ветви, вычисляем оценочное значение, и оно лучше рекорда. Каким образом будет строиться обход этой ветви?

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение25.08.2014, 18:35 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Точно так же. Поскольку оценка лучше рекорда, зарубить ветку сразу мы не может. Поэтому её ветвим. Точно так же находим кандидата на ветвление k->l, и строим две подветки - в одной путь k->l используется, в другой запрещён. И так далее.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение26.08.2014, 11:00 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Могу подкинуть популярную книжку Мудрова (из "Знаниевской" серии брошюр), где довольно подробно расписаны шаги. Куда бросать?

-- 26 авг 2014, 11:10 --

Ну, или есть:
Введение в прикладное дискретное программирование.Модели и вычислительные алгоритмы Сигал И.Х., Иванова А.П.
Тоже подробно расписано.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение26.08.2014, 12:20 


17/11/10
19
hclubmk@list.ru
будет здорово получить подробное рассмотрение хоть нескольких примеров с ветвлением и по правой части дерева.
Спасибо, буду ждать.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение26.08.2014, 13:24 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Отправлено.

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение01.09.2014, 15:38 


17/11/10
19
Это было увлекательно!
Хочу поблагодарить за книги и за подсказки - видно, что Вы - практик.
Мудров очень подробно и доступно описывает методику - хорошая книга, вероятно, ещё кому-то может пригодиться, с Вашего позволения оставлю на нее ссылку
Пришлось, конечно, повозиться с не рекуррентным обходом графа, но это уже не так важно. Метод действительно работает замечательно, как при замкнутом контуре, так и с обозначенными начальной и конечной точкой маршрута. (Конечную точку задаю запретом переходов из нее в любую другую, кроме начальной).
Ну и пара рассчитанных маршрутов как результат реализации метода: замкнутый, разомкнутый
Ещё раз благодарю за содействие.

И, да, я неловко себя чувствую... Куда высылать пиво? :-)

 Профиль  
                  
 
 Re: Алгоритм Литтла - метод решения задачи коммивояжера
Сообщение01.09.2014, 18:35 
Заслуженный участник
Аватара пользователя


11/03/08
9459
Москва
Откуда высылать-то собираетесь?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group