Йен алгоритмі - Википедия - Yens algorithm

Йен алгоритмі бір көзді есептейді Қа. үшін қысқа циклсыз жолдар график теріс емес шеті құны.[1] Алгоритмді Джин Йен Йен 1971 жылы жариялады және кез келгенін қолданады ең қысқа алгоритм ең жақсы жолды табу үшін, содан кейін табуға кіріседі Қ - ең жақсы жолдың 1 ауытқуы.[2]

Алгоритм

Терминология және нотация

ЕскертуСипаттама
Графиктің өлшемі, яғни желідегі түйіндер саны.
The графиктің түйіні, мұндағы аралығында болады дейін . Бұл дегеніміз графиктің бастапқы түйіні болып табылады - графиктің раковиналық түйіні.
Арасындағы жиектің құны және , деп ойлаған және .
The бастап ең қысқа жол дейін , қайда аралығында болады дейін . Содан кейін , қайда -ның 2-ші түйіні ең қысқа жол және -ның 3-ші түйіні ең қысқа жол және т.б.
-Дан ауытқу жолы түйінде , қайда аралығында болады дейін . Максималды мәні екенін ескеріңіз болып табылады , бұл раковинаның алдындағы түйін ең қысқа жол. Бұл дегеніміз, ауытқу жолынан ауытқу мүмкін емес раковинадағы ең қысқа жол. Жолдар және дейін дәл сол жолмен жүріңіз түйін, содан кейін жиегі кез келген жолдан өзгеше , қайда аралығында болады дейін .
Түбірлік жолы осыдан шығады дейін түйіні .
Соққысы басталады түйіні және раковинада аяқталады.

Сипаттама

Алгоритмді біріншісін анықтай отырып, екі бөлікке бөлуге болады k-ең қысқа жол, , содан кейін басқаларын анықтау к-ең қысқа жолдар. Бұл контейнер деп болжануда ұстайды к- ең қысқа жол, ал контейнер , әлеуетке ие болады к- ең қысқа жолдар. Анықтау , ең қысқа жол көзден раковинаға дейін, кез-келген тиімді ең қысқа алгоритм пайдалануға болады.

Табу үшін , қайда аралығында болады дейін , алгоритм барлық жолдар деп болжайды дейін бұрын табылған. The барлық ауытқуларды таба отырып, итерацияны екі процеске бөлуге болады және болу үшін минималды ұзындықты таңдау . Бұл қайталануда, аралығында болады дейін .

Бірінші процесті одан әрі үш операцияға бөлуге болады , табу , содан кейін қосу контейнерге . Тамыр жолы, , ішкі жолын табу арқылы таңдалады бұл біріншісіне сәйкес келеді түйіндері , қайда аралығында болады дейін . Содан кейін, егер жол табылса, жолдың құны туралы шексіздікке орнатылған. Келесі, серпінді жол, , түйіннен, түйіннен ең қысқа жолды есептеу арқылы табылады , раковинаға. Алдыңғы пайдаланылған шеттерін алып тастау дейін серпінді жолдың әр түрлі болуын қамтамасыз етеді. , түбірлік жол мен салалық жолдың қосылуы, қосылады . Содан кейін, алынып тасталған шеттер, яғни олардың бағасы шексіздікке орнатылған, бастапқы мәндеріне келтірілген.

Екінші процесс үшін қолайлы жолды анықтайды контейнердегі жолды табу арқылы ең төменгі шығындармен. Бұл жол контейнерден шығарылады және контейнерге салынған алгоритм келесі қайталауға дейін жалғасады.

Псевдокод

Алгоритм Dijkstra алгоритмі екі түйін арасындағы ең қысқа жолды табуда қолданылады деп болжайды, бірақ кез-келген қысқа жол алгоритмін өз орнында пайдалануға болады.

