Kwert-soft.ru

IT Софт для ПК
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Задача коммивояжера php

Задача коммивояжера на php (Поиск кратчайшего маршрута)

Задача:
Есть ряд точек с расстоянием и временем прибытия. Не между всеми точками есть прямая связь. Зная начальный и конечный пункт, нужно найти кратчайший путь (или время).

Таблица, без особых излишеств, выглядит так:

Реализацию задумал такую:

  • Функции на вход подается начальная и конечная точка.
  • По начальной точке делается запрос в базу, где выбираются все уникальные значения для полей city_1 и city_2 для входной точки (отсортировано по нарастающей).
  • Получившийся массив пускаем через foreach , и для каждой точки в выборке запускаем рекурсивно эту же функцию, параллельно сохраняя эти точки в возвратный массив.

На момент написания сего эпоса недокод выглядит так (пока запрос без сортировки):

Запустив этот код сейчас, получается такое:

Наполнение массива подсказали отсюда.
По задумке, я должен получить массив от начальной точки до всех возможных концов ( $end ). Далее, одну из ветвей массива вида $tree[‘A’][‘C’][‘D’][‘F’] , ключи которых я бы в будущем разобрал и по которым вывел варианты маршрута. А теперь о трудностях:

  1. Этот метод наполнения возвратного массива так и не смог адаптировать под свои нужды.
  2. Если, например, в очередной итерации я подам ключ ‘С’ , надо отфильтровать родительский ключ, иначе будет бесконечность. Я понимаю, что в нужный момент нужно добавить условие, что бы пропустить итерацию при помощи continue . Но как обратится к родительскому ключу?
  3. Каким образом перебрать каждую ветку возвращаемого массива, именно ключи (пример ветки ниже).

Т.е, запустив код getTree(‘A’, ‘F’); , я ожидаю получить такие результаты (без сортировки):

2 ответа 2

Вы меня слишком заинтриговали задачей, пришлось ее решить 🙂 Правда при наличии информации в базе мне лениво делать на php и я решил делать целиком в MySQL. Заодно научился процедуры создавать. Сделал на скорую руку, для реальной работы надо немного пересмотреть политику создания новых записей в таблице запросов и удаления их при изменениях в таблице дистанций. Но обо всем по порядку .

Процедура поиска маршрутов по алгоритму Дейкстры:

Так как для поиска оптимального маршрута необходимо пройти все узлы сети и сохранить метрики для всех пройденных узлов, нет никакого смысла искать маршрут из пункта A в пункт Б. Гораздо удобнее сохранить все оптимальные маршруты из пункта А во все достижимые пункты. И потом из этой таблички выбирать маршруты по мере надобности.

Алгоритм получился даже проще, чем я ожидал изначально. Никаких рекурсий и сложных структур. Один цикл, выбирающий еще не обработанный узел из таблицы узлов и добавляющий в нее же все вновь найденные. Прошли узел, поставили отметку, что бы не возвращаться более к нему. Если реализовывать на php, то вместо моей таблицы vertex вам понадобится массив записей с аналогичной структурой, разве что qid можно будет убрать.

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

Гамильтоновы графы

Содержание

Основные определения [ править ]

Определение:
Гамильтоновым путём (англ. Hamiltonian path) называется простой путь, проходящий через каждую вершину графа ровно один раз.
Определение:
Гамильтоновым циклом (англ. Hamiltonian cycle) называют замкнутый гамильтонов путь.
Определение:
Граф называется полугамильтоновым (англ. Semihamiltonian graph), если он содержит гамильтонов путь.
Определение:
Граф называется гамильтоновым (англ. Hamiltonian graph), если он содержит гамильтонов цикл.

Очевидно, что любой гамильтонов граф также и полугамильтонов.

Достаточные условия гамильтоновости графа [ править ]

Теорема Дирака [ править ]

Теорема Оре [ править ]

Теорема:

Теорема Поша [ править ]

Теорема:

Теорема Редеи-Камиона [ править ]

Теорема (Поша):

Теорема Гуйя-Ури [ править ]

Теорема:

Теорема Хватала [ править ]

Теорема (Ghouila-Houri):

Тогда если [math] forall k in mathbb N [/math] верна импликация:

[math] d_k leqslant k lt n/2 Rightarrow d_ geqslant n — k, (*) [/math] то граф [math] G [/math] гамильтонов.

Задача о коммивояжере [ править ]

Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре.

Описание задачи [ править ]

Теорема (Хватал):
Задача:
Задача о коммивояжере (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

Варианты решения [ править ]

Задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения с экспоненциальным временем работы.

Перебор перестановок [ править ]

Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все [math] N! [/math] всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших [math]N[/math] . Сложность алгоритма [math]O(times)[/math] .

Динамическое программирование по подмножествам (по маскам) [ править ]

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе. Зафиксируем начальную вершину [math]s[/math] и будем искать гамильтонов цикл наименьшей стоимости — путь от [math]s[/math] до [math]s[/math] , проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор [math]s[/math] не имеет значения. Поэтому будем считать [math]s = 0 [/math] .

Подмножества вершин будем кодировать битовыми векторами, обозначим [math]mask_i[/math] значение [math]i[/math] -ого бита в векторе [math]mask[/math] .

Обозначим [math]d[i][mask][/math] как наименьшую стоимость пути из вершины [math]i[/math] в вершину [math]0[/math] , проходящую (не считая вершины [math]i[/math] ) единожды по всем тем и только тем вершинам [math]j[/math] , для которых [math]mask_j = 1[/math] (т.е. [math]d[i][mask][/math] уже найденный оптимальный путь от [math]i[/math] -ой вершины до [math]0[/math] -ой, проходящий через те вершины, где [math]mask_j=1[/math] . Если [math]mask_j=0[/math] ,то эти вершины еще не посещены).

Алгоритм поиска цикла будет выглядеть следующим образом:

  • Начальное состояние — когда находимся в [math]0[/math] -й вершине, ни одна вершина не посещена, а пройденный путь равен [math]0[/math] (т.е. [math]i = 0[/math] и [math]mask = 0[/math] ).
  • Для остальных состояний ( [math]i ne 0[/math] или [math]mask ne 0[/math] ) перебираем все возможные переходы в [math]i[/math] -ую вершину из любой посещенной ранее и выбираем минимальный результат.
  • Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как [math]infty[/math] ).

Стоимостью минимального гамильтонова цикла в исходном графе будет значение [math] d[0][2^n-1][/math] — стоимость пути из [math]0[/math] -й вершины в [math]0[/math] -ю, при необходимости посетить все вершины. Данное решение требует [math]O(<2^n>times)[/math] памяти и [math]O(<2^n>times)[/math] времени.

Для того, чтобы восстановить сам путь, воспользуемся соотношением [math] d[i][mask] = w(i, j) + d[j][mask — 2^j] [/math] , которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния [math] i = 0 [/math] , [math] mask = 2^n — 1[/math] , найдем вершину [math]j[/math] , для которой выполняется указанное соотношение, добавим [math]j[/math] в ответ, пересчитаем текущее состояние как [math]i = j[/math] , [math] mask = mask — 2^j [/math] . Процесс заканчивается в состоянии [math]i = 0[/math] , [math] mask = 0 [/math] .

Оптимизация решения методом динамического программирования [ править ]

Пусть [math]d[mask][i][/math] содержит булево значение — существует ли в подмножестве [math]mask[/math] гамильтонов путь, заканчивающийся в вершине [math]i[/math] .

Сама динамика будет такая:
[math] d[mask][i] = left 1&; |mask| = 1, mask_i = 1\ bigvee_limits d[mask oplus 2^i][j] &; |mask| gt 1, mask_i= 1 \ 0&; otherwise\ endright. [/math]

Это решение требует [math]O(2^nn)[/math] памяти и [math]O(2^nn^2)[/math] времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть теперь [math]d'[mask][/math] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве [math]mask[/math] , заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: [math]d'[mask][/math] будет равно [math]sum_limits d[mask][i] cdot 2 ^i [/math] . Для графа [math]G[/math] выпишем [math]n[/math] масок [math]M_i[/math] , для каждой вершины задающие множество вершин, которые связаны ребром с данной вершиной. То есть [math]M_i = sum_limits 2^j cdot ((i, j) in E ? 1:0) [/math] .

