Пошук з вертанням

Алгоритми пошуку графами та деревами
Переліки
Пов'язані теми

Пошук з вертанням (англ. backtracking), також пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який поступово будує кандидатів на розв'язок, і відкидає кожного неповного кандидата c («вертається») як тільки визначає, що c не може бути доповненим до вірного розв'язку.[1][2][3]

Огляд

Класичний приклад використання пошуку з вертанням — це задача про вісім ферзів, в який потрібно знайти розташування восьми ферзів на стандартній шахівниці таким чином, щоб жоден ферзь не атакував іншого. В звичайному підході пошуку з вертанням, неповні кандидати це розташування k ферзів в перших k рядах дошки, всі в різних рядах і стовпцях. Будь-який неповний розв'язок, що містить два ферзі, які атакують один одного має бути відкинутий, бо він не може бути доведеним до повного правильного розв'язку.

Пошук з вертанням може бути застосований тільки до задач, що дозволяють поняття «неповних кандидатів на розв'язок» і порівняно швидку перевірку на можливість доповнення кандидата до вірного розв'язку. Це корисно, наприклад, для знаходження значення у невпорядкованій таблиці. За можливості застосування, пошук з вертанням часто значно швидший ніж повний перебір всіх можливих кандидатів, через виключення великої кількості кандидатів однією перевіркою.

Пошук з вертанням — це важливе знаряддя для розв'язання проблеми відповідності обмеженням, таких як кросворди, судоку та багато інших головоломок. Часто це найзручніший (якщо не найефективніший) підхід для розбору, для задачі пакування рюкзака та інших задач комбінаторної оптимізації. Це також базис для так званих мов логічного програмування таких як Icon, Planner і Prolog. Пошук з вертанням також використовується в рушії змін (diff) для програмного забезпечення MediaWiki.

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

Англомовний термін «backtrack» був винайдений американським математиком D. H. Lehmer в 1950-х.[4] Піонерська мова опрацювання рядків SNOBOL (1962) можливо першою забезпечила вбудовані засоби загального пошуку з вертанням.

Опис методу

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

Концептуально, неповні кандидати є вузлами деревоподібної структури, потенційне дерево пошуку. Кожний неповний кандидат є батьком кандидатів відмінних від нього на один крок розширення; листям дерева є кандидати які не можуть бути розширені далі.

Алгоритм пошуку з вертанням обходить це дерево пошуку рекурсивно, від кореня донизу, пошуком в глибину. В кожному вузлі c, алгоритм перевіряє чи може c бути доповнене до вірного розв'язку. Якщо ні, ціле піддерево з коренем в c пропускається (обрізається). Інакше, алгоритм (1) перевіряє чи є c вірним розв'язком, і якщо так повідомляє про це користувача; і (2) рекурсивно обходить усі піддерева c. Обидва тести і дочірні вузли кожного вузла визначаються за допомогою поданих користувачем процедур.

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

Псевдокод

Для застосування пошуку з вертанням для певного класу задач, потрібно мати дані P для конкреної задачі, що має бути розв'язана, і шість підпрограм, корінь, відмова, прийняття, перший, наступний, і вихід. Ці підпрограми мають отримувати дані P як параметр і мають бути такими:

  1. корінь(«P»): повертає неповний кандидат в корені дерева пошуку.
  2. відмова(P,c): повертає істину тільки якщо неповний кандидат c невартий завершення.
  3. прийняття(P,c): повертає істину якщо c є розв'язком P, і хибу якщо ні.
  4. перший(P,c): продукує перше розширення кандидата c.
  5. наступний(P,s): продукує інше наступне розширення кандидата, після розширення s.
  6. вихід(P,c): прийняти розв'язок c з P, як підходяще для застосування.

