Задача коммивояжера delphi
Задача коммивояжера delphiСкачать файл - Задача коммивояжера delphi
Регистрация Выслать повторно письмо для активации Что даёт регистрация на форуме? RU Программирование Алгоритмы Нравится ресурс? Помните, что название темы должно хоть как-то отражать ее содержимое не создавайте темы с заголовком ПОМОГИТЕ, HELP и т. Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями. Приводимые фрагменты исходного кода старайтесь выделять тегами code Помните, чем подробнее Вы опишите свою проблему, тем быстрее получите вразумительный совет 5. Запрещено поднимать неактуальные темы ПРИМЕР: Помогите пожалуйста написать программу delphi, pascal для решения этой задачи, подойдет любая любой метод: Я сам уже неделю пытаюсь что то написать, но без знания рекурсии и многих других методов ничего не получается. А точнее пользователь задаёт координаты каждой точки число точек заранее не извесно , и надо найти кратчйший путь. Вроде все хорошо объяснено. К сожелению он выдаёт ошибку в 30 процентов, и больше. Есть ли какой то способ улучшить этот алгоритм? V1taly , ты на Pascal. Я решал там задачу коммивояжера методом ветвей и границ. Метод ветвей и границ. Задача коммивояжера Там же есть ссылка на второй способ решения задачи К сожалению, если количество точек увеличить до пары сотен, то точные алгоритмы будут работать черт-те сколько ибо задача имеет экспоненциальную сложность. Поэтому часто смотрят в сторону приближенных алгоритмов, основанных на различных эвристиках. Из наиболее популярных - Kernighan-Lin heuristic или по-другому - pairwise exchange , различные комбинаторных эвристики, типа hill climbing, simulated annealing и т. Fail better' c Samuel Beckett. В школьных тьфу ты, университетских практически любых учебниках по графам помимо обхода в ширину и глубину приводится парочка жадных алгоритмов. Но не тех, которые совсем примитивны, а чуть-чуть покачественней. К примеру, по минимальному остову. Например, алгоритмом Крускала или Прима. Никакого перебора и обхода, крайне формализованные методы. Много раз уже разными людьми запрограммированные. Перебором никуда не денешься, но в этом случае перебора будет меньше входящие в такие узлы ребра 'перекидываются' в другие в условиях следующего целеполагания: Но меньше, чем в полном обходе в ширину. Это и есть решение. Где-то я это уже писала Возьму ли крылья зари и переселюсь к самому морю Правда TSP можно попробовать решить, используя эвристический поиск, где в качетве эвристики строить MST. Эта эвристика - admissible как это по-русски? К сожалению, в худшем случае мы затратим экспоненциальное время. Поэтому часто предлагаются approximation algorithms приближенные алгоритмы. Их особенность в том, что мы не перебираем все пространство решений, рискуя тем самым получить неоптимальное решение. Но зато за адекватное время. Один из подходов к такому поиску - так называемый метод локального поиска опять же, я извиняюсь, если я коверкая термины, я их на русском никогда не видел, просто стараюсь чтобы было понятнее. Идея заключается в том, что мы строим какой-то гамильтонов цикл, а потом начинаем его менять, стараясь улучшить. Kernighan и Lin предложили произвольно удалять ребра и связывать вершины заново, стремясь улучшить общую длину маршрута. Если я не ошибаюсь, то метод заключается в том, чтобы просчитать все циклы, которые получаются из данного, путем изменения ребер. Для обсчета всех циклов, они делают поиск в ширину по дереву решений, разумеется, не по исходному графу. Алгоритм запускается много раз и начинает менять разные ребра. Simulated annealing похож на local search. В общем случае он тоже меняeт поиск по пространству решений, стремясь каждый раз найти решение лучше, чем текущего. Особенность simulated annealing в том, что иногда метод ухудшает решение в надежде, что дальнейшее изменение приведет к его улучшению. Таким образом метод позволяет избегать локальных максимумов неоптимальных решений, которые тем не менее лучше всех соседних решений. К сожалению, это трудно объяснить на пальцах. Но в целом нет ничего сложного, просто нужно представлять, что такое эвристический поиск в общем виде.. Просто товарищ Виталий просил 'больше информации' Ему её предоставили. А товарищу Арсьюту, если он собирается заниматься ЭТОЙ математикой, необходимо научиться читать по-английски. Иначе ничего не получится. Спасибо за информацию хотя я в ней ничего не понял, так как еще не в университете и графы и т. Лектор сказал, что хватит и такого алгоритма пока, так как главной задачей в этом году у нас была научится самым простым основам программирования и я дополнительно создал хорошую датабазу, которая и будет оцениватся в большей степени. В следующем году буду снова доделывать этот проэкт и тогда ваша информация очень пригодится. Если хотите могу выложить все что я нашел по коммивояжеру в интернете русс. Предыдущая тема Алгоритмы Следующая тема. Powered by Invision Power Board U v1.
Задача коммивояжера
Краткое содержание рассказа номер
Художественный на арбате расписание сеансов
Решение задачи коммивояжера методом ветвей и границ в Delphi
Сколько калорий в большом банане
Расчет численного состава бригады
Коммивояжер полным перебором
Кинотеатр голд синема луховицы расписание
Таблица давление насыщения нефти газом
Коммивояжер полным перебором
Расписание автобусов киров казань 2017