Geri izleme - Backtracking

İçin hat arama kullanılan algoritma kısıtsız optimizasyon , bkz Geri İzleme hat araması .
Grafik ve ağaç
arama algoritmaları
Listeler
İlgili konular

Geri izleme , çözümlere aşamalı olarak adaylar oluşturan ve adayın geçerli bir şekilde tamamlanamayacağını belirlediği anda adayı terk eden ("geri izlemeler") başta kısıt memnuniyet sorunları olmak üzere bazı hesaplama sorunlarına çözüm bulmak için genel bir algoritmadır . çözüm.

Backtracking kullanımının klasik ders kitabı örneğidir sekiz vezir bulmacası sekiz tüm düzenlemeler için sorar, satranç kraliçeler standart üzerinde satranç tahtası , böylece hiçbir kraliçe saldırıları başka. Ortak geri izleme yaklaşımında, kısmi adaylar , tahtanın ilk k sırasındaki, tümü farklı satır ve sütunlardaki k kraliçenin düzenlemeleridir . Karşılıklı saldıran iki kraliçe içeren herhangi bir kısmi çözüm terk edilebilir.

Geri izleme, yalnızca "kısmi aday çözüm" kavramını kabul eden problemler için uygulanabilir ve geçerli bir çözüme tamamlanıp tamamlanmayacağının nispeten hızlı bir testidir. Örneğin, sırasız bir tabloda belirli bir değeri bulmak için işe yaramaz. Bununla birlikte, uygulanabilir olduğunda, tek bir testle birçok adayı ortadan kaldırabileceğinden , geri izleme genellikle tüm adayların kaba kuvvetle numaralandırılmasından çok daha hızlıdır .

Geri izleme, bulmacalar , sözel aritmetik , Sudoku ve diğer birçok bulmaca gibi kısıtlama tatmin problemlerini çözmek için önemli bir araçtır . Genellikle için en uygun tekniktir ayrıştırma için, sırt çantası sorunu ve diğer kombinatoryal optimizasyon problemlerinin. Aynı zamanda Icon , Planner ve Prolog gibi mantıksal programlama dillerinin de temelidir .

Geri izleme , çözülecek sorunu, kısmi adayların yapısını ve bunların tam adaylara nasıl genişletildiğini tanımlayan, kullanıcı tarafından verilen " kara kutu prosedürlerine " bağlıdır . Bu nedenle bir olduğunu metasezgisel diğer birçok meta sezgisel aksine, zaman sınırlı bir miktarda bir sonlu sorununa tüm çözümler bulmak için garanti edilir, her ne kadar - ziyade belirli bir algoritma.

"Geri dönüş" terimi , 1950'lerde Amerikalı matematikçi DH Lehmer tarafından icat edildi . Öncü dizi işleme dili SNOBOL (1962), yerleşik bir genel geri izleme olanağı sağlayan ilk kişi olabilir.

Yöntemin açıklaması

Geri izleme algoritması , prensipte, verilen probleme olası tüm çözümleri vermek için çeşitli şekillerde tamamlanabilen bir dizi kısmi adayı sıralar . Tamamlama, bir dizi aday uzatma adımıyla aşamalı olarak yapılır .

Kavramsal olarak, kısmi adaylar , potansiyel arama ağacı olan bir ağaç yapısının düğümleri olarak temsil edilir . Her kısmi aday, kendisinden tek bir uzatma adımıyla ayrılan adayların ebeveynidir; ağacın yaprakları daha fazla uzatılamayan kısmi adaylardır.

Geri izleme algoritması, bu arama ağacında , kökten aşağıya, derinlik birinci sırasına göre özyinelemeli olarak geçer . Her c düğümünde , algoritma c'nin geçerli bir çözüme tamamlanıp tamamlanmadığını kontrol eder . Yapamazsa, c'de köklenen tüm alt ağaç atlanır ( budanır ). Aksi takdirde, algoritma (1) c'nin kendisinin geçerli bir çözüm olup olmadığını kontrol eder ve eğer öyleyse bunu kullanıcıya bildirir; ve (2) özyinelemeli olarak c'nin tüm alt ağaçlarını numaralandırır . İki test ve her bir düğümün çocukları, kullanıcı tarafından verilen prosedürlerle tanımlanır.

