برنامه نویسی

DPLL: همه زمان ها Hit SAT-Solver

Summarize this content to 400 words in Persian Lang

DPLL را وارد کنید! – یک مقدمه

آیا تا به حال به این فکر کرده اید که کامپیوترها چگونه مشکلات SAT را حل می کنند؟ با الگوریتم DPLL، سنگ بنای دنیای معماهای منطقی آشنا شوید. DPLL مخفف چیست؟ بسیار سازندگان آن است Dآویس، پاوتنام، Lاوگمن، و Lاوولند! این یک کلاسیک در زمینه علوم کامپیوتر است که مشکلات پیچیده را با کاوش سیستماتیک راه حل های ممکن ساده می کند.

DPLL چیست؟؟

الگوریتم DPLL برای تعیین میزان رضایت فرمول های منطقی طراحی شده است. این در اصل یک روش “آزمایش و خطا” است، اما پیچیده تر است. این الگوریتم با کاوش سیستماتیک تخصیص‌های ممکن و ساده‌سازی فرمول از طریق تکنیک‌هایی مانند انتشار واحد و حذف واقعی تحت اللفظی کار می‌کند. این فرآیند پیچیدگی مشکل را کاهش می دهد و یافتن راه حل یا اثبات عدم وجود راه حل را آسان تر می کند.

بنابراین، چگونه کار می کند؟

تکثیر واحد: لفظ واحد به TRUE اختصاص داده می شود (زیرا اگر اینطور نباشد، بند و به نوبه خود کل جمله FALSE می شود). هنگامی که یک لفظ (یک واحد) اختصاص داده می شود، تأثیرات بر بندهایی است که شامل نسخه تحت اللفظی یا نفی آن است. دو نکته قابل ذکر است:

1. بند حاوی لفظ است

یک بند درست است اگر هر حرف واقعی درست باشد، حتی اگر لفظهای دیگر هنوز مقادیر صدق نداشته باشند.

از این رو، بند را می توان از لیست بندهای ایجاد کننده مشکل (جمله) حذف کرد.

به عنوان مثال، جمله (A ∨ B ∨ C) اگر A صادق باشد، صرف نظر از مقادیر B و C صادق است.

2. بند حاوی -literal است

اگر جمله ای نادرست باشد، یک جمله نادرست است، که زمانی رخ می دهد که هر یک از لفظ های آن نادرست باشد. این می تواند مدت ها قبل از تکمیل مدل رخ دهد.

بنابراین، لفظ هایی که به دلیل انتساب جدید FALSE می شوند را می توان از بندهای مربوطه حذف کرد.

حذف تحت اللفظی خالص: بعد، در مورد لفظ هایی است که فقط به یک شکل ظاهر می شوند (یا همیشه مثبت یا همیشه منفی) که به آن «لفظ خالص» می گویند. به این موارد TRUE اختصاص داده شده است (به دلایل واضح – لفظی که هرگز نفی نمی‌شود، نمی‌تواند عامل شکست در هنگام تخصیص باشد و فقط به ارضای بند و جمله کمک می کند).
تقسیم کردن: در نهایت، مشکلات فرعی باقی مانده با انتخاب یک متغیر و تخصیص مقدار به آن حل می شوند. اگر مقدار تخصیص داده شده منجر به FAILURE شود، مقدار جایگزین پس از بازگشت به عقب اختصاص داده می شود. برای بهبود بیشتر الگوریتم، می توان از یک اکتشافی برای انتخاب متغیر استفاده کرد.
موفقیت یا شکست: این با بررسی فهرست بندها مشخص می شود. به دلیل انتشار واحد پس از هر تخصیص، ممکن است بندها حذف یا کوتاه شوند.
هیچ بند در لیست به این معنی است که هر بند درست در نظر گرفته شده و از لیست حذف شده است. بنابراین، تکالیف انجام شده تا کنون برگردانده می شوند، که نشان دهنده موفقیت است.
یک بند خالی در لیست نشان می دهد که هر کلمه متعلق به بند FALSE در نظر گرفته شده و از بند حذف شده است. یعنی کل جمله FALSE است و FAILURE (None) برگردانده می شود.