функциясы YenKSP (Графика, дереккөз, раковина, K): // Көзден раковинаға дейінгі ең қысқа жолды анықтаңыз.    A [0] = Dijkstra (График, қайнар көз, раковина); // ықтимал kth қысқа жолды сақтау үшін жиынтықты инициализациялаңыз.    B = []; үшін к бастап 1 дейін K: // Шпор түйіні алдыңғы k-қысқа жолдағы бірінші түйіннен келесі түйінге дейін созылады.        үшін мен бастап 0 дейін өлшемі (A [k - 1]) - 2: // Spur түйіні алдыңғы k-қысқа жолдан алынды, k - 1.            spurNode = A [k-1] .түйін (i); // Алдыңғы k-қысқа жолдың қайнар көзге дейінгі түйіндер тізбегі.            rootPath = A [k-1] .түйіндер (0, i); әрқайсысы үшін жол б жылы Ж: егер rootPath == p.nodes (0, i): // Алдыңғы ең қысқа жолдардың құрамына кіретін сілтемелерді алып тастаңыз, олардың түбірлік жолдары бірдей.                    p.edge (i, i + 1) жою бастап График; әрқайсысы үшін rootPathNode түйіні жылы rootPath қоспағанда spurNode: жою rootPathNode бастап График; // Шпор түйінінен раковинаға дейінгі серпінді жолды есептеңіз.            spurPath = Dijkstra (Graph, spurNode, раковина); // Бүкіл жол түбірлік жол мен шпорлық жолдан тұрады.            totalPath = rootPath + spurPath; // Үйіндіге ықтимал k-қысқа жолды қосыңыз.            егер (totalPath емес B): B.append (totalPath); // Графиктен жойылған шеттер мен түйіндерді қайта қосыңыз.            шеттерін қалпына келтіру дейін График; rootPath тораптарын қалпына келтіру дейін График; егер B бос: // Бұл ешқандай жолсыздықтар немесе ешқандай жолдар қалмаған жағдайды қарастырады.            // Егер бұған жолдар бітіп қалса (А-ға қосылады),             // немесе қозғалатын жолдар мүлдем жоқ - мысалы, қайнар көзі мен раковина шыңдары болған кезде             // «тұйық» бойымен жату.            үзіліс; // Потенциалды k-қысқа жолдарды өзіндік құны бойынша сұрыптаңыз.        B.sort (); // Ең төменгі шығындар жолын қосу k-ең қысқа жолға айналады.        A [k] = B [0]; // Іс жүзінде біз ауысуды қолданғанымыз жөн, өйткені біз бірінші элементті алып тастаймыз        B.pop (); қайту A;

Мысал

Йеннің k-ең қысқа алгоритмі, K = 3, A-дан F-ге дейін

Мысалда Yen's қолданылады Қ-Ден үш жолды есептеуге арналған қысқа жол алгоритмі дейін . Дайкстра алгоритмі бастап ең жақсы жолды есептеу үшін қолданылады дейін , қайсысы құны 5. Бұл жол контейнерге қосылады және бірінші болады к- ең қысқа жол, .

Түйін туралы өзінің тамыр жолымен серпінді түйінге айналады, . Шеті, , жойылды, себебі ол тамыр жолымен және контейнердегі жолмен сәйкес келеді . Дайкстра алгоритмі штрихты есептеу үшін қолданылады , қайсысы , құны 8. контейнерге қосылады әлеует ретінде к- ең қысқа жол.

Түйін туралы түйініне айналады . Шеті, , жойылды, себебі ол тамыр жолымен және контейнердегі жолмен сәйкес келеді . Дайкстра алгоритмі штрихты есептеу үшін қолданылады , қайсысы , құны 7. контейнерге қосылады әлеует ретінде к- ең қысқа жол.

Түйін туралы түбірлік жолмен серпінді түйінге айналады, . Шеті, , жойылды, себебі ол тамыр жолымен және контейнердегі жолмен сәйкес келеді . Дайкстра алгоритмі штрихты есептеу үшін қолданылады , қайсысы , құны 8. контейнерге қосылады әлеует ретінде к- ең қысқа жол.

В контейнеріндегі үш жолдың ішінен болу үшін таңдалады өйткені оның құны 7-ге тең. Бұл процесс 3-ке дейін жалғасады к- ең қысқа жол. Алайда, осы 3-ші қайталану кезінде кейбір серпінді жолдардың жоқтығына назар аударыңыз. Болу үшін таңдалған жол болып табылады .

Ерекшеліктер

Ғарыштың күрделілігі

Графиктің шеттерін сақтау үшін ең қысқа жолдар тізімі және ықтимал қысқа жолдар тізімі , жад мекенжайлары қажет.[2] Нашар жағдайда, графиктегі барлық түйіндер графиктегі басқа түйіндердің шетін иеленеді, осылайша мекен-жай қажет. Тек екі тізімге де мекен-жай қажет және өйткені ең көп дегенде жолдар сақталады,[2] мұнда әр жолдың болуы мүмкін түйіндер.

