एल्गोरिदम अधिकतम न्यूनतम दूरी

के साथ वर्ग में बिंदु डालने पर मैं इस पर अटक गया हूं: एक वर्ग है। एन वर्ग को इस वर्ग में रखें ताकि न्यूनतम दूरी (औसत दूरी आवश्यक न हो) उच्चतम संभव है।एल्गोरिदम अधिकतम न्यूनतम दूरी

मैं एक एल्गोरिदम खोज रहा हूं जो उनकी गिनती के सभी बिंदुओं के निर्देशांक उत्पन्न करने में सक्षम होगा। 5;;

एन = 4 के लिए उदाहरण परिणाम 6:

Example results for n=4;5;6 http://i40.tinypic.com/ohrb44.png

कृपया इस तरह के संयोजन का एक बहुत कोशिश कर रहा है और फिर सही एक और इसी तरह के विचारों nitpicking के रूप में कंप्यूटिंग शक्ति आधारित सामग्री का उल्लेख नहीं है ।

स्रोत

2010-04-27 Mikulas Dite

इस "वर्ग में मंडलियां" के रूप में ही है? http://en.wikipedia.org/wiki/Packing_problem#Circles_in_square – zaf

ओपी को घोषणा करें कि यह होमवर्क है या नहीं, कृपया। –

@zaf मुझे नहीं लगता कि यह वर्गों में मंडलियों से संबंधित होगा, वहां सर्किल स्पर्श होते हैं, यहां अंक पीछे हटते हैं, भले ही आप अंक को सर्किल के केंद्रों के केंद्र मानते हैं, सर्किल ओवरलैप हो जाएंगे। :) –

यह circles in square पैकिंग समस्या है।

यह Unsolved problems in geometry में समस्या डी 1 के रूप में चर्चा की है Hallard टी क्रॉफ्ट, केनेथ जे फल्कोनर, और रिचर्ड लालकृष्ण लड़का, पेज द्वारा, 108.

alt text http://i41.tinypic.com/2s0z8gh.png

पेज 109 और 110 शामिल एक संदर्भ की सूची।

स्रोत

2010-04-27 18:09:20 zaf

वास्तव में अच्छा है! अब, निर्देशांक कैसे उत्पन्न करें। –

क्या आप अगले पृष्ठ को संदर्भों की सूची के साथ चाहते हैं? – zaf

@zaf, क्या आप हमें उस पुस्तक का शीर्षक और लेखक दे सकते हैं, यदि इस विषय पर अधिक जानकारी है? (या संभवतः अन्य पहेली?) –

आप N body simulation कर सकते हैं जहां अंक एक दूसरे को पीछे हटते हैं, शायद 1/आर^2 बल के साथ। बिंदुओं का आंदोलन स्पष्ट रूप से वर्ग द्वारा बाधित होगा। लगभग सभी बिंदुओं के साथ वर्ग के केंद्र में शुरू करें।

स्रोत

2010-04-27 17:54:51

हां, आप "कर सकते हैं"। लेकिन क्या यह कोई अच्छा होगा? (आप क्या गारंटी दे सकते हैं? क्या आप कह सकते हैं कि यह इष्टतम के एक निश्चित कारक के भीतर है, कहें?) (प्रश्न में ओपी की टिप्पणी देखें: "कृपया कंप्यूटिंग-पावर आधारित सामानों का उल्लेख न करें जैसे कि बहुत सारे संयोजन की कोशिश करना और फिर सही और समान विचारों को नाइट करना।") – ShreevatsaR

मैं एक एन बॉडी सिमुलेशन जल्दी से सहायक हो सकता हूं अनुमान, हालांकि। –

"अधिकतम न्यूनतम दूरी" 1/आर^अनंत क्षमता के बराबर है। अगर कोई इस तरह के अनुमानों को बनाना चाहता था - जो मुझे एक अच्छी ह्युरिस्टिक पद्धति के रूप में मारता है - किसी को 1/आर^2 से शुरू करना चाहिए, लेकिन जब कोई समाधान के करीब होता है तो उच्च शक्तियों पर ले जाता है। –

मिकुलस, मुझे संभवतया अस्थायी, या वर्तमान में सबसे अच्छे ज्ञात समाधानों के छवि उदाहरणों से भरा एक पृष्ठ मिला। यह मेरा नहीं है, इसलिए इसे अपने जोखिम से उपयोग करें।

देखें

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/numerical.php?table=csq-mina&title=Packing%20of%20unitary-radius%20circles%20in%20a%20square

स्रोत:

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/

स्रोत

2010-04-27 18:20:38

+1। मुझे संदेह है कि ये वास्तव में इष्टतम (संख्यात्मक रूप से) हैं, दो कारणों से: वे अपने एल्गोरिदम का वर्णन करने में "हल" शब्द का उपयोग करते हैं, और अलग-अलग एन में परीक्षणों की अलग-अलग संख्या होती है, जो सुझाव देते हैं कि संभवतः वे प्रारंभिकता तक पहुंच गए हैं। (यह सुनिश्चित करने के लिए, स्रोत को देखना बेहतर होगा और देखें कि क्या वे केवल तभी रुकते हैं जब द्वंद्व अंतर 0 पर जाता है, या क्या।) – ShreevatsaR

@ShreevatsaR: इष्टतमता साबित करने का एक और विषय है। ;] काफी अच्छा है, कभी-कभी पर्याप्त है। –

हां, मुझे पता है, मैं बस इतना कह रहा हूं कि न केवल ये पर्याप्त हैं, वे वास्तव में भी अनुकूल हैं। – ShreevatsaR

एल्गोरिदम अधिकतम न्यूनतम दूरी

उत्तर

संबंधित मुद्दे