شبه کد

هوش مصنوعی – یک رویکرد مدرن
(نسخه سوم) توسط استوارت جی راسل و پیتر نورویگ

پیاده سازی در پایتون

# Functions
find_pure_literals(clauses)
unit_propagation(clauses, unit)
dpll(clauses, assignmemt)

def find_pure_literals(clauses):
”’ Returns list of pure literals present in the provided list of clauses
”’
pure_literals = [] for clause in clauses:
for literal in clause:
if literal not in pure_literals:
pure_literals.append(literal) # adds all literals
pure_literals = [x for x in pure_literals if -x not in pure_literals] # retains pure literals and filters out others
return pure_literals

def unit_propagation(clauses, unit):
”’ Eliminates the clauses that contain ‘unit’
Shortens the clauses that contain ‘-unit’
Returns the list of clauses after the above modifications
”’
new_clauses = [] for clause in clauses:
if unit in clause:
continue # removing true clauses (clauses with ‘unit’)
new_clause = [x for x in clause if x != -unit] # shortening clauses with ‘-unit’
new_clauses.append(new_clause)
return new_clauses

def dpll(clauses, assignment):
”’
Returns the current assignment if no more clauses in the list
None if empty clauses found (FAILED TO SATISFY)
Assign pure literal TRUE, if any
Assign unit literal TRUE, if any
Choose a variable, assign FALSE, proceed for other literals:
If the result is FAILURE, remove the assignment
(BACKTRACK), assign TRUE and return the result (success
or failure, whatever!)
Else return the result

Note: The assigned pure literals, chosen variables are also propagated just like unit literals
”’
if not clauses:
return assignment

if any([len(clause)==0 for clause in clauses]):
return None

for clause in clauses:
if len(clause)==1: # unit literal
unit = clause.pop()
clauses = unit_propagation(clauses, unit)
assignment.append(unit)
return dpll(clauses, assignment)

pure_literals = find_pure_literals(clauses)
if pure_literals:
for unit in pure_literals:
clauses = unit_propagation(clauses, unit)
assignment.append(unit)
return dpll(clauses, assignment)

variable = clauses[0].pop() # chosen var – first literal in the first clause found in the list of clauses
result = dpll(unit_propagation(clauses, -variable), assignment + [-variable]) # modify clauses, assignments and pass as params
if result:
return result
return dpll(unit_propagation(clauses, variable), assignment + [variable])

# main
cnf1 = [{1, -3, 4}, {-1, 2, 3}, {-2, -3, 4}, {1, -2, 3}, {-1, 2, -4}, {1, 2, -3}, {-1, -2, 3}, {1, -3, -4}, {-1, 3, 4}, {2, -3, 4}] cnf2 = [{1, -2, 3}, {-1, 2, -3}, {1, 2, 3}, {-1, -2, -3}, {1, -3, 4}, {-1, 3, -4}, {2, -3, 4}, {-2, 3, -4}, {1, -2, 4}, {-1, 2, -4}] cnf3 = [{-1, -2}, {-1, -3}, {-2, -3}, {1, 2}, {1, 3}, {2, 3}] cnf_list = [cnf1, cnf2, cnf3] for i,cnf in enumerate(cnf_list):
result = dpll(cnf, [])
if result:
print(f”CNF {i+1} is satisfiable with the following assignment: \n{result}”)
else:
print(f”CNF {i+1} is unsatisfiable\n[]”)

مزایا (و همچنین محدودیت ها:)

من قصد ندارم این پست را بیش از این بگذارم، بنابراین در اینجا یک مرور مختصر در مورد جوانب مثبت و منفی وجود دارد –

