Labirent sorununa üstel çözüm mü?

Question

Her düğümün en fazla üç çocuğu ve üç ebeveyni olduğu bir n boyutlu çok başlı asiklik grafik verildiğinde, iki düğümün aynı değeri paylaşmadığı bir n uzunluğundaki yolun var olup olmadığını belirlemek için üstel bir algoritma yoktur. ve bir kümenin her değeri hesaplanıyor mu?

Temel olarak, her alanın rasgele bir değere (1..n) sahip olduğu bir n * n labirentim var. Her değeri içeren n düğümlerinin bir yolunu (yukarıdan aşağıya) bulmalıyım.

Şu anda derinlemesine arama özelliğini kullanıyorum, fakat O(3^n) olan ve ideal olmayan bir çözüm olan T(n) = 3T(n-1) + O(1). Korkularımı doğrulamak ya da beni doğru yöne işaret etmek çok takdir edilecektir.

Düzenleme: Bunu biraz daha somut hale getirmek için, burada çözümleri olan bir labirent (derinlik-ilk çözüm kullanılarak çözüldü).

 1 2 5 5 4 
1 5 1 3 5 
4 1 2 3 2 
5 5 4 4 3 
4 2 1 2 4 
S3, 5, 1, 3, 4, 2, F4 
S3, 5, 1, 3, 4, 2, F2 
S3, 5, 1, 3, 4, 2, F4 
S3, 5, 3, 2, 4, 1, F3 
S3, 5, 3, 2, 4, 1, F3 
S3, 5, 3, 2, 4, 1, F3 
S4, 5, 3, 2, 4, 1, F3 
S4, 5, 3, 2, 4, 1, F3 
S4, 5, 3, 2, 4, 1, F3 
S4, 5, 1, 3, 4, 2, F4 
S4, 5, 1, 3, 4, 2, F2 
S4, 5, 1, 3, 4, 2, F4 
S5, 4, 3, 2, 5, 1, F3 
13 total paths`

Answer 1

Bu sorun NP tamamlandı ve bu nedenle, bir polinom zaman çözümünün bulunup bulunmadığı bilinmiyor. (Muhtemelen pratikte kolay olan standart şartlar, vs., hepsi geçerlidir.) Mümkün olan bir azalma 3SAT'tır.

Örneğin, (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c) gibi bir 3SAT örneğimiz olduğunu varsayalım. Sorunun bir örneğini oluşturmak için "gadget'ları" nasıl kullanacağımı göstereceğim. Başlamadan önce, 3SAT problemini a1 = a2, b1 = b2 ve c1 = c2 ile birlikte (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) olarak tekrar yazınız. Yani, her bir değişkenin benzersiz bir oluşumunu yapın, ancak aynı değişkenin farklı oluşumlarının eşit olması şartını ekleyin. Öncelikle, ilk satırda 0 sayısını seçmeniz gerektiğinden emin olun, böylece daha sonra kullanmanız gereken "sentinel" olarak kullanabiliriz. Çünkü ilk satırın

0 _ 0 
a1 0 ¬a1 
a2 0 ¬a2 

(bu gadget her kullanımda yeni bir benzersiz bir sayıdır burada alt çizgi _):

0 0 0 

Şimdi, a1 = a2 üstünlüğünü uyguladığı bir gadget oluşturur 0'lardan kaçınmalısınız. Bu, ya "a1, a2" yolunu ya da "¬a1, ¬a2" yolunu aldığınız anlamına gelir; Birincisi (biraz kafa karıştırıcı bir şekilde) a'ya yanlış olarak karşılık gelecektir, ikincisi ise a'ya doğru bir ayara karşılık gelecektir. Bunun nedeni, fıkra gadget'ımızın gerçekten çok kolay olmasından kaynaklanmaktadır.

0 _ 0 
a1 b1 b2 

veya yalnızca vb a1 ve ¬a1 birini kullandım çünkü Nihayet

0 _ 0 
¬a1 ¬b1 ¬b2 

, size alalım: (yine _ burada yeni bir değişken her zaman olduğu) olanlar özgürce kullanmadığınız: a1 biri ve ¬a1 değişken seçim gadget kullanılmış olabileceğini çünkü diğer bir de kullanılmış olabileceğini iken

0 _ 0 
a1 ¬a1 0 

Şimdi, bu, oldukça işe değil fıkra. Bu nedenle, değişkenlerden biri yerine alabileceğiniz her bir öğe için @i değişkenini ekledik. Değişken a1 Madde 1'de görünen Yani, biz

0 _ 0 
a1 ¬a1 @1 

Burada orijinal 3SAT maddesinin bir çeviri (false c true a ve b ayarı tekabül yolunu vurgular ve bir toplama tam çıkış var olması ilk maddeden), soldaki sayılar ve sağdaki parlaklık.Gadget'lar yeniden sıralanır (ilk madde gadget'ları, daha sonra her değişken için eşitlik gadget'ı ve ardından kullanılmayan gadget), ancak bu zaten bağımsız olduklarından önemli değildir.

0  0 < 0    .  . < .  
0  8 < 0    .  _ < .  
2 < 4  6    a1 < b1  c1  
0  16 < 0    .  _  .  
11  13  15 <   -a2  -b2  -c2<  
0  17 < 0    .  _ < .  
2  0  3 <   a1  .  -a1<  
10  0  11 <   a2  .  -a2<  
0  18 < 0    .  _ < .  
2  3  1 <   a1  -a1  @1 <  
0  19 < 0    .  _  .  
10 < 11  9    a2 < -a2  @2  
0  20 < 0    .  _ < .  
4  0  5 <   b1  .  -b1<  
12  0  13 <   b2  .  -b2<  
0  21 < 0    .  _ < .  
4 < 5  1    b1 < -b1  @1  
0  22 < 0    .  _ < .  
12 < 13  9    b2 < -b2  @2  
0  23 < 0    .  _ < .  
6 < 0  7    c1 < .  -c1  
14 < 0  15    c2 < .  -c2  
0  24 < 0    .  _ < .  
6  7 < 1    c1  -c1< @1  
0  25 < 0    .  _ < .  
14  15  9 <   c2  -c2  @2 <  

(Eğer her şey kare olmasını istiyorsanız, sadece her satırın sonunda sıfır bir demet içerir.) Bu olursa olsun kalbinde, sen bu çözmek nasıl olduğunu görmek için eğlenceli 3SAT sorununun çözümü. Yazımın sonunda

sorunun ortaya çıkan durumda değişken sayısı 11C + V + 1 olan forma

a b c 
-a -b -c 

bir girişten senin sorunlardan birini oluşturan bir aceleyle yazılmış bir Perl programıdır. Programa, sayılar yerine parlaklık üretmek için -r anahtarını verin.

# Set useful output defaults 
$, = "\t"; $\ = "\n"; 

# Process readability option and force sentinel 
my $r = "0"; 
if($ARGV[0] =~ /-r/) { shift; $r = "."; } 
print $r, $r, $r; 

# Clause gadgets 
my(%v, %c, $m, $c); 
$m = 1; 
while(<>) { 
    my(@v, @m); 
    $c = $m++; 
    chomp; @v = split; 
    for my $v (@v) { 
     push @{$v{strip($v)}}, -1; # hack, argh! 
     push @m, ($r ? $v.@{$v{strip($v)}} : $m + neg($v)); 
     $c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c; 
     $v{strip($v)}->[-1] = ($r ? (strip($v).@{$v{strip($v)}}) : $m); 
     $m += 2 unless $r; 
    } 
    print $r, newv(), $r; 
    print @m; 
} 

# Variable gadget 
for my $v (sort keys %v) { 
    # Force equal 
    print $r, newv(), $r; 
    for my $n (@{$v{$v}}) { 
     print $n, $r, ($r ? "-".$n : $n+1); 
    } 

    # Unused 
    for my $n (@{$v{$v}}) { 
     print $r, newv(), $r; 
     print $n, ($r ? "-".$n : $n+1), ($r ? "\@".$c{$n} : $c{$n}); 
    } 
} 

# Strip leading - 
sub strip { 
    my($v) = @_; 
    return substr $v, neg($v); 
} 

# Is this variable negative? 
sub neg { 
    my($v) = @_; 
    return "-" eq substr($v, 0, 1); 
} 

# New, unused variable 
sub newv { 
    return "_" if $r; 
    return $m++; 
} 

Answer 2

Polinom zamanında yapılabileceğine eminim. Boş bir setle başlıyorum ve daha sonra satırları yukarıdan aşağıya doğru kaydırırdım. Her türlü kodu atlatacağım ve her adımda durumun nasıl görüneceğini size göstereceğim. Eminim ki en iyi durum, ilk genişlikte bir arama varyasyonunu kullanarak ve bir tablodaki mevcut iyi yolların kaydını tutarak, O (n^2) 'den biraz daha kötüdür.

DÜZENLEME: Bu hala yeterince hızlı değilse, Harlequin's optimization uygulayarak geliştirebilirsiniz. Örnek için

:

durum 0: R = 0 // Sıra p = {} // yol ayarlama

// {{Path so far}, Column} 

P' = { 
    {{1}, 0} 
    {{2}, 1} 
    {{3}, 2} 
} 

P = P' 

durum 1: R = 1 // SIRA p = { {{1}, 0} {{2}, 1} {{3}, 2} }

P' = { 
    {{1 3}, 0} 
    {{1 2}, 1} 
    {{2 3}, 0} 
    {{2 1}, 2} 
    {{3 2}, 1} 
    {{3 1}, 2} 
} 

durum 2: R = 2 p = { {{1 ila 3}, 0} {{1 2 }, 1} {{2 3}, 0} {{2: 1}, 2} {{3 2}, 1} {{3 1}, 2} }

P' = { 
    {{1 3 2}, 1} 
    {{2 3 1}, 0} 
    {{3 2 1}, 0} 
    {{3 2 1}, 2} 
    {{3 1 2}, 1} 
} 

Sonuç :
Yol Sayısı: 5
S1 1 3 2 F2
S2 2 3 1 F1
S3 3 2 1 F1
S3 3 2 1 F3
S3 3 1 2 F2

Answer 3

A * arama bak. Bu senin arkadaşın.

Answer 4

ant colony optimization'u deneyebilirsiniz. Hızlı bir şekilde mükemmel çözümlere çok yakın olan çok iyi sonuçlar verir.

Answer 5

Kevin Loney's solution için bir optimizasyon, aynı öğeler içeren aynı öğeleri içeren kısmi yolları birleştirmek olabilir. Sonunda çözüm sayısını bilmek istiyorsanız, yol ile birleştirme sayısını not etmeniz gerekir.

Örnek: 5x5 örneğinizde, üçüncü satıra geldiğinizde, üçüncü sütunda, bir sırayla (1 2 5) içeren üç yolu vardır. Bunları ayrı ayrı takip etmek zorunda değilsiniz, ama onları birleştirebilirsiniz. Sonunda çözüm sayısını bilmek istiyorsanız, sadece yol veri yapınızı ayarlamanız gerekir, ör. üç (1 (1 2 5)) (3 (1 2 5)) ile birleşirdi.