Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Алгоритм найближчого сусіда один з перших і найбільш простих евристичних методів розв язування задачі комівояжера Віднос

Метод найближчого сусіда

Метод найближчого сусіда

Алгоритм найближчого сусіда — один з перших і найбільш простих евристичних методів розв'язування задачі комівояжера. Відноситься до категорії жадібних алгоритмів. За кожен крок його виконання до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв'язок знайдено і не намагається його покращити.

Пояснення алгоритму

Формулюється таким чином: Алгоритм найближчого сусіда починається в довільній точці та поступово відвідує кожну найближчу точку, яка ще не була відвідана. Пункти обходу плану послідовно включаються до маршруту, причому, кожен черговий пункт, що включається до маршруту, повинен бути найближчим до останнього вибраного пункту серед усіх інших, ще не включених до складу маршруту. Алгоритм завершується, коли відвідано всі точки. Остання точка з'єднується з першою.

Вхідні дані: множина точок V розмірністю N Вихідні дані: маршрут Т, що складається з послідовності відвідування точок множини V

Кроки алгоритму (варіант 1)

  1. Вибрати довільну точку V1
  2. Т1 = V1
  3. Для і=2 до і=N виконати:
  4. Вибрати точку Vi, найближчу до точки Ті-1
  5. Ti = Vi
  6. Т N +1 = V1
  7. Кінець алгоритму

Кроки алгоритму (варіант 2)

  1. Довільно обрати поточну точку
  2. Знайти найкоротше ребро, що сполучає поточну точку з досі ще не відвіданою точкою V
  3. Зробити точку V поточною
  4. Позначити точку V, як відвідану
  5. Коли всі точки розмірності N відвідані, припинити пошук маршруту
  6. Перейти до другого кроку

Алгоритм простий у реалізації, швидко виконується, але, як і інші «жадібні» алгоритми, може видавати неоптимальні рішення. Обчислювальна складність алгоритму — O(n2). Результатом виконання алгоритму найближчого сусіда є маршрут, приблизно на 25% довший від оптимального. Одним з евристичних критеріїв оцінки рішення є правило: якщо шлях, пройдений на останніх кроках алгоритму, зіставний зі шляхом, пройденим на початкових кроках, то можна умовно вважати знайдений маршрут прийнятним, інакше, імовірно, існують кращі рішення. Інший варіант оцінки рішення полягає у використанні алгоритму нижньої граничної оцінки. Другий критерій оцінки рішення полягає в застосуванні алгоритму нижньої граничної оцінки.

Для будь-якої кількості міст більшій за три в задачі комівояжера можна підібрати таке розташування міст (значення відстаней між вершинами графу і вказівка ​​початкової вершини), що алгоритм найближчого сусіда буде видавати найгірше рішення.

Див. також

Примітки

  1. Базилевич Р., Кутельмах Р. «Дослідження ефективності існуючих алгоритмів для розв'язання задачі комівояжера», 2009 [1]
  2. G. Gutin, A. Yeo and A. Zverovich, 2002

Посилання

  • Алгоритм найближчого сусіда на Mathcad Calculation Server
  • Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
  • J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121–127.
  • G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288–298.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Algoritm najblizhchogo susida odin z pershih i najbilsh prostih evristichnih metodiv rozv yazuvannya zadachi komivoyazhera Vidnositsya do kategoriyi zhadibnih algoritmiv Za kozhen krok jogo vikonannya do znajdenoyi chastini marshrutu dodayetsya nove rebro Algoritm pripinyaye robotu koli rozv yazok znajdeno i ne namagayetsya jogo pokrashiti Poyasnennya algoritmuFormulyuyetsya takim chinom Algoritm najblizhchogo susida pochinayetsya v dovilnij tochci ta postupovo vidviduye kozhnu najblizhchu tochku yaka she ne bula vidvidana Punkti obhodu planu poslidovno vklyuchayutsya do marshrutu prichomu kozhen chergovij punkt sho vklyuchayetsya do marshrutu povinen buti najblizhchim do ostannogo vibranogo punktu sered usih inshih she ne vklyuchenih do skladu marshrutu Algoritm zavershuyetsya koli vidvidano vsi tochki Ostannya tochka z yednuyetsya z pershoyu Vhidni dani mnozhina tochok V rozmirnistyu N Vihidni dani marshrut T sho skladayetsya z poslidovnosti vidviduvannya tochok mnozhini V Kroki algoritmu variant 1 Vibrati dovilnu tochku V1 T1 V1 Dlya i 2 do i N vikonati Vibrati tochku Vi najblizhchu do tochki Ti 1 Ti Vi T N 1 V1 Kinec algoritmu Kroki algoritmu variant 2 Dovilno obrati potochnu tochku Znajti najkorotshe rebro sho spoluchaye potochnu tochku z dosi she ne vidvidanoyu tochkoyu V Zrobiti tochku V potochnoyu Poznachiti tochku V yak vidvidanu Koli vsi tochki rozmirnosti N vidvidani pripiniti poshuk marshrutu Perejti do drugogo kroku Algoritm prostij u realizaciyi shvidko vikonuyetsya ale yak i inshi zhadibni algoritmi mozhe vidavati neoptimalni rishennya Obchislyuvalna skladnist algoritmu O n2 Rezultatom vikonannya algoritmu najblizhchogo susida ye marshrut priblizno na 25 dovshij vid optimalnogo Odnim z evristichnih kriteriyiv ocinki rishennya ye pravilo yaksho shlyah projdenij na ostannih krokah algoritmu zistavnij zi shlyahom projdenim na pochatkovih krokah to mozhna umovno vvazhati znajdenij marshrut prijnyatnim inakshe imovirno isnuyut krashi rishennya Inshij variant ocinki rishennya polyagaye u vikoristanni algoritmu nizhnoyi granichnoyi ocinki Drugij kriterij ocinki rishennya polyagaye v zastosuvanni algoritmu nizhnoyi granichnoyi ocinki Dlya bud yakoyi kilkosti mist bilshij za tri v zadachi komivoyazhera mozhna pidibrati take roztashuvannya mist znachennya vidstanej mizh vershinami grafu i vkazivka pochatkovoyi vershini sho algoritm najblizhchogo susida bude vidavati najgirshe rishennya Div takozhGraf najblizhchih susidivPrimitkiBazilevich R Kutelmah R Doslidzhennya efektivnosti isnuyuchih algoritmiv dlya rozv yazannya zadachi komivoyazhera 2009 1 G Gutin A Yeo and A Zverovich 2002PosilannyaAlgoritm najblizhchogo susida na Mathcad Calculation Server Gutin A Yeo and A Zverovich Traveling salesman should not be greedy domination analysis of greedy type heuristics for the TSP Discrete Applied Mathematics 117 2002 81 86 J Bang Jensen G Gutin and A Yeo When the greedy algorithm fails Discrete Optimization 1 2004 121 127 G Bendall and F Margot Greedy Type Resistance of Combinatorial Problems Discrete Optimization 3 2006 288 298

Дата публікації:
Топ