Тогда динамика перепишется следующим образом:
[math] d'[mask] = left mask &; |mask| = 1 \ sum_limits 2^i cdot ((d[mask oplus 2^i] & M_i) neq 0?1:0) &; |mask| gt 1 \ 0&; otherwise\ endright. [/math]

Особое внимание следует уделить выражению [math]d[mask oplus 2^i] & M_i[/math] . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве [math]mask[/math] без вершины [math]i[/math] , а вторая — подмножество вершин, связанных с [math]i[/math] ребром. Если эти множества пересекаются хотя бы по одной вершине (их [math]&[/math] не равен [math]0[/math] ), то, как нетрудно понять, в [math]mask[/math] существует гамильтонов путь, заканчивающийся в вершине [math]i[/math] .

Окончательная проверка состоит в сравнении [math]d[2^n — 1][/math] c [math]0[/math] .

Это решение использует [math]O(2^n)[/math] памяти и имеет асимптотику [math]O(2^nn)[/math] .

Псевдокод [ править ]

Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за [math]|mask|[/math] количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния [math]langle i, mask rangle[/math] мы смотрим на состояния

[math]langle j, mask — 2^j rangle[/math] , и [math]|mask| = |mask — 2^j| + 1[/math] , то состояния с большим [math]|mask|[/math] должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).

Дальше ищем сам цикл:

Алгоритм нахождения гамильтонова цикла [ править ]

Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. В массиве [math]d[i][mask][/math] мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает [math] true[/math] , то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.

Алгоритм нахождения гамильтонова пути [ править ]

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

Задача коммивояжера — метод ветвей и границ

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ.

Общий план решения задачи коммивояжера

Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):

  1. Построение матрицы с исходными данными.
  2. Нахождение минимума по строкам.
  3. Редукция строк.
  4. Нахождение минимума по столбцам.
  5. Редукция столбцов.
  6. Вычисление оценок нулевых клеток.
  7. Редукция матрицы.
  8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
  9. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4. Нахождение минимума по столбцам

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути, ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 42314.

Общая длина пути: L = 30.

Практическое применение задачи коммивояжера

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

Решение задачи коммивояжера онлайн

Иногда бывает необходимо быстро просчитать какой-либо вариант для этой задачи или проверить правильность решения. На этот случай я создал сервис для решения задачи коммивояжера онлайн. Воспользоваться им можно перейдя по приведенной здесь ссылке.

© Копирование материала допустимо только при указании прямой гиперссылки на источник: Галяутдинов Р.Р.

Пригодилась статья? Поделитесь с друзьями:

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Задача коммивояжера — метод ветвей и границ // Сайт преподавателя экономики. [2013]. URL: http://galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 04.04.2020).

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

ФОРМУЛЫ —>
ТЕРМИНЫ —>
БУХУЧЕТ —>
НАЛОГИ —>
СТАТИСТИКА —>
БИОГРАФИИ —>
ЗАДАЧИ —>
ENGLISH —>

ГАЛЯУТДИНОВ
Руслан Рамилевич

старший преподаватель экономических дисциплин (маркетинг, логистика, рынок ценных бумаг). подробнее

    Типы рыночных структур: совершенная конкуренция, монополистическая конкуренция, олигополия и монополия

Приступаем к разработке сайта (http://nino.site50.net) Наполняем контент сайта необходимой информацией.

Главная

Об управлении

Одно окно

Задача Коммивояжера код на Php.

Перед тем как вставить Php код на наш сайт не обходимо скачать плагин Sourcerer с сайта (https://extensions.joomla.org/extension/sourcerer/) и установить его на Joomla. После того как мы его установим материалах появится кнопка

Нажимаем на кнопку «<>Код» и вставляем туда код.

Код содержится в административной панели Joomla->Материалы-> Менеджер материалов->

Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.

Формулируется следующим образом:

Пункты обхода плана последовательно включаются в маршрут, причем каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (lowerboundalgorithm).

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

Код PHP. Решение Задачи Коммивояжера методом ближайшего соседа

Читать еще:  Http video converter ru download php
Ссылка на основную публикацию
Adblock
detector