सर्च एल्गोरिथम (Search Algorithm)

आर्टिफीसियल इंटेलिजेंस में Search algorithm किसी समस्या के समाधान का खोजने का एक व्यापक तरीका है. यहाँ कुछ एकल-खिलाड़ी खेल जैसेकि- सुडोकु, क्रॉसवर्ड आदि हैं, जिनमें search algorithm आपको किसी विशेष स्थिति को खोजने या उस स्थिति में निर्णय लेने में आपकी मदद करती है.

Single Agent Pathfinding Problem

अनेक खेल जैसेकि 3X3 eight-title, 4X4 fifteen title, और 5X5 twenty four title puzzle (पहेली), single agent pathfinding खेल हैं. इसमें अनेक titles की एक matrix (सारणिक) होती है जिसमें अनेक खाली title भी होते हैं. एक खिलाड़ी को इन titles को खाली स्थान पर खिसकाकर लंबवत या आड़ इस तरह से व्यवस्थित करना होता है की वह एक लक्ष्य को पा सके.

Single agent pathfinding problem अन्य उदाहरण हैं- Travelling Salesman Problem, Rubik’s Cube, और Theorem Proving.

Search terminology (शब्दावली)

Problem Space – यह वह environment है जहां search अपना काम करती है. जिसमें states का set, और state को बदलने वाले operators का set सम्मिलित हैं.

Problem Instance - इसमें Initial state + Goal state सम्मिलित हैं.

Problem Space Graph – यह problem state का प्रतिनिधित्व करती है. State को node और operator को edge से दिखाया जाता है.

Depth of a problem – सबसे छोटे रास्ते की लंबाई (Length of a shortest path) या operator की सबसे छोटी श्रृंखला (shortest sequence), Initial State (प्रारंभिक अवस्था) से goal state (लक्ष्य अवस्था) तक.

Space Complexity – node की अधिकतम संख्या जो कि memory में संग्रहित हो सकती है.

Time Complexity – अधिकतम node की संख्या जिनका सृजन किया जा सकता है.

Admissibility − एल्गोरिथम की वह विशेषता जिससे हमेशा optimal solution पाया जा सके.

Branching Factor − Problem space graph में child node की औसत संख्या.

Brute-Force Search Strategies

यह सबसे सरल हैं, क्योंकि इन्हें domain-specific knowledge की जरूरत नहीं होती है. यह कम संख्या में संभावित अवस्थाओं में बहुत अच्छा काम करती है.

इसके लिए निम्न चीजों की जरूरत होती है

· State description (स्थिति का विवरण)

· A set of valid operators (उचित आपरेटर का समुच्चय)

· Initial state (प्रारंभिक स्थिति)

· Goal state description (लक्ष्य का विवरण)

Breadth-First Search

इसमें शुरूआत root node से करते हैं, फिर सबसे पहले neighboring nodes का परीक्षण करते हैं और फिर अगले level के neighbors को देखते हैं. यह एक बार में एक tree को बनाता है जबतक की solution (समाधान) नहीं मिल जाए. इसका उपयोग FIFO (First In First Out) queue data structure का प्रयोग करके भी किया जा सकता है. यह तरीका (method) किसी समस्या का shortest path उपलब्ध करता है.

Theorem: यदि branching factor (किसी node के लिए child node की औसत संख्या) और depth है तब level पर node की संख्या होगी.

Corollary: सबसे खराब स्थिति में create की गई कुल node की संख्या होगी .

दोष- चूकीं प्रत्येक level पर nodes को बचाकर रखा जाता है, अगली node को create करने के लिए, यह काफी ज्यादा memory space घेरती है. Nodes को store करने के लिए Space requirement, exponential होती है.

इसकी complexity, nodes की संख्या पर निर्भर करती है. यह duplicate nodes की जांच कर सकती है.

Depth-First Search

इसका उपयोग Last In First Out (LIFO) data structure में भी किया जाता है. इसमें भी node का वही set मिलता है जैसेकि Breadth-First search में method में मिलता है, केवल उसका क्रम (order) होता है.

प्रत्येक iteration में किसी एक रास्ते (path) में root से leaf तक पड़ने वाली nodes को संग्रहित किया जाता है, इस कारण nodes को संग्रहित करने के लिए space requirement, रैखिक (linear) होती है. यदि branching factor band depth, m है, तब storage space b^m होगी.