Bu nedenle, algoritma tarafından geçilen gerçek arama ağacı , potansiyel ağacın yalnızca bir parçasıdır. Algoritmanın toplam maliyeti, gerçek ağacın düğüm sayısı ile her bir düğümü elde etme ve işleme maliyetinin çarpımıdır. Potansiyel arama ağacı seçilirken ve budama testi uygulanırken bu gerçek dikkate alınmalıdır.

sözde kod

Sorunları belirli sınıfa backtracking uygulamak için, bir veri sağlamalıdır P çözülecek olan problemin özellikle örneğin altı prosedürel parametreler , kök , reddetmek , kabul , ilk , sonraki ve çıkış . Bu prosedürler, örnek verisi P'yi parametre olarak almalı ve aşağıdakileri yapmalıdır:

  1. root ( P ): kısmi adayı arama ağacının köküne döndürür.
  2. reddet ( P , c ): yalnızca kısmi aday c tamamlanmaya değmiyorsa true değerini döndürür .
  3. kabul ( P , C ) geri doğru ise C bir çözüm P ve yanlış aksi.
  4. first ( P , c ): c adayının ilk uzantısını oluşturur .
  5. aşağıdaki ( P , s ): dahili sonra bir adayın aşağıdaki alternatif bir uzantıya oluşturmak s .
  6. çıkış ( P , C ) çözeltisi kullanmak c ait P uygulamasına uygun olarak,.

Geri izleme algoritması, sorunu geri arama izleme ( root ( P ) ) sorununa indirger , burada geri izleme aşağıdaki özyinelemeli prosedürdür: 

procedure backtrack(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(s)
        s ← next(P, s)

Kullanım konuları

Reddetmek prosedür olmalıdır boolean değerli işlev olduğu döndürür gerçek bunun hiçbir olası uzatma kesindir yalnızca c için geçerli bir çözümdür P . Prosedür kesin bir sonuca varamazsa, false döndürmelidir . Yanlış bir gerçek sonucu yol açabilir bt bazı geçerli çözümler kaçırmak prosedürü. Prosedür varsayabiliriz red ( P , T ) geri false her soy için t ait c ara ağacında.

Öte yandan, geri izleme algoritmasının verimliliği , köke mümkün olduğunca yakın olan adaylar için doğru döndürmeyi reddetmeye bağlıdır . Eğer reddetmek her zaman döndürür false , algoritma hala tüm çözümler bulmak, ancak bir kaba kuvvet arama eşit olacaktır.

Kabul prosedürü dönmelidir doğruysa eğer c tam ve geçerli bir problem örneği için çözüm P ve sahte aksi. Kısmi aday c'nin ve ağaçtaki tüm atalarının reddetme testini geçtiğini varsayabilir .

Yukarıdaki genel sözde kod, geçerli çözümlerin her zaman potansiyel arama ağacının yaprakları olduğunu varsaymaz. Başka bir deyişle, P için geçerli bir çözümün başka geçerli çözümler elde etmek için daha da genişletilebileceği olasılığını kabul eder .

Birinci ve sonraki işlemler bir düğüm çocukların numaralandırmak için backtracking algoritması tarafından kullanılan c olan ağacın, farklı adaylar c tek bir uzatma aşaması. first ( P , c ) çağrısı bir sırayla c öğesinin ilk çocuğunu vermelidir ; ve çağrı aşağıdaki ( P , s ) düğüm sonraki eş döndürmelidir ler bu sırayla,. İstenen alt öğe yoksa, her iki işlev de ayırt edici bir "NULL" aday döndürmelidir.

Birlikte, kök , ilk ve sonraki fonksiyonlar kısmi adayların seti ve potansiyel arama ağacı tanımlar. P'nin her çözümü ağaçta bir yerde olacak ve hiçbir kısmi aday birden fazla olmayacak şekilde seçilmelidir . Ayrıca, verimli ve etkili bir reddetme yüklemini kabul etmelidirler .

Erken durdurma varyantları

Yukarıdaki sözde kod , verilen P örneğine çözüm olan tüm adaylar için çıktıyı arayacaktır . Algoritma, ilk çözüm veya belirli sayıda çözüm bulunduktan sonra duracak şekilde değiştirilebilir; veya belirli sayıda kısmi adayı test ettikten sonra veya belirli bir miktarda CPU zamanı harcadıktan sonra .

Örnekler

Geri izleme ile çözülen bir Sudoku .

Bulmacaları veya sorunları çözmek için geri izlemenin kullanılabileceği örnekler şunları içerir:

Kısıtlama memnuniyet sorunu için geri izlemenin kullanıldığı bir örnek aşağıdadır :

Kısıtlama memnuniyeti

Genel kısıtlama tatmin problemi , her biri {1, 2, …, m } aralığında olan ve bazılarını tatmin eden x = ( x [1], x [2], …, x [ n ]) tamsayılarının bir listesini bulmaktan ibarettir. keyfi kısıtlama (boole işlevi) F .

Bu problem sınıfı için, örnek verisi P , m ve n tam sayıları ve F yüklemi olacaktır . Bu problemin tipik bir geri izleme çözümünde, kısmi bir aday , 0 ile n arasındaki herhangi bir k için c = ( c [1], c [2], …, c [k]) tamsayılarının bir listesi olarak tanımlanabilir . ilk k değişkene x [1], x [2], …, x [ k ] atanacaktır . Kök adayı daha sonra boş liste () olacaktır. İlk ve sonraki işlemler daha sonra olurdu 

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)

function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Burada uzunluk ( c ), c listesindeki öğelerin sayısıdır .

F kısıtlaması , c'nin k öğesiyle başlayan herhangi bir n tamsayı listesi tarafından karşılanamıyorsa , çağrı reddetme ( P , c ) true dönmelidir . Etkili olduğu yararlar, bazı adaylar için en az, bu durumu tespit etmek için bir yolu olmalı c , bu tüm numaralandırma olmadan m n - k n -tuples.

Örneğin, F olan birlikte birçok mantıksal önermeler, bir F = F [1] ∧ F [2] ∧ ... ∧ F [ p ] , ve her bir E [ I ], sadece değişken küçük bir alt bağlıdır x [1 ], …, x [ n ] , o zaman reddetme prosedürü, yalnızca x [1], …, x [ k ] değişkenlerine bağlı olan F [ i ] terimlerini kontrol edebilir ve bu terimlerden herhangi biri false döndürürse true değerini döndürür . Aslında, yalnızca x [1], …, x [ k − 1]'e bağlı terimler arama ağacında daha fazla test edileceğinden , reddetme yalnızca x [ k ] öğesine bağlı olan terimleri kontrol etmeye ihtiyaç duyar .

Varsayılarak reddetme , daha sonra yukarıdaki gibi uygulanır kabul ( P , C , yalnızca kontrol gerekmektedir) C de sahip olup, olduğu tamamlandıktan n elemanları.

Değişkenlerin listesini en kritik olanlarla başlayacak şekilde sıralamak genellikle daha iyidir (yani en az değer seçeneğine sahip olan veya sonraki seçimler üzerinde daha büyük etkisi olan).

Bir sonraki işlevin, zaten kendisi tarafından atanan değişkenlerin değerlerine dayalı olarak, kısmi bir adayı genişletirken hangi değişkenin atanması gerektiğini seçmesine de izin verilebilir. Kısıt yayılımı tekniği ile daha fazla iyileştirme elde edilebilir .

Yedeklemede kullanılan minimum kurtarma değerlerini korumaya ek olarak, geri izleme uygulamaları genellikle değer değişikliği geçmişini kaydetmek için değişken bir iz tutar. Etkili bir uygulama, seçim noktası olmadığında birbirini izleyen iki değişiklik arasında değişken bir iz girişi oluşturmaktan kaçınacaktır, çünkü geri izleme tüm değişiklikleri tek bir işlem olarak silecektir.

Değişken izine bir alternatif, değişkende son değişikliğin ne zaman yapıldığına dair bir zaman damgası tutmaktır . Zaman damgası, bir seçim noktasının zaman damgasıyla karşılaştırılır. Seçim noktası, değişkenin süresinden daha sonra ilişkili bir zamana sahipse, seçim noktası oluşmadan önce değiştirildiği için, seçim noktası geriye doğru izlendiğinde değişkeni geri almak gereksizdir.

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

Dış bağlantılar