DPLL برای بسیاری از مشکلات عملی SAT بسیار کارآمد است (عمدتا به دلیل استفاده از تکنیک های عالی مانند انتشار واحد و حذف واقعی واقعی)
همچنین کامل است (در صورت وجود راه حلی پیدا خواهد کرد)
این الگوریتم اساس بسیاری از حل‌کننده‌های SAT مدرن را تشکیل می‌دهد که در کاربردهای مختلفی مانند اثبات قضیه خودکار، تأیید سخت‌افزار و هوش مصنوعی استفاده می‌شوند. (من فقط آن را از ویکی پدیا نقل کردم، اما هر چه باشد، می دانم که درست است)
در بدترین حالت، الگوریتم DPLL دارای پیچیدگی زمانی نمایی است.
این می تواند مقدار قابل توجهی از حافظه را مصرف کند، به خصوص برای نمونه های بزرگ.
عملکرد می تواند به شدت به اکتشافی مورد استفاده برای انتخاب متغیر و تصمیم گیری وابسته باشد. اکتشافی ضعیف می تواند منجر به جستجوهای ناکارآمد و زمان راه حل طولانی تر شود.

برنامه های کاربردی؟ (من، من…)

در این زمان، می دانید که این الگوریتم برای حل مسائل SAT طراحی شده است. بنابراین، نتیجه می شود که هر مشکلی که بتوان آن را به عنوان مسئله SAT مدل کرد، در واقع با استفاده از DPLL قابل حل است!

نتیجه گیری

شما برای حل مشکلات رضایت‌پذیری در معرض الگوریتم DPLL قرار گرفته‌اید. نتیجه گیری همین است! بنابراین، یک قهوه بگیرید، آستین ها را بالا بزنید و به Plus Ultra روی DPLL بروید. در حال حاضر!

مراجع

این پست به معنای معرفی (سطح تکلیف) در مورد DPLL است. بنابراین، اگر واقعاً به آن علاقه دارید (مثل اینکه می خواهید اکتشافات را برای انتخاب متغیر کاوش کنید)، یک نینجا جستجو در Google شوید (مطمئناً، شما تحقیق خود را انجام داده اید، اما هی، همیشه چیزهای بیشتری برای کشف وجود دارد!)
همچنین، توصیه می کنم خودتان یک بار کتاب درسی را مرور کنید.
من این اسلایدها را واقعا مفید یافتم و قطعا توصیه می کنم.

DPLL را وارد کنید! – یک مقدمه

آیا تا به حال به این فکر کرده اید که کامپیوترها چگونه مشکلات SAT را حل می کنند؟ با الگوریتم DPLL، سنگ بنای دنیای معماهای منطقی آشنا شوید. DPLL مخفف چیست؟ بسیار سازندگان آن است Dآویس، پاوتنام، Lاوگمن، و Lاوولند! این یک کلاسیک در زمینه علوم کامپیوتر است که مشکلات پیچیده را با کاوش سیستماتیک راه حل های ممکن ساده می کند.

DPLL چیست؟؟

الگوریتم DPLL برای تعیین میزان رضایت فرمول های منطقی طراحی شده است. این در اصل یک روش “آزمایش و خطا” است، اما پیچیده تر است. این الگوریتم با کاوش سیستماتیک تخصیص‌های ممکن و ساده‌سازی فرمول از طریق تکنیک‌هایی مانند انتشار واحد و حذف واقعی تحت اللفظی کار می‌کند. این فرآیند پیچیدگی مشکل را کاهش می دهد و یافتن راه حل یا اثبات عدم وجود راه حل را آسان تر می کند.

بنابراین، چگونه کار می کند؟

  • تکثیر واحد: لفظ واحد به TRUE اختصاص داده می شود (زیرا اگر اینطور نباشد، بند و به نوبه خود کل جمله FALSE می شود). هنگامی که یک لفظ (یک واحد) اختصاص داده می شود، تأثیرات بر بندهایی است که شامل نسخه تحت اللفظی یا نفی آن است. دو نکته قابل ذکر است:

1. بند حاوی لفظ است

یک بند درست است اگر هر حرف واقعی درست باشد، حتی اگر لفظهای دیگر هنوز مقادیر صدق نداشته باشند.

از این رو، بند را می توان از لیست بندهای ایجاد کننده مشکل (جمله) حذف کرد.

به عنوان مثال، جمله (A ∨ B ∨ C) اگر A صادق باشد، صرف نظر از مقادیر B و C صادق است.

2. بند حاوی -literal است

