NP-Zor & Geri İzleme

Zor

DAA Notes

Sedgewick

M renk kullanarak komşu düğümlerin aynı renge boyanmamasını sağlayan Graf Boyama backtracking algoritmasını ve Cook Teoremi temelli SAT çözücü (DPLL) yaklaşımını ele alır.

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Algoritması

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Açıklaması

Graf Boyama (Graph Coloring), bir grafın köşelerine belirli renkler atanırken, birbirine bağlı hiçbir komşu köşenin aynı rengi almaması kısıtını güden klasik bir NP-Zor problemdir. Karar versiyonu (m renkle boyanabilir mi?) ise NP-Tamdır.

Bu problemi çözmek için en yaygın kesin yöntem M-Boyama Geri İzleme (M-Coloring Backtracking) algoritmasıdır. Düğümler sırayla boyanır, eğer bir komşuluk çakışması olursa geri adım (backtrack) atılarak diğer alternatif renkler denenir.

Cook Teoremi, Boolean Formülünün Karşılanabilirliği (SAT) probleminin ilk NP-Tam problem olduğunu kanıtlamıştır. DPLL (Davis-Putnam-Logemann-Loveland) algoritması, mantıksal formülleri (CNF formatında) çözmek için bir karar ağacı kurup, birim yayılımı (unit propagation) ve saf sembol elemeleriyle arama uzayını daraltan temel bir SAT çözücüdür.

Kaynak Notları

DPLL algoritması, modern endüstriyel SAT çözücülerin (MiniSAT vb.) temelini oluşturur ve çelişki tabanlı öğrenme (CDCL) ile genişletilmiştir.
Harita boyama (Planar Graphs) problemleri en fazla 4 renkle çözülebilir (Dört Renk Teoremi).

Çalışma Prensibi

M-Boyama Geri İzleme:
Boyama fonksiyonunu düğüm 0 ile çağır.
Eğer tüm düğümler başarıyla boyandıysa, çözümü döndür.
Düğüm u için c = 1'den m renk limitine kadar döngü kur:
Düğüm u'yu c rengine boyamanın komşularıyla çakışıp çakışmadığını kontrol et (Safe check).
Çakışmıyorsa, düğüm u'yu c rengine boya ve sonraki düğüm için fonksiyonu özyinelemeli çağır.
Çağrı başarılı olduysa sonucu ilet.
Başarısız olduysa, düğümün rengini sıfırla (backtrack) ve sonraki rengi dene.
Tüm renkler elendiyse başarısızlık döndür.
DPLL SAT Çözücü:
Verilen mantıksal ifadeyi clauses listesi olarak al (CNF: Conjunctive Normal Form).
Eğer tüm clause listesi boşsa (tümü doğruysa), "SATISFIABLE" döndür.
Eğer boş bir clause varsa (çelişki oluştuysa), "UNSATISFIABLE" döndür.
Birim Clause (tek bir değişken içeren clause) varsa, o değişkene değerini ata, sadeleştir ve özyinelemeli çağır (Unit Propagation).
Bir değişken seç ve doğru (True) olduğunu varsay, formülü sadeleştir, çözmeyi dene.
Çözülemezse yanlış (False) olduğunu varsay, çözmeyi dene.
Her iki dal da başarısız olursa "UNSATISFIABLE" döndür.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Algoritması - TypeScript

1export function isColorSafe(
2  node: number,
3  graph: number[][],
4  color: number[],
5  c: number
6): boolean {
7  for (let i = 0; i < graph.length; i++) {
8    if (graph[node][i] === 1 && color[i] === c) {
9      return false;
10    }
11  }
12  return true;
13}
14
15export function graphColoringBacktracking(
16  graph: number[][],
17  m: number,
18  color: number[],
19  node: number
20): boolean {
21  const v = graph.length;
22  if (node === v) return true;
23  
24  for (let c = 1; c <= m; c++) {
25    if (isColorSafe(node, graph, color, c)) {
26      color[node] = c;
27      if (graphColoringBacktracking(graph, m, color, node + 1)) {
28        return true;
29      }
30      color[node] = 0; // Backtrack
31    }
32  }
33  
34  return false;
35}