दोष – इस एल्गोरिथम को terminate नहीं किया जा सकता है और यह एक ही रास्ते पर अनंत बार (infinitely) जा सकती है. इस समस्या का समाधान है की cut-off depth का प्रयोग करें. यदि आदर्श (ideal) cut-off, d, और यदि चयन किया गया cut-off, d से कम है, तब यह एल्गोरिथम असफल हो सकती है. यदि चयन किया cut-off, d से ज्यादा है, तब निष्पादन का समय (execution time) बढ़ सकता है.

इसकी paths की संख्या पर complexity निर्भर करती है. यह duplicate nodes की जांच नहीं कर सकता है.

Bidirectional Search

यह search आगे की ओर बढ़ती है initial state से और goal state से पीछे की तरफ चलती है जबतक की दोनों मिलने के लिए एक common state की पहचान न कर लें.

चूंकि Initial state से चलने वाला path उस रास्ते से मिलता है जो goal state से उलटा चलता है. प्रत्येक search को total path का आधा ही करना होता है.

Uniform Cost Search

यह सबसे कम कीमत की नोड़ (least cost node) का विस्तार करती हैं. यह Breadth First search के समान ही है यदि विस्तार एक ही लागत (cost) का हो.

यह भिन्न रास्तों (paths) को बढ़ती कीमत के आधार पर खोजती है.

दोष – यहां पर अनेक लंबे रास्ते (paths) हो सकते हैं जिनकी लागत (cost) ≤ C* हो. तब Uniform Cost search को सभी का विश्लेषण करना होता है.

Iterative Deepening Depth-First Search

यह level 1 पर हमेशा depth-first search को करती है, शुरूआत करते हुए फिर से level 2 पर depth-first search करती है, और इसी तरह से तब तक कार्यवाही करती है जब तक कोई solution नहीं मिल जाए.

यह तब तक किसी node का सृजन नहीं करती है जबतक सभी lower nodes, का सृजन न कर लिया जाए. यह एल्गोरिथम तब काम करना बंद करती है जब वह गहराई (depth) d पर समाधान खोज लेती है. गहराई (depth) d पर नोड की संख्या b^d और गहराई d-1 पर यह b^d-1 होगी.

भिन्न एल्गोरिथम की जटिलता की तुलना

भिन्न एल्गोरिथम की भिन्न मानकों के अनुसार तुलना −

Criterion	Breadth First	Depth First	Bidirectional	Uniform Cost	Interactive Deepening
Time	b^d	b^m	b^d/2	b^d	b^d
Space	b^d	b^m	b^d/2	b^d	b^d
Optimality	हाँ	नहीं	हाँ	हाँ	हाँ
Complex	हाँ	नहीं	हाँ	हाँ	हाँ

Informed (Heuristic) Search Strategies

बड़ी समस्याओं को हल करने के लिए जिसमें काफी संख्या में संभावित अवस्थाएं हों, problem-specific knowledge को भी जोड़ने की जरूरत होती है जिससे की search algorithm की दक्षता को बढ़ाया जा सके.

Heuristic Evaluation Functions

यह दो states के बीच optimal path की cost की गणना करता है. Sliding-tiles games के लिए एक heuristic function की गणना यह गिनते हुए की जाती है की प्रत्येक tiles ने कितने moves लिए अपनी goal state से और फिर इन tiles के सभी moves को जोड़ा जाता है.

Pure Heuristic Search

यह nodes का विस्तार करता है उनकी heuristic values के अनुसार. यह दो lists तैयार करता है, एक बंद लिस्ट (closed list) पहले से विस्तरित नोड़ (expanded nodes) के लिए और खुली लिस्ट (open list) बनाए जाने वाली अविस्तारित नोड़ों (unexpanded nodes) के लिए.

प्रत्येक iteration, में वह नोड़ जिसकी minimum heuristic value है उसका विस्तार (expand) करते हैं, उसकी सभी child nodes का सृजन किया जाता है और उन्हें बंद लिस्ट (closed list) में रखते है. तब, heuristic function को child nodes पर प्रयोग करते है और उन्हें खुली लिस्ट (open list) में रखा जाता है उनकी heuristic value के अनुसार. सबसे छोटे रास्तों (shorter paths) को save करते हैं और लम्बे रास्तों का त्याग (dispose) कर देते हैं.

A * Search

यह Best First search का सबसे ज्यादा जाने जाना वाला प्रकार है. यह उन रास्तों को पहले से छोड़ देता है जो पहले से महंगे (expensive), परंतु सबसे ज्यादा भरोसे वाले रास्तों का विस्तार करता है.

f(n) = g(n) + h(n), जहां

g(n), node n तक पहुंचने की लागत (cost).

h(n), node n से लक्ष्य (goal) तक पहुंचने की अनुमानित लागत (estimated cost).

f(n), node n से लक्ष्य (goal) तक पहुंचने वाले रास्ते की अनुमानित कुल लागत (estimated total cost). इसके लिए f(n) को बढ़ाते हुए priority queue का प्रयोग करते हैं.

Greedy Best First Search

यह उन node से शुरूआत करते हैं जिनकी की लक्ष्य (goal) के पास दिखने की संभावना दिखती है. यह nodes का विस्तार f(n) = h(n) पर आधारित होकर priority queue का प्रयोग करती है.

दोष − यह loop में फंस सकती है. जो कि optimal न हो.

Local Search algorithm

यह संभावित समाधान (prospective solution) से शुरूआत करती है और फिर पड़ोस में समाधान (neighboring solution) को खोजती है. यह वापस उचित समाधान (valid solution) पर आ सकते हैं यदि उन्हें किसी भी समय interrupt कर दिया जाए अंत से पहले.

Hill-Climbing Search

यह एक iterative algorithm है यह एक arbitrary solution से शुरूआत करती है और फिर बेहतर solution को पाने की कोशिश करती है solution के एक बार में एक element को बदलते हुए. यदि बदलाव बेहतर solution देता है, तब इस बदलाव को नए solution की तरह से प्रयोग किया जाता है. इस प्रक्रिया को तब तक निरंतर दुहराया जाता है जब तक बेहतर सुधार मिलना बंद न हो जाए.

Function Hill-Climbing (problem), उस state को वापस करता है जो कि local maximum होती है.

inputs: problem, a problem

local variables: current, a node

neighbor, a node

current <-Make_node(Initial-State[problem])

loop

do neighbor <- a highest_valued successor of current

if Value[neighbor] ≤ Value[current] then

return State[current]

current <- neighbor

end

दोष − यह एल्गोरिथम न तो पूर्ण है और न ही यह optimal है.

Local Beam Search

इस एल्गोरिथम में, यह किसी समय में k, states को संज्ञान में लेती है. शुरुआत में यह states आमतौर पर randomly, generate की जाती है. इन k states के successors की गणना objective function की मदद से की जाती है. यदि इनमें से किसी successors से objective function की maximum value मिलती है, तब यह एल्गोरिथम stop हो जाती है. अन्यथा, (initial k states और k number of successors of the states = 2k) states को pool में रखा जाता है. Pool को तब numerically, sort किया जाता है. Highest k states का नई initial states के लिए चयन किया जाता है. इस प्रक्रिया को निरंतर किया जाता है जब तक maximum value को नहीं पा लिया जाए.

Function BeamSearch (problem, k), solution state को वापस करता है.

start with k randomly generated states

loop

generate all successors of all k states

if any of the states = solution, then return the state

else select the k best successors

end

Simulated Annealing

Annealing किसी धातु को गर्म करने और ठंडा करने की प्रक्रिया है जिससे की उसकी आंतरिक संरचना (internal structure) को उसके भौतिक गुणों (physical properties) में बदलाव के लिए बदला जा सके. जब धातु ठंडी होती है, उसकी नई संरचना पकड़ बनाती है, और धातु इन गुणों को ग्रहण कर लेती है. इस प्रक्रिया को करते समय तापमान में निरंतर बदलाव बनाए रखा जाता रहता है.

हम शुरूआत में तापमान ज्यादा रखते हैं और फिर उसे ठंडा होने देते हैं जैसाकी एल्गोरिथम (प्रक्रिया) अनुमति देती है. जब तापमान ज्यादा होता है तब एल्गोरिथम सबसे खराब समाधान को स्वीकार करने की अनुमति देती है.

Start

Initialize k = 0; L = integer number of variables;

From i → j, search the performance difference ∆.

If ∆ <= 0 then accept else if exp(-D/T(k)) > random(0,1) then accept;

Repeat steps 1 and 2 for L(k) steps.

k = k + 1;

Repeat steps 1 through 4 till the criteria is met.

End

Travelling Salesman Problem

इस algorithm का उद्देश्य कम खर्च में यात्रा की योजना बनाना है जो कि एक शहर से शुरू होती है, जिसमें रास्ते में पड़ने वाले सभी शहरों में एक बार जाना होता है और अंत में शुरुआत करने वाले शहर में यात्रा खत्म करनी होती है.