اگر جمله ای نادرست باشد، یک جمله نادرست است، که زمانی رخ می دهد که هر یک از لفظ های آن نادرست باشد. این می تواند مدت ها قبل از تکمیل مدل رخ دهد.

بنابراین، لفظ هایی که به دلیل انتساب جدید FALSE می شوند را می توان از بندهای مربوطه حذف کرد.

  • حذف تحت اللفظی خالص: بعد، در مورد لفظ هایی است که فقط به یک شکل ظاهر می شوند (یا همیشه مثبت یا همیشه منفی) که به آن «لفظ خالص» می گویند. به این موارد TRUE اختصاص داده شده است (به دلایل واضح – لفظی که هرگز نفی نمی‌شود، نمی‌تواند عامل شکست در هنگام تخصیص باشد و فقط به ارضای بند و جمله کمک می کند).

  • تقسیم کردن: در نهایت، مشکلات فرعی باقی مانده با انتخاب یک متغیر و تخصیص مقدار به آن حل می شوند. اگر مقدار تخصیص داده شده منجر به FAILURE شود، مقدار جایگزین پس از بازگشت به عقب اختصاص داده می شود. برای بهبود بیشتر الگوریتم، می توان از یک اکتشافی برای انتخاب متغیر استفاده کرد.

  • موفقیت یا شکست: این با بررسی فهرست بندها مشخص می شود. به دلیل انتشار واحد پس از هر تخصیص، ممکن است بندها حذف یا کوتاه شوند.
    هیچ بند در لیست به این معنی است که هر بند درست در نظر گرفته شده و از لیست حذف شده است. بنابراین، تکالیف انجام شده تا کنون برگردانده می شوند، که نشان دهنده موفقیت است.
    یک بند خالی در لیست نشان می دهد که هر کلمه متعلق به بند FALSE در نظر گرفته شده و از بند حذف شده است. یعنی کل جمله FALSE است و FAILURE (None) برگردانده می شود.

شبه کد

هوش مصنوعی – یک رویکرد مدرن
(نسخه سوم) توسط استوارت جی راسل و پیتر نورویگ
الگوریتم DPLL از هوش مصنوعی یک رویکرد مدرن (شکل 7.17)

پیاده سازی در پایتون

# Functions
find_pure_literals(clauses) 
unit_propagation(clauses, unit) 
dpll(clauses, assignmemt)
def find_pure_literals(clauses):
    ''' Returns list of pure literals present in the provided list of clauses
    '''
    pure_literals = []
    for clause in clauses:
        for literal in clause:
            if literal not in pure_literals:
                pure_literals.append(literal) # adds all literals
    pure_literals = [x for x in pure_literals if -x not in pure_literals] # retains pure literals and filters out others
    return pure_literals

def unit_propagation(clauses, unit):
    ''' Eliminates the clauses that contain 'unit'
        Shortens the clauses that contain '-unit'
        Returns the list of clauses after the above modifications
    '''
    new_clauses = []
    for clause in clauses:
        if unit in clause:
            continue # removing true clauses (clauses with 'unit')
        new_clause = [x for x in clause if x != -unit] # shortening clauses with '-unit'
        new_clauses.append(new_clause)
    return new_clauses

def dpll(clauses, assignment):
    '''
    Returns the current assignment if no more clauses in the list
    None if empty clauses found (FAILED TO SATISFY)
    Assign pure literal TRUE, if any
    Assign unit literal TRUE, if any
    Choose a variable, assign FALSE, proceed for other literals: 
        If the result is FAILURE, remove the assignment 
        (BACKTRACK), assign TRUE and return the result (success 
        or failure, whatever!)
        Else return the result

    Note: The assigned pure literals, chosen variables are also propagated just like unit literals
    '''
    if not clauses:
        return assignment

    if any([len(clause)==0 for clause in clauses]):
        return None

    for clause in clauses:
        if len(clause)==1: # unit literal
            unit = clause.pop()
            clauses = unit_propagation(clauses, unit)
            assignment.append(unit)
            return dpll(clauses, assignment)

    pure_literals = find_pure_literals(clauses)
    if pure_literals:
        for unit in pure_literals:
            clauses = unit_propagation(clauses, unit)
            assignment.append(unit)
        return dpll(clauses, assignment)

    variable = clauses[0].pop() # chosen var - first literal in the first clause found in the list of clauses
    result = dpll(unit_propagation(clauses, -variable), assignment + [-variable]) # modify clauses, assignments and pass as params
    if result:
        return result
    return dpll(unit_propagation(clauses, variable), assignment + [variable])