Kendi Verilerinizle Test Edin

Graf boyama backtracking veya DPLL CNF SAT çözücü adımlarını komşuluk matrisleri ve mantıksal kurallarla izleyin.

Graf Boyama ve DPLL SAT Çözücü

Graf boyama backtracking veya DPLL CNF SAT çözücü adımlarını komşuluk matrisleri ve mantıksal kurallarla izleyin.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(V) - Çelişki bulunmayan durumlar

Ortalama Durum: Üstel - O(m^V)

En Kötü Durum: O(m^V) / O(2^V) - Tüm arama ağacı gezildiğinde

Alan Karmaşıklığı

O(V) - Özyinelemeli çağrı yığını (call stack) derinliği - Bu algoritmanın karmaşıklığı belirtilmemiş.

NP-Zor Karar Ağacı Analizi

M-Boyama probleminde düğüm sıralama stratejileri (örneğin derecesi en yüksek olanı önce boyama) arama derinliğini ve çelişkileri çok daha hızlı fark etmeyi sağlar.
DPLL algoritmasında "Unit Propagation" adımları, arama ağacının derin dallarına inmeden önce milyarlarca olasılığı tek seferde eleyebilir.
Cook-Levin teoremi, 3-SAT probleminin polinomsal sürede başka herhangi bir NP problemine indirgenebileceğini göstermiştir.

Avantajlar ve Dezavantajlar

Avantajlar

Kesin olarak grafın belirtilen m renk ile boyanıp boyanamayacağını veya formülün sağlanabilir olup olmadığını söyler.
Backtracking sayesinde geçersiz atamalar tespit edildiği an geriye dönülerek gereksiz aramalar önlenir.
SAT çözücü yapısı, donanım doğrulama (hardware verification) ve yapay zeka planlama problemlerine birebir uygulanabilir.

Dezavantajlar

Büyük graflarda veya binlerce değişkene sahip SAT formüllerinde arama ağacı devasa hale gelir ve kilitlenmeye yol açabilir.
NP-Zor bir problemi kesin olarak çözmek teorik olarak $P \neq NP$ varsayımında polinomsal sürede imkansızdır.
Hafıza tüketimi olmasa bile işlemciyi uzun süre kilitleyebilir.

İlgili Algoritmalar

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Kaba Kuvvet (Exhaustive Search)

Tüm olası atamaları teker teker deneyen basit ve verimsiz yaklaşım.

Greedy Graf Boyama

Geri izleme yapmadan düğümleri hızlıca boyayan ancak minimum renk sayısını garanti etmeyen sezgisel.

Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Algoritması

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Açıklaması

Kaynak Notları

DPLL algoritması, modern endüstriyel SAT çözücülerin (MiniSAT vb.) temelini oluşturur ve çelişki tabanlı öğrenme (CDCL) ile genişletilmiştir.
Harita boyama (Planar Graphs) problemleri en fazla 4 renkle çözülebilir (Dört Renk Teoremi).

Çalışma Prensibi

