Giải pháp phi hàm mũ để giải quyết vấn đề?

Question

Với biểu đồ tuần hoàn đa hướng có kích thước * n trong đó mỗi nút có tối đa ba trẻ và ba cha mẹ, có một thuật toán không theo hàm mũ để xác định xem có tồn tại đường dẫn n chiều dài không có hai nút chia sẻ cùng một giá trị, và mọi giá trị của một tập hợp được tính?

Về cơ bản, tôi có một mê cung n * n trong đó mỗi không gian có giá trị ngẫu nhiên (1.n). Tôi cần phải tìm một con đường (từ trên xuống dưới) của n nút bao gồm mọi giá trị.

Hiện tại tôi đang sử dụng tìm kiếm theo chiều sâu, nhưng đó là T(n) = 3T(n-1) + O(1), là O(3^n), một giải pháp không lý tưởng.

Hoặc là xác nhận nỗi sợ của tôi hoặc chỉ cho tôi đúng hướng sẽ được đánh giá cao.

Chỉnh sửa: để thực hiện điều này một chút cụ thể hơn, đây là một mê cung với các giải pháp (được giải quyết bằng cách sử dụng giải pháp độ sâu đầu tiên).

 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

Vấn đề này là NP-hoàn chỉnh và do đó không biết có hay không có giải pháp đa thức thời gian. (Các quy định chuẩn có thể dễ thực tế, , v.v., tất cả đều được áp dụng.) Một mức giảm có thể là từ 3SAT.

Giả sử chúng ta có một cá thể 3SAT, chẳng hạn như (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c). Tôi sẽ chỉ cách sử dụng "các tiện ích" để xây dựng một ví dụ về vấn đề của bạn. Trước khi bắt đầu, hãy viết lại bài toán 3SAT dưới dạng (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) cùng với a1 = a2, b1 = b2 và c1 = c2; có nghĩa là, làm cho mỗi lần xuất hiện của một biến duy nhất, nhưng sau đó thêm điều kiện mà các lần xuất hiện khác nhau của cùng một biến phải bằng nhau.

Trước tiên, chúng tôi đảm bảo rằng bạn phải chọn số 0 ở hàng đầu tiên, để chúng tôi có thể sử dụng số này sau này dưới dạng "dấu gửi" mà bạn phải tránh.

0 0 0 

Bây giờ, chúng ta xây dựng một tiện ích mà thực thi các quy tắc a1 = a2: (Các gạch _ đây là một số duy nhất mới trong mỗi lần sử dụng của tiện ích này)

0 _ 0 
a1 0 ¬a1 
a2 0 ¬a2 

Do hàng đầu tiên , bạn phải tránh số 0. Điều này có nghĩa là bạn có đường dẫn "a1, a2" hoặc đường dẫn "¬a1, ¬a2"; trước đây sẽ tương ứng với (hơi gây nhầm lẫn) thiết lập một để sai, trong khi sau này sẽ tương ứng với một thiết lập một sự thật. Điều này là do tiện ích khoản của chúng tôi thực sự dễ dàng, vì chúng tôi chỉ đơn giản viết ra mệnh đề, ví dụ: (Một lần nữa _ đây là một biến mới mỗi lần):

0 _ 0 
a1 b1 b2 

hoặc

0 _ 0 
¬a1 ¬b1 ¬b2 

Cuối cùng, vì bạn chỉ sử dụng một trong những a1 và ¬a1, vv, chúng tôi cho phép bạn lấy những bạn chưa sử dụng tự do:

0 _ 0 
a1 ¬a1 0 

Bây giờ, điều này không hoàn toàn làm việc, bởi vì một trong những a1 và ¬a1 có thể đã được sử dụng trong các tiện ích lựa chọn biến, trong khi người kia có thể đã được sử dụng trong một mệnh đề. Vì vậy, chúng tôi bao gồm một biến mới @i cho mỗi mệnh đề mà bạn có thể thực hiện thay vì một trong các biến. Vì vậy, nếu biến a1 xuất hiện tại khoản 1, ta có

0 _ 0 
a1 ¬a1 @1 

Dưới đây là kết quả hoàn toàn của một bản dịch của mệnh đề 3SAT gốc (làm nổi bật con đường tương ứng với thiết a và b là true, c false, và chọn một từ mệnh đề đầu tiên), với các con số ở bên trái và tô bóng ở bên phải.Các tiện ích được sắp xếp lại (các tiện ích khoản đầu tiên, sau đó cho mỗi biến, tiện ích bình đẳng và sau đó là tiện ích không sử dụng), nhưng điều này không quan trọng vì chúng độc lập.

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 <  

(Nếu bạn muốn toàn bộ hình vuông, chỉ cần bao gồm một số 0 ở cuối mỗi dòng.) Thật thú vị khi thấy bạn giải quyết điều này bằng cách nào, giải quyết vấn đề 3SAT.

Vào cuối bài viết của tôi là một chương trình Perl vội vàng viết mà tạo ra một trong những vấn đề của mình từ một đầu vào có dạng

a b c 
-a -b -c 

Số lượng các biến trong trường hợp kết quả của vấn đề của bạn là 11C + V + 1. Cung cấp cho chương trình chuyển đổi -r để tạo bóng thay vì số.

# 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

Tôi khá chắc chắn điều này có thể được thực hiện trong thời gian đa thức. Tôi sẽ bắt đầu với một tập rỗng và sau đó lặp lại các hàng từ trên xuống dưới. Tôi sẽ bỏ qua bất kỳ loại mã nào và cho bạn biết trạng thái của mỗi trạng thái như thế nào ở mỗi bước bạn sẽ có thể đặt cùng một thuật toán từ đó. Tôi khá chắc chắn trường hợp tốt nhất là hơi tồi tệ hơn O (n^2) bằng cách sử dụng một biến thể của tìm kiếm đầu tiên bề rộng và theo dõi các đường dẫn tốt hiện tại trong một bảng.

EDIT: Nếu điều này vẫn chưa đủ nhanh, bạn có thể cải thiện nó bằng cách áp dụng Harlequin's optimization.

Ví dụ:

Nhà nước 0: R = 0 // Row P = {} // Đường dẫn Đặt

// {{Path so far}, Column} 

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

P = P' 

Tiểu bang 1: R = 1 // ROW 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} 
} 

Nhà nước 2: R = 2 P = { {{1 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} 
} 

quả :
Số lượng đường dẫn: 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

Tra Một tìm kiếm *. Đó là bạn của bạn.

Answer 4

Bạn có thể thử ant colony optimization. Nó nhanh chóng mang lại kết quả rất tốt rất gần với giải pháp hoàn hảo.

Answer 5

Một tối ưu hóa cho Kevin Loney's solution có thể là hợp nhất các đường dẫn một phần có chứa các phần tử giống nhau tại cùng một cột. Bạn sẽ phải lưu ý số lượng hợp nhất với đường dẫn nếu bạn muốn biết số lượng giải pháp ở cuối.

Ví dụ: Trong ví dụ 5x5 của bạn, khi bạn đến hàng thứ ba, cột thứ ba có ba đường dẫn đến nó chứa (1 2 5) theo thứ tự nào đó. Bạn không cần phải làm theo những cách riêng biệt từ thời điểm này, nhưng có thể hợp nhất chúng. Nếu bạn muốn biết số lượng giải pháp ở cuối, bạn chỉ cần điều chỉnh cấu trúc dữ liệu đường dẫn của mình, ví dụ: ba (1 (1 2 5)) sẽ hợp nhất thành (3 (1 2 5)).