КОММИВОЯЖЕР

Коммивояжёр

КОММИВОЯЖЕР

Материал из Posmotre.li

TV Tropes Для англоязычных и желающих ещё глубже ознакомиться с темой в проекте TV Tropes есть статья Traveling Salesman. Вы также можете помочь нашему проекту и перенести ценную информацию оттуда в эту статью.
« Мое первое с ним знакомство произошло после того, как он, вылетев из окна второго этажа, пролетел мимо окна первого этажа, где я в то время жил, – и упал на мостовую.»
— Аркадий Тимофеевич Аверченко, «Рыцарь индустрии»
« Если хочешь получить в глаз, попробуй мне что-либо продать.»
— Народное
« Торговым агентам вход воспрещён.»
— В эту статью

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

Им всё равно, что вы о них думаете, они будут находить вас везде, чтоб продать свой товар, и не отстанут, пока вы это не сделаете — или не пресечёте их гнусные поползновения самым радикальным образом.

Знакомьтесь: это — коммивояжёры, которые уже сидят у вас в печёнках!

Раньше им приходилось денйствительно заниматься вояжами, т. е. обходить/объезжать потенциальных жертв. Единственное, что могло облегчить их деятельность — бумажные письма. Но научно-технический прогресс облегчил им жизнь — нам на горе. Двоюродный брат сабжа, что торгует опиумом для народа — пастырь назойливый.

Литература[править]

  • Теодор Драйзер, «Сестра Кэрри» — Чарльз Друэ.
  • «Хроники Амбера» — Люк, он же Ринальдо, по мнению Мерлина, давно заслужил звание коммивояжёра года, и вообще талант этот всегда при нем.
  • «Досье Дрездена» — Гарри поражается настойчивости фирм в их попытке продать ему современную технику, несмотря на несколько писем с просьбой не посылать каталоги.
  • «Благие знамения» — Кроули чуть ли не ежемесячно меняет номера телефонов, но его всё равно находят. Правда, их фирме не поздоровилось, когда оказалось, что Кроули записал на автоответчик своего непосредственного начальника.
  • А. Аверченко, «Рыцарь индустрии» (см. эпиграф) — пять минут разговора, и вы готовы будете в него стрелять!
  • Космоолухи — все шоарцы. Усугубляет ещё то, что они тут местный Китай и производят товар всей планетой!
  • Стивен Кинг, рассказ «Всё, что ты любил когда-то, ветром унесёт» — один из немногих трагических образов коммивояжёра.
  • Сергей Лукьяненко, «Если вы позвоните прямо сейчас» — к Земле прилетел космический корабль, хозяин которого предложил правительствам всех стран купить различные вещи и даже технологии производства. За золото и бриллианты. И в каждой покупке позже были выявлены существенные изъяны.

Телесериалы[править]

  • «Байки из склепа» — эпизод «Смерть коммивояжёра» несомненно порадует всех, кого заколебали эти товарищи.
  • Оригинальная «Сумеречная зона» — эпизод «[Распродажа,] достойная ангелов». Добродушный коммивояжёр и друг детей Лью Букман выторговал у Смерти отсрочку, сославшись на то, что не может умереть, пока не устроит распродажу, достойную ангелов. Решив, что он обманул Смерть, Лью обещает себе больше ничем не торговать — но, как выясняется, взамен него Смерти требуется другой человек, например, восьмилетняя соседка Букмана. Чтобы спасти девочку, он устраивает распродажу для Смерти — и оба соглашаются, что она вполне достойна ангелов.

Мультсериалы[править]

  • Утиные истории — Бью БезПромах. Эталон и одновременно высмеивание тропа.
  • Черный Плащ — Герберт Мадлфут работает коммивояжёром и сохраняет дружелюбно-доставучую манеру поведения и в домашней обстановке, чем выводит из себя ЧП.

Веб-комиксы[править]

  • «Глубина заблуждения» — Рикки, пародия с педалью в пол. До смеха крутой продаван, в позволяющих это слоях способный буквально на чудеса — но и в реальности не сдающий позиций. Как вам идея продавать отпугивающие коммивояжёров волшебные амулеты? Агентов Смитов? Самого себя своим же друзьям (сработало как телепортация из проигранного боя прямиком в коробку)?
  • В одном фетиш-стрипе EndArt продававший расчёски коммивояжёр выпорол попытавшуюся грубо послать его девицу всем своим ассортиментом, после чего она согласилась купить все.

игры[править]

  • «Розовая Пантера: Фокус-покус» — главный герой, бывший в предыдущей части [шпион]]ом, забросил шпионское ремесло и стал коммивояжёром. Однако приключения настигли его и здесь, потому что недалеко от дома его очередных клиентов проживал самый настоящий колдун.

Телевидение[править]

  • «Городок», серия про «чудесный пылесос». Смотреть, принимая пищу, не рекомендуется.

Прочее[править]

  • В мире SCP Foundation вообще хватает аномальных торгашей, и коммивояжёры тоже присутствуют. Например, SCP-1879 «Торговец в дверях» — настырное гуманоидное нечто, которое впаривает людям всякие вещи от пластинок до атомных бомб, а в обмен также может попросить что угодно с разными последствиями для покупателя, прибегая к исландским методам.
  • «Задача коммивояжёра» в математике — нахождение оптимального пути на графе (который в классической формулировке описывается как набор городов, связанных дорогами) при условии посещения каждого города ровно один раз. Говорят, некий преподаватель, описывая эту задачу своим студентам, давал обоснуй: «Второй раз в тот же город заявляться нельзя — побьют».

Реальная жизнь[править]

  • Старше, чем пар — правда, не намного раньше, но изобретение паровоза распространило их на всю Британскую империю!
  • Известная фраза «Имею скафандр, готов путешествовать Имею X, готов Y» — в оригинале цитата из резюме коммивояжёра 1930-х, имеющего костюм (для представительности) и готового путешествовать (чтобы продавать товар).
  • Дейл Карнеги в молодости был коммивояжером. Благодаря этому опыту он смог написать свои бестселлеры по психологии общения.
  • Наша реальность:
    • Интернет-реклама и бесконечные рекламные паузы на телевидении — они, родимые.
    • Телефонные операторы. 7 СМС-к в неделю с предложением сменить тариф — это в их стиле.
    • Туда же и продавцов сетевых компаний, достающих ВСЕХ своих знакомых с просьбой купить у них «уникальный товар».
    • Менеджеры банков, названивающие с предложениями оформить кредит. И нет, отказы их не останавливают.
      • Зато прекрасно останавливают угрозы подачи заявления о нарушении закона 152-ФЗ о защите персональных данных — разрешения на использование ваших ПД (фамилия, имя, отчество, номер телефона) у них нет, а штрафы за это немаленькие. Так что одной фразы достаточно, чтобы больше никто не звонил — автор правки проверил это лично.
  • Если вы думаете что ВСЁ ЭТО преувеличение, то попробуйте пообщаться с ними сами!
  • Они даже на этом сайте «статьи» создают! Чуть менее чем всегда это безобразие удаляется модераторами после того, как сознательные участники заменяют спам своим ценным мнением об этих козлах. Но в редких случаях из этого лимона можно, следуя заветам этого самого Карнеги, сделать лимонад. Например, статья «никогда не нужно промывать форсунки» выросла из спама.

Источник: https://posmotre.li/%D0%9A%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80

Чем занимается торговый агент? Коммивояжер – это…

КОММИВОЯЖЕР

«Каждый человек что-то продает» — это любимая поговорка американцев. При этом вовсе необязательно заниматься коммерческой деятельностью.

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

Коммивояжер – это…

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

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

В Древнем Риме слово «продавец» было созвучно со словом «мошенник», а покровителем представителей этой хитрой и изворотливой профессии считался Меркурий – бог лукавства.

Коммивояжер – это бродячий торговец, разъездной сбытовой посредник, являющийся промежуточным звеном между фирмой и клиентом, продавцом товара и покупателем. Обычно, он только предлагает товар, рассказывает о достоинствах, заинтересовывает в его приобретении.

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

Некоторые фирмы устанавливают фиксированную ставку, которую сотрудник получит в любом случае, а также используют систему поощрений – премии, надбавки.

Типичный облик коммивояжера

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

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

Еще один неудачный облик типичного торгового агента показан в пьесе «Смерть коммивояжера», где Вилли Лоумен предстает зрителю очень несчастным.

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

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

Многие консультанты очень застенчивые, не умеют красиво изъясняться, но тем не менее подкупают искренностью, желанием помочь, удачной презентацией и т. д.

Главные качества хорошего продавца

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

Для набора кандидатов используются установление контакта со студентами экономических вузов, объявления, конторы по трудоустройству.

Далее следует трудоемкий отбор претендентов, ведь сразу выявить нужные качества бывает довольно проблематично.

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

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

Также консультант должен обладать целеустремленностью, чтобы довести дело до конца.

Два типа коммивояжера

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

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

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

Подход торгового агента к потенциальным покупателям

Быстрое выявление потенциальных покупателей и работа с ними – вот что предполагает эта профессия. Коммивояжер должен самостоятельно создавать клиентскую базу предприятию, на которое он работает. Чтобы отыскать заказчиков, в основном, пользуются отработанными приемами:

  1. Осваивают различные источники информации, собирая клиентскую базу у банкиров, дилеров, поставщиков, неконкурентных коммивояжеров.
  2. У постоянных клиентов запрашивают имена знакомых, которые могут стать потенциальными покупателями.
  3. Вступают в организации, в которых состоят потенциальные клиенты.
  4. Изучают прессу и другие источники данных.
  5. Посещают различные организации, заявляя о своей продукции.

Источник: https://FB.ru/article/133483/chem-zanimaetsya-torgovyiy-agent-kommivoyajer-eto

Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости

КОММИВОЯЖЕР

Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.

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

Метод ветвей и границ

Алгоритм Литтла является частным случаем МВиГ, т.е. в худшем случае его сложность равна сложности полного перебора. Теоретическое описание выглядит следующим образом:

Имеется множетво S всех гамильтоновых циклов рафа. На каждом шаге в S ищется ребро (i, j), исключение которого из маршрута максимально увеличит оценку снизу. Далее происходит разбиение множества на два непересекающихся S1 и S2.

S1 — все циклы, содержащие ребро (i, j) и не содержащие (j, i). S2 — все циклы, не содержащие (i, j). Далее вычисляется оценка снизу для длины пути каждого множества и, если она превышает длину уже найденного решения, множество отбрасывается.

Если нет — множества S1 и S2 обрабатываются так же, как и S.

Алгоритмическое описание

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

Стоит оговориться, что нужно вести учет двух видов бесконечностей — одна добавляется после удаления строки и столбца из матрицы, чтобы не возникало преждевременных циклов, другая — при отбрасывании ребер. Случаи будут рассмотрены чуть позже. Первую бесконечность обозначим как inf1, вторую — inf2. Диагональ заполнена inf1.

  1. Из каждого элемента каждой строки вычитается минимальный элемент данной строки. При этом минимальный элемент строки прибавляется к нижней границе
  2. Из каждого столбца аналогично вычитается минимальный элемент и прибавляется к нижней границе.
  3. Для каждого нулевого элемента M(i, j) вычисляется коэффициент, равный сумме минимальных элементов строки i и столбца j, исключая сам элемент (i, j). Этот коэффициент показывает, насколько гарантированно увеличится нижняя граница решения, если исключить из него ребро (i, j)
  4. Ищется элемент с максимальным коэффициентом. Если их несколько, можно выбрать любой (все равно оставшиеся будут рассмотрены на следующих шагах рекурсии)
  5. Рассматриваются 2 матрицы — M1 и M2. M1 равна M с удаленными строкой i и столбцом j. В ней находится столбец k и строка l, в которых не содержится inf1 и элемент M(k, l) приравнивается inf1. Как было сказано ранее, это необходимо во избежание преждевременных циклов (т.е. на первых этапах (k, l) == (j, i)). Матрица M1 соответствует множеству, сожержащему ребро (i, j). Вместе с удалением столбца и строки ребро (i, j) включается в путь.
  6. M2 равна матрице M, у которой элемент (i, j) равен inf2. Матрица соответствует множетсву путей, не сожержащих ребро (i, j) (важно понимать, что ребро (j, i) при этом не исключается).
  7. Переход к п.1 для матриц M1 и M2.

Эвристика состоит в том, что у матрицы M1 нижняя граница не больше, чем у матрицы M2 и в первую очередь рассматривается ветвь, содержащая ребро (i, j).

Пример

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

Так что приведу шаги поиска оптимального пути для этой матрицы.

0 1 2 3 4
0inf2018128
15inf14711
21218inf611
3111711inf12
45555inf

Пошаговое решение 0 1 2 3 40 inf1 20.00 18.00 12.00 8.001 5.00 inf1 14.00 7.00 11.002 12.00 18.00 inf1 6.00 11.003 11.00 17.00 11.00 inf1 12.004 5.00 5.00 5.00 5.00 inf1 After subtracting: 0 1 2 3 40 inf1 12.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 12.00 inf1 0.00 5.003 0.00 6.00 0.00 inf1 1.004 0.00 0.00 0.00 0.00 inf1 edge (4, 1) 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 2.00 inf12 6.00 inf1 0.00 5.003 0.00 0.00 inf1 1.00 After subtracting: 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 2.00 inf12 6.00 inf1 0.00 5.003 0.00 0.00 inf1 1.00 edge (3, 2) 0 3 40 inf1 4.00 0.001 0.00 2.00 inf12 6.00 inf1 5.00 After subtracting: 0 3 40 inf1 2.00 0.001 0.00 0.00 inf12 1.00 inf1 0.00 edge (0, 4) 0 31 inf1 0.002 1.00 inf1 candidate solution(4 1) (3 2) (0 4) (1 3) (2 0)cost: 43; record: infNEW RECORD 0 3 40 inf1 2.00 0.001 0.00 0.00 inf12 1.00 inf1 0.00 not edge (0, 4) 0 3 40 inf1 2.00 inf21 0.00 0.00 inf12 1.00 inf1 0.00 After subtracting: 0 3 40 inf1 0.00 inf21 0.00 0.00 inf12 1.00 inf1 0.00 limit: 44; record:43DISCARDING BRANCH 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 2.00 inf12 6.00 inf1 0.00 5.003 0.00 0.00 inf1 1.00 not edge (3, 2) 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 2.00 inf12 6.00 inf1 0.00 5.003 0.00 inf2 inf1 1.00 After subtracting: 0 2 3 40 inf1 1.00 4.00 0.001 0.00 0.00 2.00 inf12 6.00 inf1 0.00 5.003 0.00 inf2 inf1 1.00 limit: 44; record:43DISCARDING BRANCH 0 1 2 3 40 inf1 12.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 12.00 inf1 0.00 5.003 0.00 6.00 0.00 inf1 1.004 0.00 0.00 0.00 0.00 inf1 not edge (4, 1) 0 1 2 3 40 inf1 12.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 12.00 inf1 0.00 5.003 0.00 6.00 0.00 inf1 1.004 0.00 inf2 0.00 0.00 inf1 After subtracting: 0 1 2 3 40 inf1 6.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 6.00 inf1 0.00 5.003 0.00 0.00 0.00 inf1 1.004 0.00 inf2 0.00 0.00 inf1 edge (3, 1) 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 inf1 6.002 6.00 inf1 0.00 5.004 0.00 0.00 0.00 inf1 After subtracting: 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 inf1 6.002 6.00 inf1 0.00 5.004 0.00 0.00 0.00 inf1 edge (0, 4) 0 2 31 0.00 9.00 inf12 6.00 inf1 0.004 inf1 0.00 0.00 After subtracting: 0 2 31 0.00 9.00 inf12 6.00 inf1 0.004 inf1 0.00 0.00 edge (4, 2) 2 32 inf1 0.004 0.00 inf1 candidate solution(3 1) (0 4) (1 0) (2 3) (4 2)cost: 41; record: 43NEW RECORD 0 2 31 0.00 9.00 inf12 6.00 inf1 0.004 inf1 0.00 0.00 not edge (2, 0) 0 2 31 inf2 9.00 inf12 6.00 inf1 0.004 inf1 0.00 0.00 After subtracting: 0 2 31 inf2 0.00 inf12 0.00 inf1 0.004 inf1 0.00 0.00 limit: 56; record:41DISCARDING BRANCH 0 2 3 40 inf1 10.00 4.00 0.001 0.00 9.00 inf1 6.002 6.00 inf1 0.00 5.004 0.00 0.00 0.00 inf1 not edge (0, 4) 0 2 3 40 inf1 10.00 4.00 inf21 0.00 9.00 inf1 6.002 6.00 inf1 0.00 5.004 0.00 0.00 0.00 inf1 After subtracting: 0 2 3 40 inf1 6.00 0.00 inf21 0.00 9.00 inf1 1.002 6.00 inf1 0.00 0.004 0.00 0.00 0.00 inf1 limit: 50; record:41DISCARDING BRANCH 0 1 2 3 40 inf1 6.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 6.00 inf1 0.00 5.003 0.00 0.00 0.00 inf1 1.004 0.00 inf2 0.00 0.00 inf1 not edge (3, 1) 0 1 2 3 40 inf1 6.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 6.00 inf1 0.00 5.003 0.00 inf2 0.00 inf1 1.004 0.00 inf2 0.00 0.00 inf1 After subtracting: 0 1 2 3 40 inf1 0.00 10.00 4.00 0.001 0.00 inf1 9.00 2.00 6.002 6.00 0.00 inf1 0.00 5.003 0.00 inf2 0.00 inf1 1.004 0.00 inf2 0.00 0.00 inf1 limit: 47; record:41DISCARDING BRANCHSolution tour:0 4 2 3 1 0Tour length:41

Шаг 1

Получение нулей в каждой строке и каждом столбце.

double LittleSolver::subtractFromMatrix(MatrixD &m) const { // сумма всех вычтенных значений double subtractSum = 0; // массивы с минимальными элементами строк и столбцов vector minRow(m.size(), DBL_MAX), minColumn(m.size(), DBL_MAX); // обход всей матрицы for (size_t i = 0; i < m.size(); ++i) { for (size_t j = 0; j < m.size(); ++j) // поиск минимального элемента в строке if (m(i, j) < minRow[i]) minRow[i] = m(i, j); for (size_t j = 0; j < m.size(); ++j) { // вычитание минимальных элементов из всех // элементов строки, кроме бесконечностей if (m(i, j) < _infinity) { m(i, j) -= minRow[i]; } // поиск минимального элемента в столбце после вычитания строк if ((m(i, j) < minColumn[j])) minColumn[j] = m(i, j); } } // вычитание минимальных элементов из всех // элементов столбца, кроме бесконечностей for (size_t j = 0; j < m.size(); ++j) for (size_t i = 0; i < m.size(); ++i) if (m(i, j) < _infinity) { m(i, j) -= minColumn[j]; } // суммирование вычтенных значений for (auto i : minRow) subtractSum += i; for (auto i : minColumn) subtractSum += i; return subtractSum;}

Шаг 2

Увеличение нижней границы и сравнение ее с рекордом.

// вычитание минимальных элементов строк и столбцов// увеличение нижней границыbottomLimit += subtractFromMatrix(matrix);// сравнение верхней и нижней границif (bottomLimit > _record) { return;}

Шаг 3

Расчет коэффициентов.

double LittleSolver::getCoefficient(const MatrixD &m, size_t r, size_t c) { double rmin, cmin; rmin = cmin = DBL_MAX; // обход строки и столбца for (size_t i = 0; i < m.size(); ++i) { if (i != r) rmin = std::min(rmin, m(i, c)); if (i != c) cmin = std::min(cmin, m(r, i)); } return rmin + cmin;}

Поиск всех нулевых элементов и вычисление их коэффициентов.

// список координат нулевых элементовlist zeros;// список их коэффициентовlist coeffList; // максимальный коэффициентdouble maxCoeff = 0;// поиск нулевых элементовfor (size_t i = 0; i < matrix.size(); ++i) for (size_t j = 0; j < matrix.size(); ++j) // если равен нулю if (!matrix(i, j)) { // добавление в список координат zeros.emplace_back(i, j); // расчет коэффициена и добавление в список coeffList.push_back(getCoefficient(matrix, i, j)); // сравнение с максимальным maxCoeff = std::max(maxCoeff, coeffList.back()); }

Шаг 4

Отбрасывание нулевых элементов с немаксимальными коэффициентами.

{ // область видимости итераторов auto zIter = zeros.begin(); auto cIter = coeffList.begin(); while (zIter != zeros.end()) { if (*cIter != maxCoeff) { // если коэффициент не максимальный, удаление элемента из списка zIter = zeros.erase(zIter); cIter = coeffList.erase(cIter); } else { ++zIter; ++cIter; } }} return zeros;

Шаг 5

Переход к множеству, содержащему ребро с максимальным штрафом.

auto edge = zeros.front();// копия матрицыauto newMatrix(matrix);// из матрицы удаляются строка и столбец, соответствующие вершинам ребраnewMatrix.removeRowColumn(edge.first, edge.second);// ребро iter добавляется к путиauto newPath(path);newPath.emplace_back(matrix.rowIndex(edge.first), matrix.columnIndex(edge.second));// добавление бесконечности для избежания преждевремнного циклаaddInfinity(newMatrix);// обработка множества, содержащего ребро edgehandleMatrix(newMatrix, newPath, bottomLimit);

Шаг 6

Переход к множеству, не содержащему ребро с максимальным штрафом.

// переход к множеству, не сожержащему ребро edge// снова копирование матрицы текущего шагаnewMatrix = matrix;// добавление бесконечности на место iternewMatrix(edge.first, edge.second) = _infinity + 1;// обработка множества, не сожержащего ребро edgehandleMatrix(newMatrix, path, bottomLimit);

Сравнение МВиГ с полным перебором

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

Ниже представлены графики сравнения МВиГ с полным перебором и среднее время работы реализованного мной алгоритма на различном количестве городов. Тестировалось на матрицах для случайно сгенерированных точек.

Сравнение метода ветвей и границ с полным перебором.

Начиная с 9 городов полный перебор заметно проигрывает МВиГ. Начиная с 13 городов полный перебор занимает больше минуты.

Время работы МВиГ на различном количестве городов.

Также был сделан графический интерфейс на Qt с возможностью динамически смотреть на процесс решения. Как раз его рабочая область на гифке в шапке статьи. Итересующиеся могут скомпилировать и потрогать прогу руками.

Желтым цветом обозначен наилучший найденный путь и его длина находится в поле «Tour length».

Черным обозначены ребра, находящиеся в последнем просмотренном наборе.

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

Вместо заключения

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

→ Исходный код

Источник: https://habr.com/ru/post/332208/

Все термины
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: