Backtracking

Backtracking este numele unui algoritm general de descoperire a tuturor soluțiilor unei probleme de calcul, algoritm ce se bazează pe construirea incrementală de soluții-candidat, abandonând fiecare candidat parțial imediat ce devine clar că acesta nu are șanse să devină o soluție validă.[1][2][3]

Exemplul de bază folosit în numeroase manuale de liceu și de nivel universitar este problema reginelor, care cere să se găsească toate modurile în care pot fi așezate pe o tablă de șah opt regine astfel încât să nu se atace. În abordarea backtracking, candidatele parțiale sunt aranjamente de câte k regine pe primele k rânduri ale tablei, toate pe rânduri și coloane diferite. Orice soluție parțială ce conține două regine care se atacă poate fi abandonată, deoarece în mod clar restul de regine nu pot fi așezate într-o soluție validă.

Tehnica backtracking se poate aplica doar pentru probleme ce admit conceptul de „candidat parțial de soluție” și oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluție validă. Când se poate aplica, însă, backtrackingul este adesea mult mai rapid decât căutarea prin metoda forței brute prin toți candidații, întrucât este capabilă să elimine dintr-un singur test un mare număr de candidați.

Backtrackingul este util la rezolvarea unor probleme de satisfacere a constrângerilor, cum ar fi cuvintele încrucișate, jocuri de sudoku și alte probleme similare. Ea stă la baza unei serii de limbaje de programare logică, cum ar fi Icon, Planner și Prolog.

Termenul „backtrack” a fost inventat de matematicianul american D. H. Lehmer în anii 1950.[4]

Note

  1. ^ Donald E. Knuth (). The Art of Computer Programming. Addison-Wesley. 
  2. ^ Thomas H. Cormen (). Introduction to Algorithms. McGraw-Hill. 
  3. ^ Gurari, Eitan (). „CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms”. Arhivat din original la . Accesat în . 
  4. ^ Rossi, Francesca (august 2006). „Constraint Satisfaction: An Emerging Paradigm”. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Amsterdam: Elsevier. p. 14. ISBN 978-0-444-52726-4. Accesat în . Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s. 

Read other articles:

Laksamana Sukardi

Laksamana SukardiPotret resmi, 1999 Menteri Negara Badan Usaha Milik Negara Republik Indonesia ke-2Masa jabatan29 Oktober 1999 – 26 April 2000PresidenAbdurrahman Wahid PendahuluTanri AbengPenggantiM. Rozy MunirMasa jabatan10 Agustus 2001 – 20 Oktober 2004PresidenMegawati Soekarnoputri PendahuluM. Rozy MunirPenggantiSoegihartoKepala Badan Koordinasi Penanaman Modal ke-5Masa jabatan26 Oktober 1999 – 26 April 2000PresidenAbdurrahman Wahid PendahuluMuhamma...

 

Lloyd Ruby

American racing driver (1928–2009) Lloyd RubyNationality AmericanBornRichard Lloyd Ruby(1928-01-12)January 12, 1928Wichita Falls, Texas, U.S.DiedMarch 23, 2009(2009-03-23) (aged 81)Wichita Falls, Texas, U.S.Championship titles1965, 1966 24 Hours of Daytona Winner 1966 12 Hours of Sebring WinnerAwardsIndianapolis Motor Speedway Hall of Fame (1991) Motorsports Hall of Fame of America (2015)Champ Car career176 races run over 20 yearsYears active1958–1977Best finish3rd – 1964First race...

 

Pro Patria et Libertate Sezione Calcio 1975-1976

Voce principale: Aurora Pro Patria 1919. Pro Patria et Libertate Sezione CalcioStagione 1975-1976Sport calcio Squadra Pro Patria Allenatore Adelio Crespi Presidente Adriano Mancini Serie C16º posto nel girone A. Coppa Italia SemiproEliminata agli Ottavi Maggiori presenzeCampionato: Berra (38) Miglior marcatoreCampionato: Foglia (7) StadioStadio Comunale 1974-1975 1976-1977 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti la Pro Patria et Libertat...

Cirene (figlia di Ipseo)