Пошук з вертанням зводиться до виклику bt(root(P)), де bt наступна рекурсивна підпрограма: 

 procedure bt(c)
   якщо відмова(P,c) тоді вийти
   якщо прийняття(P,c) тоді вихід(P,c)
   s ← перший(P,c)
   доки s ≠ Λ робити
     bt(s)
     s ← наступний(P,s)

Див. також

Примітки

  1. ↑ Дональд Кнут (1968). Мистецтво програмування. Addison-Wesley.
  2. ↑ Thomas H. Cormen; Charles E. Leiserson, Ronald R. Rivest, Cliff Stein (1990). Introduction to Algorithms. McGraw-Hill.
  3. ↑ Gurari, Eitan (1999). CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms. Архів Backtracking algorithms оригіналу за 17 березня 2007. Процитовано 19 січня 2011.
  4. ↑ Rossi, Francesca; Beek, Peter Van; Walsh, Toby (August 2006). Constraint Satisfaction: An Emerging Paradigm. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Амстердам: Elsevier. с. 14. ISBN 978-0-444-52726-4. Процитовано 30 грудня 2008. Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.

Read other articles:

Pemindaian port

Pindai Port Pemindaian port (Port Scanner) merupakan aplikasi yang digunakan untuk mendeteksi dan melihat sejumlah informasi atau status dari protokol maupun port yang terbuka (open) dari sebuah perangkat[1]. Port scanner adalah cara untuk mengakses layanan jaringan di komputer. Setiap komputer memiliki bilangan bulat unsigned 16-bit yang berkisar dari 0 sampai 65.535 port yang dapat dibuka atau ditutup suatu waktu.[2] Penggunaan pemindaian port tidak secara keseluruhan diarti...

 

 

Elliot See

Elliot SeeSee pada tahun 1964LahirElliot McKay See Jr.(1927-07-23)23 Juli 1927Dallas, Texas, Amerika SerikatMeninggal28 Februari 1966(1966-02-28) (umur 38)St. Louis, Missouri, Amerika SerikatMakamPemakaman Nasional ArlingtonKebangsaanAmerika SerikatAlmamaterUT AustinUnited States Merchant Marine Academy, B.S. 1949UCLA, M.S. 1962PekerjaanPilot uji coba, insinyur,penerbang angkatan lautKarier luar angkasaastronaut NASAPangkat Komandan, USNRSeleksiNASA Grup 2 1962MisiTidak ada Elliot McKay...

 

 

Lin Bekasi (LRT Jabodebek)

Lin BekasiLangsiran KRL LRT Jabodebek TS2 Lin Bekasi memasuki stasiun JatimulyaIkhtisarNama lainLintas pelayanan 3 LRT JabodebekJenisLintas rel terpadu, transportasi umumSistemLRT JabodebekStatusBeroperasi (Jatimulya–Dukuh Atas)Tahap studi kelayakan (Dukuh Atas–Bandara Soekarno-Hatta)Tahap studi perencanaan (Jatimulya-Karawang)LokasiJakarta Selatan Jakarta TimurKota Bekasi Kabupaten BekasiTerminusJatimulyaDukuh AtasStasiun14OperasiRencana pembukaan28 Agustus 2023[1]PemilikDirektor...

Politique environnementale de l'Union européenne

Cet article pourrait être amélioré en traduisant l'article de Wikipédia en anglais : Environmental policy of the European Union. anglais - Environmental policy of the European Union Si vous connaissez bien la langue suggérée, vous pouvez faire cette traduction. Découvrez comment. Politique environnementale de l'Union européenne Description Politique de l'Union européenne Administration Traité Article 4(2)(e) du TFUEArticle 11 du TFUETitre XX : articles 191 à 193 du TFUE ...

 

 

Leonid Ogul

Russian politician In this name that follows Eastern Slavic naming customs, the patronymic is Anatolievich and the family name is Ogul. You can help expand this article with text translated from the corresponding article in Russian. (February 2024) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accu...

 

 

Tok Aba

