حل غير الأسي لالمتاهة المشكلة؟

Question

ونظرا ل* ن الحجم برئاسة متعددة الرسم البياني احلقي حيث كل عقدة لديه ثلاثة على الأكثر أطفال وثلاثة آباء، هناك خوارزمية غير الأسي لتحديد ما إذا كان مسار ن طول موجود حيث تشترك أي عقدتين نفس القيمة ويتم احتساب قيمة كل مجموعة ل؟

والأساس، ولدي ن * ن المتاهة حيث كل مساحة له قيمة عشوائية (1..n). ولست بحاجة لإيجاد مسار (من أعلى إلى أسفل) من العقد ن يتضمن كل قيمة.

والآن أنا باستخدام البحث بالعمق أولا، ولكن هذا هو T(n) = 3T(n-1) + O(1)، وهو O(3^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

وهذه المشكلة هي NP-كاملة، وحتى لا يعرف ما إذا كان أو لم يكن هناك حل وقت متعدد الحدود. (والفقرات الشرطية القياسية ربما يكون من السهل عمليا، <م> غيرها. ، وتطبيق جميع.) واحدة خفض محتمل هو من 3SAT.

ونفترض أن لدينا مثيل 3SAT، مثل (أ ∨ ∨ ب ج) ∧ (¬a ∨ ∨ ¬b ¬c). وسوف تظهر كيفية استخدام "الأدوات" لبناء مثيل مشكلتك. قبل أن نبدأ، كتابة المشكلة 3SAT باسم (A1 ∨ ∨ B1 C1) ∧ (¬a2 ∨ ∨ ¬b2 ¬c2) جنبا إلى جنب مع = A2 A1، B1 = B2، و C1 = C2. وهذا هو، وجعل لكل تواجد فريدة من نوعها متغير، ولكن بعد إضافة شرط أن حوادث مختلفة من نفس المتغير يجب أن يكون على قدم المساواة.

أولا، أن نتأكد من أنه يجب اختيار الرقم 0 في الصف الأول، حتى نتمكن من استخدامها في وقت لاحق بأنه "الحارس" التي يجب تجنبها.

 0   0   0 

والآن، ونحن نبني الأداة التي تفرض A1 = حكم A2: (إن _ تسطير هنا هو رقم جديد فريد من نوعه في كل استخدام هذه الأداة)

 0   _   0 
 a1  0  ¬a1
 a2  0  ¬a2

ولأن من الصف الأول، يجب تجنب 0S. هذا يعني أنك إما أن تتخذ مسار "A1، A2" أو مسار "¬a1، ¬a2". السابق سوف تقابل (مشوش قليلا) وضع إلى false، في حين أن هذا الأخير سوف تتوافق مع وضع إلى true. وذلك لأن لدينا أداة شرط من السهل حقا ثم، لأننا ببساطة كتابة فقرة، على سبيل المثال (_ مرة أخرى هنا هو متغير جديد في كل مرة):

 0   _   0 
 a1  b1  b2

أو

 0   _   0 
¬a1 ¬b1 ¬b2

وأخيرا، منذ كنت قد استخدمت واحد فقط من A1 و¬a1، وما إلى ذلك، ونحن تمكنك من تلك التي لم تستخدم بحرية:

 0   _   0 
 a1 ¬a1  0 

والآن، وهذا لا يعمل تماما، لأن واحدا من A1 و¬a1 قد تكون استخدمت في اختيار الأداة متغيرة، في حين أن الآخر كان يمكن استخدامها في الشرط. لذلك، نحن تشمل @i متغير جديد لكل بند التي يمكنك اتخاذها بدلا من واحدة من المتغيرات. حتى إذا ظهر A1 متغير في الفقرة 1، لدينا

 0   _   0 
 a1 ¬a1  @1 

وهنا إخراج كاملة من ترجمة للبند 3SAT الأصلي (تسليط الضوء على مسار المقابلة لتحديد وب إلى true، ج إلى false، ويلتقط من الفقرة الأولى)، مع الأرقام على اليسار ومعان على حق. الأدوات يعاد أمر (الأدوات بند أولا، ثم لكل متغير، والأداة المساواة والأداة ثم غير مستخدمة)، ولكن هذا لا يهم حيث انهم مستقل على أي حال.

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 <    

و(إذا كنت تريد كل شيء ليكون مربع، وتشمل مجرد حفنة من الأصفار في نهاية كل سطر). انها متعة أن نرى أن بغض النظر عن كيفية حل هذه، في القلب، وأنت حل هذه المشكلة 3SAT .

وفي نهاية منصبي هو برنامج بيرل كتبت على عجل، الذي يولد واحد من مشاكلك من مدخلات النموذج

a b c
-a -b -c

وعدد من المتغيرات في المقام مما أدى لمشكلتك هو 11C + V + 1. منح برنامج التحول -r لإنتاج معان بدلا من الأرقام.

# 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

وأنا متأكد من هذا يمكن القيام به في الوقت متعدد الحدود. وأود أن تبدأ مع مجموعة فارغة ثم يتكرر خلال الصفوف الأعلى إلى الأسفل. انا ذاهب لتخطي أي نوع من رمز وتظهر لك ما الدولة قد تبدو في كل خطوة يجب أن تكون قادرة على وضع معا خوارزمية من هناك. أنا متأكد من أفضل حالة هي أسوأ قليلا من O (ن ^ 2) باستخدام الاختلاف من اتساع بحث أولا وتتبع مسارات جيدة الحالية في جدول.

تعديل: إذا هذا لا يزال غير سريع بما فيه الكفاية يمكنك تحسينه من خلال تطبيق <وأ href = "https://stackoverflow.com/questions/535859/non-exponential-solution-to -maze-مشكلة / 536189 # 536189 "> المهرج الأمثل .

لمثال:

1 2 3
3 2 1
1 2 1

وحالة 0:     R = 0 // صف     P = {} // مسار مجموعة

// {{Path so far}, Column}

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

P = P'

وحالة 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}
}

والدولة 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}
}

والنتيجة:
    عدد المسار: 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

ويمكنك أن تجرب مستعمرة النمل الأمثل . وسرعان ما تعطي نتائج جيدة للغاية التي هي قريبة جدا من الحل الأمثل.

Answer 4

والأمثل واحدة لحل كيفن لوني في قد يكون ل دمج مسارات الجزئية التي تحتوي على نفس العناصر في نفس العمود. سيكون لديك لاحظ عدد من دمج مع المسار إذا كنت تريد أن تعرف عدد من الحلول في نهاية المطاف.

مثال: في المثال 5X5 الخاص بك، عند وصولك إلى الصف الثالث، العمود الثالث على ثلاثة مسارات المؤدية إليها التي تحتوي على (1 2 5) في بعض الأمر. لم يكن لديك لاتباع هذه بمعزل عن هذه النقطة، ولكن يمكن دمجها. إذا كنت تريد أن تعرف عدد من الحلول في النهاية، لديك فقط لضبط الهيكل الخاص البيانات مسار، على سبيل المثال ثلاثة (1 (1 2 5)) من شأنه دمج ل(3 (1 2 5)).

Answer 5

وابحث عن A * البحث. ومن صديقك.