CireneCirene con il bestiame, di Edward Calvert Nome orig.Κυρήνη Caratteristiche immaginarieSessoFemmina ProfessioneCacciatrice Cirene (in greco antico: Κυρήνη?, Kürḕnē) è un personaggio della mitologia greca ed eponima della città di Cirene e della Cirenaica[1]. Indice 1 Genealogia 2 Mitologia 3 Note 4 Altri progetti 5 Collegamenti esterni Genealogia Figlia del re Lapita Ipseo[2][3][4] (o di Peneo[5]) e di Chlidanope[6]....

 

McLaren 750S

McLaren 750SDescrizione generaleCostruttore McLaren Automotive Tipo principaleBerlinetta Produzionedal 2023 Sostituisce laMcLaren 720S Altre caratteristicheDimensioni e massaLunghezza4569 mm Larghezza1930 mm Altezza1196 mm Passo2670 mm Massa1277 kg AltroAssemblaggioWoking ProgettoSandy Holford[1] Altre antenateMcLaren 650S Stessa famigliaMcLaren 720S La McLaren 750S è un'auto sportiva prodotta dalla casa automobilistica britannica McLaren dal 2023. Indic...

 

Juan Sebastián Molano

Colombian cyclist Juan Sebastián MolanoMolano in 2018Personal informationFull nameJuan Sebastián Molano BenavidesBorn (1994-04-11) 11 April 1994 (age 30)Paipa, ColombiaHeight1.83 m (6 ft 0 in)Weight70 kg (154 lb)Team informationCurrent teamUAE Team EmiratesDisciplinesRoadTrackRoleRiderRider typeSprinterAmateur teams2011–2012Proyectos Alcaldía Paipa2013Fuerzas Armadas–Ejército Nacional2014Coldeportes–Claro Professional teams2015Colombia201...

Armoured cavalry

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Armoured cavalry – news · newspapers · books · scholar · JSTOR (August 2019)Military with armoured vehicles APC by David E. Graves, Vietnam Combat Artists Program, CAT IX, 1969-70. Courtesy of National Museum of the U.S. Army. Armoured cavalry are mil...

 

Земли Чешской короны

Гербы земель чешской короны: щит с клетчатым орлом — Моравия; чёрный орёл в золотом поле — Нижняя Силезия, золотая стена — Верхняя Лужица; золотой орёл в синем поле — Верхняя Силезия; красный вол — Нижняя Лужица; в центре — Богемия Земли Чешской короны при правлении коро...

 

J. Hardin Peterson

American politician J. Hardin PetersonMember of the U.S. House of Representativesfrom Florida's 1st districtIn officeMarch 4, 1933 – January 3, 1951Preceded byHerbert J. DraneSucceeded byChester B. McMullen Personal detailsBornJames Hardin PetersonFebruary 11, 1894Batesburg, South Carolina, USDiedMarch 28, 1978 (aged 84)Lakeland, Florida, USPolitical partyDemocratic James Hardin Peterson (February 11, 1894 – March 28, 1978) was a U.S. Representative from Florida.[...

A Ride for Liberty – The Fugitive Slaves

1862 painting by Eastman Johnson A Ride for Liberty – The Fugitive SlavesBrooklyn Museum versionArtistEastman JohnsonYear1862 (1862)MediumOil on paperboardDimensions55 cm × 66 cm (21 in × 26 in)LocationBrooklyn Museum; Virginia Museum of Fine ArtsAccession40.59a (Brooklyn Museum); 85.644 (Virginia Museum of Fine Arts) A Ride for Liberty – The Fugitive Slaves (1862) is a painting by the American artist Eastman Johnson that depicts a family o...

 

My Wife's Friends

1949 film My Wife's FriendsDirected byHans DeppeWritten byThea BrechtJochen KuhlmeyProduced byGyula TrebitschStarringSonja ZiemannGrethe WeiserGerda MaurusCinematographyHeinz SchnackertzEdited byKlaus DudenhöferMusic byWilli KolloProductioncompanyReal FilmDistributed byHerzog-FilmverleihRelease date 25 August 1949 (1949-08-25) Running time85 minutesCountryWest GermanyLanguageGerman My Wife's Friends (German: Die Freunde meiner Frau) is a 1949 West German comedy film directed b...

 