Tok AbaTokoh BoBoiBoyPenampilan Tok Aba di BoBoiBoy GalaxyPenampilanperdanaBoBoiBoy Musim 1, Episode 1 (2011)Pengisi suara Anas Abdul Aziz (Bahasa Melayu dan Inggris) Edy Rachmat (Bahasa Indonesia) InformasiAliasTok AbaJulukan Aba Atok, Tok Babas, Tok Abu (BoBoiBoy dan Ochobot) Encik Aba, Bos Aba (Papa Zola,Pak Kumar, Pak Yim) Uncle Aba (Gopal) Papa (Amato) SpesiesManusiaJenis kelaminLaki-LakiPekerjaanPemilik toko Tok Aba dan BoBoiBoy KokotiamKeluarga BoBoiBoy (cucu laki-laki) Ochobot (cucu l...

Baek Ji-young

South Korean singer (born 1976) Not to be confused with Baek Ji Yoon or Baek Ji-hoon. In this Korean name, the family name is Baek. Baek Ji-youngBaek in 2019Born (1976-03-25) March 25, 1976 (age 48)Seoul, South KoreaOccupationSingerYears active1999–presentSpouse Jung Suk-won ​(m. 2013)​Children1Musical careerGenresK-popR&BLabelsMusic Works Musical artistKorean nameHangul백지영Hanja白智榮Revised RomanizationBaek Ji-yeongMcCune–ReischauerPaek...

 

 

The Ox (film)

1992 Swedish filmThe OxUS theatrical posterDirected bySven NykvistScreenplay bySven NykvistLasse SummanenBased onOxenby Siv CederingProduced byJean DoumanianStarring Max von Sydow Ewa Fröling Stellan Skarsgård Erland Josephson Liv Ullmann CinematographySven NykvistEdited byLasse SummanenRelease date 22 November 1992 (1992-11-22) Running time92 minutesCountrySwedenLanguageSwedish The Ox (Swedish: Oxen) is a 1991 Swedish drama film directed by Sven Nykvist. Collaborating with L...

 

 

Radiapoh Hasiholan Sinaga

Ini adalah nama Batak Simalungun, marganya adalah Sinaga. Radiapoh Hasiholan Sinaga Bupati Simalungun ke-16PetahanaMulai menjabat 26 April 2021PresidenJoko WidodoGubernurEdy RahmayadiWakilZonny WaldiPendahuluJR SaragihPenggantiPetahana Informasi pribadiLahir18 Juni 1968 (umur 55)Tiga Runggu, Purba, Simalungun,Sumatera UtaraKebangsaanIndonesiaSuami/istriRatnawati br. SidabutarAnak4Alma materUniversitas BatamPekerjaanPengusahaPolitisiSunting kotak info • L • B Radiapo...

Годзилла

У этого термина существуют и другие значения, см. Годзилла (значения). Годзиллаゴジラ Годзилла на плакате к японскому фильму «Годзилла» (1954) Вселенная Годзилла Официальное название Годзилла (ゴジラ) Первое появление Годзилла (1954) Последнее появление Годзилла и Конг: Новая им...

 

 

詹姆斯·卡拉漢

此條目可参照英語維基百科相應條目来扩充。 (2023年12月1日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 此條目需要补充更多来源。 (2021年4月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能�...

 

 

Textiles of Sumba

Native Indonesian weaving style of Sumbanese Newsreel footage of a 1965 exposition on Sumba textiles at the Museum voor Land- en Volkenkunde, Rotterdam.[1] The textiles of Sumba, an island in eastern Indonesia, represent the means by which the present generation passes on its messages to future generations. Sumbanese textiles are deeply personal; they follow a distinct systematic form but also show the individuality of the weavers and the villages where they are produced. Internationa...

Top Sergeant Mulligan (1941 film)

1941 film by Jean Yarbrough Top Sergeant MulliganTheatrical release posterDirected byJean YarbroughScreenplay byEdmond KelsoProduced byLindsley ParsonsStarringNat PendletonCarol HughesSterling HollowayMarjorie ReynoldsTom NealFrank FaylenCharlie HallCinematographyMack StenglerEdited byJack OgilvieProductioncompanyMonogram PicturesDistributed byMonogram PicturesRelease date October 17, 1941 (1941-10-17) Running time70 minutesCountryUnited StatesLanguageEnglish Top Sergeant Mulli...

 

 

Глава Чеченской Республики

Глава Чеченской Республикичечен. Мехк-Да Штандарт главы Чеченской Республики Должность занимает Рамзан Ахматович Кадыров(врио 15 февраля — 5 апреля 2007) с 5 апреля 2007 года(врио 25 марта — 5 октября 2016) Должность Возглавляет Чеченскую Республику Резиденция Резиденция Главы �...

 

 

Subshrub

Short woody plantLavandula stoechas Linnaea borealis A subshrub (Latin suffrutex) or undershrub is either a small shrub (e.g. prostrate shrubs) or a perennial that is largely herbaceous but slightly woody at the base (e.g. garden pink and florist's chrysanthemum).[1] The term is often interchangeable with bush.[2] Because the criteria are matters of degree (normally of height) rather than of kind, the definition of a subshrub is not sharply distinguishable from that of a shrub...

فامبروفازون

فامبروفازون الاسم النظامي 1-methyl-5-{[methyl(1-phenylpropan-2-yl)amino]methyl}-2-phenyl-4-(propan-2-yl)-1,2-dihydro-3H-pyrazol-3-one اعتبارات علاجية طرق إعطاء الدواء فم معرّفات CAS 22881-35-2 ك ع ت None بوب كيم CID 3326 ECHA InfoCard ID 100.041.153  درغ بنك DB16702  كيم سبايدر 3209 المكون الفريد HN0NCX453C Y ChEMBL CHEMBL1475693 بيانات كيميائية الصيغة ال�...

 

 

Baekjeong

Korean untouchable caste BaekjeongA masked person acting as a baekjeong butcher in a playKorean nameHangul백정Hanja白丁Revised RomanizationBaekjeongMcCune–ReischauerPaekchŏng The baekjeong (Korean: 백정) were an untouchable caste in Korea,[1] originating from some minority, nomadic groups of disputed ethnicity. In the early part of the Goryeo period (918–1392), these minorities were largely settled in fixed communities.[1] However, the Mongol invasion left Korea in ...

 

 

نجم من النوع OB

مجموعة ساطعة من نجوم النوع OB في سحابة ماجلان الكبرى. نجم من النوع OB أو نجم-OB هي نجوم ساخنة وكبيرة الكتلة من الأنواع الطيفية O أو نجوم من النوع المبكر من النوع B على مخطط هرتسبرونغ وراسل. تتشكل نجوم-OB في اتحاد نجمي منظم وحر مكون من 10 إلى 100 نجم ضخم من الأنواع الطيفية O و B، يسمى تجم...

Assembly of Canonical Orthodox Bishops of Canada

Organization of church hierarchs This article forms part of the seriesEastern Orthodox Christianityin North America History History of Eastern Orthodoxy in North America Eastern Orthodoxy in North America timeline Eastern Orthodoxy in the United States bibliography Ligonier Meeting People Saints Bishops Writers Jurisdictions (list) Assembly of Bishops Ecumenical Patriarchate Greek Albanian ACROD Ukrainian Palestinian/Jordanian GOAC UOCC GOMM Antiochian AOAM Russian ROCOR Serbian Romanian Bulg...

 

 

GNOME Office

GNOME Office Тип Офисный пакет Разработчик Проект GNOME Операционная система Кроссплатформенный Последняя версия 2.24 Лицензия GNU GPL Сайт live.gnome.org/GnomeOffi… GNOME Office — набор независимых программ, выполняющий роль офисного пакета проекта GNOME[1]. Содержание 1 Стандартные офисные п�...