M-Boyama Geri İzleme:
Boyama fonksiyonunu düğüm 0 ile çağır.
Eğer tüm düğümler başarıyla boyandıysa, çözümü döndür.
Düğüm u için c = 1'den m renk limitine kadar döngü kur:
Düğüm u'yu c rengine boyamanın komşularıyla çakışıp çakışmadığını kontrol et (Safe check).
Çakışmıyorsa, düğüm u'yu c rengine boya ve sonraki düğüm için fonksiyonu özyinelemeli çağır.
Çağrı başarılı olduysa sonucu ilet.
Başarısız olduysa, düğümün rengini sıfırla (backtrack) ve sonraki rengi dene.
Tüm renkler elendiyse başarısızlık döndür.
DPLL SAT Çözücü:
Verilen mantıksal ifadeyi clauses listesi olarak al (CNF: Conjunctive Normal Form).
Eğer tüm clause listesi boşsa (tümü doğruysa), "SATISFIABLE" döndür.
Eğer boş bir clause varsa (çelişki oluştuysa), "UNSATISFIABLE" döndür.
Birim Clause (tek bir değişken içeren clause) varsa, o değişkene değerini ata, sadeleştir ve özyinelemeli çağır (Unit Propagation).
Bir değişken seç ve doğru (True) olduğunu varsay, formülü sadeleştir, çözmeyi dene.
Çözülemezse yanlış (False) olduğunu varsay, çözmeyi dene.
Her iki dal da başarısız olursa "UNSATISFIABLE" döndür.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Graf Boyama ve NP-Zor (Graph Coloring & Hard Problems) Algoritması - TypeScript

1export function isColorSafe(
2  node: number,
3  graph: number[][],
4  color: number[],
5  c: number
6): boolean {
7  for (let i = 0; i < graph.length; i++) {
8    if (graph[node][i] === 1 && color[i] === c) {
9      return false;
10    }
11  }
12  return true;
13}
14
15export function graphColoringBacktracking(
16  graph: number[][],
17  m: number,
18  color: number[],
19  node: number
20): boolean {
21  const v = graph.length;
22  if (node === v) return true;
23  
24  for (let c = 1; c <= m; c++) {
25    if (isColorSafe(node, graph, color, c)) {
26      color[node] = c;
27      if (graphColoringBacktracking(graph, m, color, node + 1)) {
28        return true;
29      }
30      color[node] = 0; // Backtrack
31    }
32  }
33  
34  return false;
35}

Kendi Verilerinizle Test Edin

Graf boyama backtracking veya DPLL CNF SAT çözücü adımlarını komşuluk matrisleri ve mantıksal kurallarla izleyin.

Graf Boyama ve DPLL SAT Çözücü

Graf boyama backtracking veya DPLL CNF SAT çözücü adımlarını komşuluk matrisleri ve mantıksal kurallarla izleyin.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(V) - Çelişki bulunmayan durumlar

Ortalama Durum: Üstel - O(m^V)

En Kötü Durum: O(m^V) / O(2^V) - Tüm arama ağacı gezildiğinde

Alan Karmaşıklığı

O(V) - Özyinelemeli çağrı yığını (call stack) derinliği - Bu algoritmanın karmaşıklığı belirtilmemiş.

NP-Zor Karar Ağacı Analizi

M-Boyama probleminde düğüm sıralama stratejileri (örneğin derecesi en yüksek olanı önce boyama) arama derinliğini ve çelişkileri çok daha hızlı fark etmeyi sağlar.
DPLL algoritmasında "Unit Propagation" adımları, arama ağacının derin dallarına inmeden önce milyarlarca olasılığı tek seferde eleyebilir.
Cook-Levin teoremi, 3-SAT probleminin polinomsal sürede başka herhangi bir NP problemine indirgenebileceğini göstermiştir.

Avantajlar ve Dezavantajlar

Avantajlar

Kesin olarak grafın belirtilen m renk ile boyanıp boyanamayacağını veya formülün sağlanabilir olup olmadığını söyler.
Backtracking sayesinde geçersiz atamalar tespit edildiği an geriye dönülerek gereksiz aramalar önlenir.
SAT çözücü yapısı, donanım doğrulama (hardware verification) ve yapay zeka planlama problemlerine birebir uygulanabilir.

Dezavantajlar

Büyük graflarda veya binlerce değişkene sahip SAT formüllerinde arama ağacı devasa hale gelir ve kilitlenmeye yol açabilir.
NP-Zor bir problemi kesin olarak çözmek teorik olarak $P \neq NP$ varsayımında polinomsal sürede imkansızdır.
Hafıza tüketimi olmasa bile işlemciyi uzun süre kilitleyebilir.