تيودور بيرجمان (أستاذ جامعي)

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أبريل 2019) تيودور بيرجمان (بالألمانية: Theodor Bergmann)‏    معلومات شخصية الميلاد 7 مارس 1916   برلين  الوفاة 12 يونيو 2017 (101 سنة)   شتوتغارت  مواطنة ألمانيا  إخوة و...

Fyodor Logginovich van Heiden

Russian general and official (1821–1900) In this name that follows Eastern Slavic naming customs, the patronymic is Logginovich and the family name is Heiden. This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and remov...

 

Family Legal Care

This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Family Legal Care – news · newspapers · books · scholar · JSTOR (November 2017) (Learn how and when to remove this message) Family Legal CareFounded1996TypeCommunity-Based Nonprofit OrganizationTax ID no. 13-3910567LocationBrooklyn, NYRevenue U.S. $3,000,000Employees 20Volunteers 50+Website[1] Family Legal...

 

Paper Clip

Paper ClipEpisode The X-FilesNomor episodeMusim 3Episode 2SutradaraRob BowmanPenulisChris CarterKode produksi3X02Tanggal siar29 September 1995Durasi45 menitBintang tamu Mitch Pileggi sebagai Walter Skinner Walter Gotell sebagai Victor Klemper Melinda McGraw sebagai Melissa Scully Sheila Larken sebagai Margaret Scully Nicholas Lea sebagai Alex Krycek William B. Davis sebagai The Smoking Man John Neville sebagai Well-Manicured Man Tom Braidwood sebagai Melvin Frohike Dean Haglund sebagai R...

South African Class 38-000

1992 design of electro-diesel locomotive South African Class 38-000No. 38-012 at Capital Park, 28 September 2006Type and originPower typeElectro-dieselDesignerConsortium, led by SiemensBuilderUnion Carriage & WagonSerial number38-001 to 38-050ModelConsortium Class 38Build date1992-1993Total produced50SpecificationsConfiguration:​ • AARB-B • UICBo'Bo' • CommonwealthBo-BoGauge3 ft 6 in (1,067 mm) Cape gaugeWheel diameter1,054...

 

December 1913

Month of 1913 1913 January February March April May June July August September October November December << December 1913 >> Su Mo Tu We Th Fr Sa 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31   December 21, 1913: The first crossword puzzle is introduced December 12, 1913: The world's most famous painting, stolen from the Louvre Museum two years earlier, is recovered by police in Italy The following events occurred in December 191...

 

Jules Basdevant

Jules Basdevant Hakim Mahkamah InternasionalMasa jabatan1946–1964 Informasi pribadiKebangsaanPrancisProfesiHakim, yuris (1964) Commander of the Legion of Honour (en) Sunting kotak info • L • B Jules Basdevant adalah seorang yuris (ahli hukum) asal Prancis yang dikenal akan kiprahnya sebagai hakim pada Mahkamah Internasional. Ia mulai menjabat sebagai hakim pada mahkamah tersebut pada tahun 1946. Masa baktinya sebagai hakim berakhir pada tahun 1964.[1] Referensi ^ All M...

Албания

У этого топонима есть и другие значения, см. Албания (значения). Республика Албанияалб. Republika e Shqipërisë Флаг Герб Девиз: «алб. Ti, Shqipëri, më jep nder, më jep emrin Shqiptar»«Ты, Албания, даёшь мне честь, даёшь мне имя албанца» Гимн: «Hymni i Flamurit (Объединённые вокруг флага)» Албания на карте м...

 

اللواء 190 دفاع جوي (اليمن)

اللواء 190 ميكا دفاع جوي هو لواء دفاع جوي يمني، يتبع القوات الجوية والدفاع الجوي، [1] يتمركز اللواء في قاعدة الريان الجوية بمدينة المكلا التابعة لمحافظة حضرموت، ضمن عمليات المنطقة العسكرية الثانية.[1] في 15 أغسطس 2015 أصدر الرئيس عبد ربه منصور هادي قراراً بتعيين العميد ا...