Уақыттың күрделілігі

Йен алгоритмінің уақыт күрделілігі штрихты есептеу кезінде қолданылатын ең қысқа жол алгоритміне тәуелді, сондықтан Дайкстра алгоритмі қабылданады. Dijkstra алгоритмі жағдайдың уақыт күрделілігінің нашарлығына ие , бірақ Фибоначчи үйіндісін қолдану ол болады ,[3] қайда - графиктегі жиектердің мөлшері. Йеннің алгоритмі жасайды Дидкстраны шақыру жолдарын есептеу кезінде, қайда бұл серпінді жолдардың ұзындығы. Конденсацияланған графикте күтілетін мән болып табылады , ал ең нашар жағдай . , уақыттың күрделілігі болады .[4]

Жақсартулар

Йеннің алгоритмін сақтау үшін үйінді қолдану арқылы жақсартуға болады , потенциал жиынтығы к- ең қысқа жолдар. Тізімнің орнына үйінді пайдалану алгоритмнің жұмысын жақсартады, бірақ күрделілігі емес.[5] Күрделілікті сәл төмендетудің бір әдісі - жоқ серпінді жолдар жоқ түйіндерді өткізіп жіберу. Бұл жағдай цилиндр түйінінен шыққан барлық қозғалмалы жолдар бұрын қолданылған кезде пайда болады . Егер контейнер болса бар контейнерге қатысты минималды ұзындықтағы жолдар , содан кейін оларды бөліп алып, контейнерге салуға болады өйткені қысқа жолдар табылмайды.

Лоулердің модификациясы

Евгений Лоулер Йен алгоритміне модификация ұсынды, онда қайталанатын жол есептелмейді, ал бастапқы алгоритмге қарағанда есептелмейді, содан кейін олар қайталанған кезде жойылады.[6] Бұл қайталанатын жолдар түбірдегі түйіндердің серпінді жолдарын есептеу нәтижесінде пайда болады . Мысалы, ауытқиды кейбір түйінде . Кез келген серпінді жол, қайда , бұл есептелген телнұсқа болады, өйткені олар бұрын есептелген болатын қайталану. Демек, түйіндер үшін серпінді жолдар ғана болатын есептелуі керек, яғни тек қайда аралығында болады дейін . Бұл әрекетті орындау үшін , қай жерде түйінді анықтау үшін жазба қажет тармақталған .

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

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

  1. ^ Yen, Jin Y. (1970). «Жалпы тораптарда барлық көз түйіндерінен берілген бағытқа ең қысқа маршруттарды табудың алгоритмі». Тоқсандық қолданбалы математика. 27 (4): 526–530. дои:10.1090 / qam / 253822. МЫРЗА  0253822.
  2. ^ а б в Yen, Jin Y. (шілде 1971). «The к Желідегі ең қысқа циклсыз жолдар ». Менеджмент ғылымы. 17 (11): 712–716. дои:10.1287 / mnsc.17.11.712. JSTOR  2629312.
  3. ^ Фредман, Майкл Лоуренс; Тарджан, Роберт Е. (1984). Фибоначчи үйінділері және оларды желіні оңтайландыру алгоритмдерінде қолдану. Информатика негіздеріне арналған 25-ші жыл сайынғы симпозиум. IEEE. 338-34 бет. дои:10.1109 / SFCS.1984.715934.CS1 maint: ref = harv (сілтеме)
  4. ^ Булье, Эрик (2007). Торлы оптикалық желілердегі маршруттау. Чичестер, Англия: Джон Вили және ұлдары. ISBN  9780470032985.
  5. ^ Брандер, Эндрю Уильям; Синклер, Марк С. Салыстырмалы зерттеу к-қысқаша жол алгоритмдері. Эссекс Университетінің электронды жүйелер инженері кафедрасы, 1995 ж.
  6. ^ Lawler, EL (1972). «Дискреттік оңтайландыру мәселелеріне арналған k ең жақсы шешімдерді есептеу процедурасы және оны ең қысқа жол мәселесіне қолдану». Менеджмент ғылымы. 18 (7): 401–405. дои:10.1287 / mnsc.18.7.401.

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