# main
cnf1 = [{1, -3, 4}, {-1, 2, 3}, {-2, -3, 4}, {1, -2, 3}, {-1, 2, -4}, {1, 2, -3}, {-1, -2, 3}, {1, -3, -4}, {-1, 3, 4}, {2, -3, 4}]
cnf2 = [{1, -2, 3}, {-1, 2, -3}, {1, 2, 3}, {-1, -2, -3}, {1, -3, 4}, {-1, 3, -4}, {2, -3, 4}, {-2, 3, -4}, {1, -2, 4}, {-1, 2, -4}]
cnf3 = [{-1, -2}, {-1, -3}, {-2, -3}, {1, 2}, {1, 3}, {2, 3}]
cnf_list = [cnf1, cnf2, cnf3]
for i,cnf in enumerate(cnf_list):
    result = dpll(cnf, [])
    if result:
      print(f"CNF {i+1} is satisfiable with the following assignment: \n{result}")
    else:
      print(f"CNF {i+1} is unsatisfiable\n[]")

مزایا (و همچنین محدودیت ها:)

من قصد ندارم این پست را بیش از این بگذارم، بنابراین در اینجا یک مرور مختصر در مورد جوانب مثبت و منفی وجود دارد –

  • DPLL برای بسیاری از مشکلات عملی SAT بسیار کارآمد است (عمدتا به دلیل استفاده از تکنیک های عالی مانند انتشار واحد و حذف واقعی واقعی)
  • همچنین کامل است (در صورت وجود راه حلی پیدا خواهد کرد)
  • این الگوریتم اساس بسیاری از حل‌کننده‌های SAT مدرن را تشکیل می‌دهد که در کاربردهای مختلفی مانند اثبات قضیه خودکار، تأیید سخت‌افزار و هوش مصنوعی استفاده می‌شوند. (من فقط آن را از ویکی پدیا نقل کردم، اما هر چه باشد، می دانم که درست است)

  • در بدترین حالت، الگوریتم DPLL دارای پیچیدگی زمانی نمایی است.

  • این می تواند مقدار قابل توجهی از حافظه را مصرف کند، به خصوص برای نمونه های بزرگ.

  • عملکرد می تواند به شدت به اکتشافی مورد استفاده برای انتخاب متغیر و تصمیم گیری وابسته باشد. اکتشافی ضعیف می تواند منجر به جستجوهای ناکارآمد و زمان راه حل طولانی تر شود.

برنامه های کاربردی؟ (من، من…)

در این زمان، می دانید که این الگوریتم برای حل مسائل SAT طراحی شده است. بنابراین، نتیجه می شود که هر مشکلی که بتوان آن را به عنوان مسئله SAT مدل کرد، در واقع با استفاده از DPLL قابل حل است!

نتیجه گیری

شما برای حل مشکلات رضایت‌پذیری در معرض الگوریتم DPLL قرار گرفته‌اید. نتیجه گیری همین است! بنابراین، یک قهوه بگیرید، آستین ها را بالا بزنید و به Plus Ultra روی DPLL بروید. در حال حاضر!

مراجع

  • این پست به معنای معرفی (سطح تکلیف) در مورد DPLL است. بنابراین، اگر واقعاً به آن علاقه دارید (مثل اینکه می خواهید اکتشافات را برای انتخاب متغیر کاوش کنید)، یک نینجا جستجو در Google شوید (مطمئناً، شما تحقیق خود را انجام داده اید، اما هی، همیشه چیزهای بیشتری برای کشف وجود دارد!)
  • همچنین، توصیه می کنم خودتان یک بار کتاب درسی را مرور کنید.
  • من این اسلایدها را واقعا مفید یافتم و قطعا توصیه می کنم.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا