Stacker crane problem
સંયુક્ત ઓપ્ટિમાઇઝેશનમાં, સ્ટેકર ક્રેનની સમસ્યા એ ઓપ્ટિમાઇઝેશનની સમસ્યા છે જે મુસાફરી કરતા વેચાણકર્તાની સમસ્યા સાથે નજીકથી સંબંધિત છે. તેના ઇનપુટમાં મેટ્રિક જગ્યામાં પોઇન્ટ્સની ક્રમબદ્ધ જોડીનો સંગ્રહ હોય છે, અને ધ્યેય આ બિંદુઓને ઓછામાં ઓછી કુલ લંબાઈના ચક્રમાં જોડવાનો છે જેમાં એકબીજા સાથે સતત લક્ષી તમામ જોડીનો સમાવેશ થાય છે. તે સ્ટેકર ક્રેન, બાંધકામ ક્રેન અથવા (ડ્રેયેજમાં) ટ્રક દ્વારા, આ ડિલિવરીના સમય પર અવરોધો વિના, સરળ સ્વરૂપમાં, વ્યક્તિગત લોડના માલસામાનની ઉપાડ અને ડિલિવરીના સમયપત્રકની સમસ્યાઓનું મોડેલ બનાવે છે. તે ઇનપુટ જોડીઓનું મોડેલિંગ કરતી નિર્દેશિત ધાર અને તેમના અંતરનું મોડેલિંગ કરતી દિશાહીન ધાર સાથે મિશ્ર આલેખની દ્રષ્ટિએ સમકક્ષ રચના સાથે રજૂ કરવામાં આવી હતી. ફ્રેડરિકસન એટ અલ. તેની રચનાનો શ્રેય ડેનિયલ જે. રોસેનક્રાન્ઝના વ્યક્તિગત સંદેશાવ્યવહારને આપવામાં આવે છે. સ્ટેકર ક્રેન સમસ્યાને મેટ્રિક જગ્યાઓમાં મુસાફરી કરતા વેચાણકર્તાની સમસ્યાના સામાન્યીકરણ તરીકે જોઈ શકાય છેઃ મુસાફરી કરતા વેચાણકર્તાની સમસ્યાના કોઈપણ ઉદાહરણને સ્ટેકર ક્રેન સમસ્યાના ઉદાહરણમાં રૂપાંતરિત કરી શકાય છે, જેમાં મુસાફરી કરતા વેચાણકર્તાના ઉદાહરણમાં દરેક બિંદુ માટે એક જોડી હોય છે. બીજી દિશામાં, સ્ટેકર ક્રેનની સમસ્યાને અસમપ્રમાણ મુસાફરી કરનાર સેલ્સપર્સન સમસ્યાના એક વિશેષ કેસ તરીકે જોઈ શકાય છે, જ્યાં અસમપ્રમાણ મુસાફરી કરનાર સેલ્સપર્સન સમસ્યાના મુદ્દાઓ સ્ટેકર ક્રેન ઉદાહરણની જોડી છે અને એક જોડીથી બીજી જોડીનું અંતર પ્રથમ જોડીના ડિલિવરી પોઇન્ટથી, તેના પિકઅપ પોઇન્ટ દ્વારા, બીજી જોડીના ડિલિવરી પોઇન્ટ સુધીના અંતર તરીકે લેવામાં આવે છે. કારણ કે તે મુસાફરી કરતી વેચાણકર્તાની સમસ્યાને સામાન્ય બનાવે છે, તે સમાન કોમ્પ્યુટેશનલ જટિલતાને વારસામાં મેળવે છેઃ તે એન. પી.-હાર્ડ છે, અને ઓછામાં ઓછું અંદાજ લગાવવું મુશ્કેલ છે. મુસાફરી કરતી વેચાણકર્તાની સમસ્યા માટે ક્રિસ્ટોફાઇડ્સ અલ્ગોરિધમ પર આધારિત અંદાજિત અલ્ગોરિધમ 9/5 ના અંદાજિત ગુણોત્તરમાં સ્ટેકર ક્રેન સમસ્યાના ઉકેલનો અંદાજ લગાવી શકે છે. ઉપયોગમાં લેવાતા થ્રેડની કુલ માત્રાને ઘટાડવા માટે ભરતકામ પેટર્નની પાછળની બાજુની રચના કરવાની સમસ્યા સ્ટેકર ક્રેનની સમસ્યા સાથે નજીકથી સંબંધિત છે, પરંતુ તે તેના દરેક જોડીઓના બિંદુઓને (પેટર્નની આગળની બાજુએ દૃશ્યમાન ટાંકાઓના છેડા) બંને દિશામાં પસાર કરવાની મંજૂરી આપે છે, તેના બદલે ટ્રાવર્સલને સુસંગત દિશામાં તમામ જોડીઓમાંથી પસાર થવાની જરૂર પડે છે. મુસાફરી કરતી વેચાણકર્તાની સમસ્યામાંથી સમાન પરિવર્તન દ્વારા તે એન. પી.-હાર્ડ છે, અને 2 ના અંદાજિત ગુણોત્તરમાં અંદાજિત કરી શકાય છે. સ્ટેકર ક્રેન સમસ્યાની અન્ય વિવિધતા, જેને ડાયલ-એ-રાઇડ સમસ્યા કહેવામાં આવે છે, તે વાહનને તેના માર્ગ પર કોઈપણ સમયે અમુક સંખ્યામાં ભારને પકડી રાખવાની મંજૂરી આપતી વખતે પિકઅપ્સ અને ડિલિવરીનો સંગ્રહ કરવા માટે ઓછામાં ઓછો માર્ગ પૂછે છે. સંદર્ભો મુસાફરી કરતી વેચાણકર્તાની સમસ્યા