Dykstra's projection algorithm
ડાયક્સ્ટ્રા અલ્ગોરિધમ એ એક એવી પદ્ધતિ છે જે બહિર્મુખ સમૂહોના આંતરછેદમાં એક બિંદુની ગણતરી કરે છે, અને તે વૈકલ્પિક પ્રક્ષેપણ પદ્ધતિનો એક પ્રકાર છે (જેને બહિર્મુખ સમૂહો પર અંદાજ પદ્ધતિ પણ કહેવાય છે). તેના સૌથી સરળ સ્વરૂપમાં, પદ્ધતિ દરેક બહિર્મુખ સમૂહ પર પુનરાવર્તિત રીતે પ્રક્ષેપિત કરીને બે બહિર્મુખ સમૂહના આંતરછેદમાં એક બિંદુ શોધે છે; તે વૈકલ્પિક પ્રક્ષેપણ પદ્ધતિથી અલગ છે જેમાં મધ્યવર્તી પગલાં છે. અલ્ગોરિધમનું સમાંતર સંસ્કરણ ગાફકે અને માથરે વિકસાવ્યું હતું. આ પદ્ધતિનું નામ રિચાર્ડ એલ. ડિક્સ્ટ્રા પરથી રાખવામાં આવ્યું છે, જેમણે 1980ના દાયકામાં તેનો પ્રસ્તાવ મૂક્યો હતો. ડાઇકસ્ટ્રાના અલ્ગોરિધમ અને પ્રમાણભૂત વૈકલ્પિક પ્રક્ષેપણ પદ્ધતિ વચ્ચેનો મુખ્ય તફાવત ત્યારે થાય છે જ્યારે બે સમૂહોના આંતરછેદમાં એક કરતાં વધુ બિંદુ હોય. આ કિસ્સામાં, વૈકલ્પિક પ્રક્ષેપણ પદ્ધતિ આ આંતરછેદમાં અમુક મનસ્વી બિંદુ આપે છે, જ્યારે ડિક્સ્ટ્રાનું અલ્ગોરિધમ એક ચોક્કસ બિંદુ આપે છેઃ આંતરછેદ પર r નું પ્રક્ષેપણ, જ્યાં r એ અલ્ગોરિધમમાં વપરાતો પ્રારંભિક બિંદુ છે, એલ્ગોરિધમ ડિક્સ્ટ્રાનું અલ્ગોરિધમ દરેક માટે માત્ર એવું જ શોધે છે કેઃ જ્યાં બહિર્મુખ સમૂહો છે. આ સમસ્યા સેટ પરના પ્રક્ષેપણને શોધવાની સમકક્ષ છે, જેને આપણે સૂચવીએ છીએ. ડાઇકસ્ટ્રાના અલ્ગોરિધમનો ઉપયોગ કરવા માટે, સેટ પર અને અલગથી પ્રોજેક્ટ કેવી રીતે કરવો તે જાણવું આવશ્યક છે. પ્રથમ, મૂળભૂત વૈકલ્પિક પ્રક્ષેપણ (ઉર્ફ પી. ઓ. સી. એસ.) પદ્ધતિને ધ્યાનમાં લો (પ્રથમ અભ્યાસ, જ્યારે સમૂહો રેખીય પેટા જગ્યાઓ હતા ત્યારે, જ્હોન વોન ન્યુમેન દ્વારા), જે પ્રારંભ કરે છે અને પછી ક્રમ પેદા કરે છે. ડાઇકસ્ટ્રાનું અલ્ગોરિધમ સમાન સ્વરૂપનું છે, પરંતુ વધારાના સહાયક ચલોનો ઉપયોગ કરે છે. સાથે પ્રારંભ કરો અને પછી અપડેટ કરો પછી ક્રમ મૂળ સમસ્યાના ઉકેલમાં એકરૂપ થાય છે. અભિસરણ પરિણામો અને સાહિત્ય પર આધુનિક પરિપ્રેક્ષ્ય માટે, સંદર્ભો સાઇટેશન કન્વેક્સ ભૂમિતિ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ જુઓ.