Лин-Керниган эвристикалық - Lin–Kernighan heuristic

Бұл мақала саяхатшылардың саяхаттарындағы эвристикалық мәселелер туралы. Графикті бөлуге арналған эвристикалық алгоритмді қараңыз Керниган-Лин алгоритмі.

Жылы комбинаторлық оңтайландыру, Лин-Керниган ең жақсылардың бірі эвристика симметриялы шешуге арналған сатушы мәселесі. Қысқаша айтқанда, бұл жаңа тур жасау үшін суб-турлардың жұптарын ауыстыруды көздейді. Бұл жалпылау 2-таңдау және 3-таңдау. 2-опт және 3-опт экскурсияны қысқарту үшін екі немесе үш шетін ауыстыру арқылы жұмыс істейді. Линь-Керниган бейімделгіш және әр қадамда қысқа тур табу үшін қалалар арасындағы қанша жолды ауыстыру керек екенін шешеді.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  • Лин, Шен; Керниган, В.В. (1973). «Саяхатшы-сатушы мәселесінің тиімді эвристикалық алгоритмі». Операцияларды зерттеу. 21 (2): 498–516. дои:10.1287 / opre.21.2.498.
  • К.Хельсгаун (2000). «Лин-Керниганның саяхатшы-эвристикасын тиімді жүзеге асыру». Еуропалық жедел зерттеу журналы. 126 (1): 106–130. CiteSeerX  10.1.1.180.1798. дои:10.1016 / S0377-2217 (99) 00284-2.
  • Джонсон, Дэвид С .; McGeoch, Lyle A. (1997). «Саяхатшылардың саяхаты: жергілікті оңтайландырудағы мысал» (PDF). E. H. L. Aarts-та; Лента Дж (ред.). Комбинаторлық оңтайландырудағы жергілікті іздеу. Лондон: Джон Вили және ұлдары. 215–310 бб.

Сыртқы сілтемелер