मैं (घ) आयाम का एक ग्रिड, सभी आयामों डेल्टा का उपयोग कर = 0.25, अंक की एक ग्रिड सर्च कर रहे हैं प्रत्येक बिंदु पर जाकर एक बार केवल
इस ग्रिड का एक उदाहरण यह आंकड़ा है विभाजित हैं (यहाँ d 2 है, और प्रत्येक आयाम सामान्यीकृत 0-1 है):
प्रत्येक चौराहे को दर्शाता है 1 अंक, उदाहरण के लिए, बीच में बिंदु के रूप में प्रस्तुत किया जाता है:
double[] A={0.5, 0.5};
मेरा प्रश्न है: मैं इनपुट ग्रिड ए और उसके पड़ोसियों से शुरू होने से इस ग्रिड को खोजना चाहता हूं। फिर ऐसा करना जारी रखें। एक शर्त के साथ: प्रत्येक बिंदु केवल एक बार दौरा किया जाता है।
अधिक स्पष्ट करने के लिए, इस उदाहरण पर विचार करें: प्रारंभिक बिंदु है:
double[] A={0.5, 0.5};
तो, एक चेक किया गया है पहले, तो अपने पड़ोसियों को उत्पन्न किया और (कतार एक के आधार पर क्रमबद्ध किया जाता है एक पंक्ति में डाला जाता है समारोह एफ)।
यहाँ बिंदु एक अंधेरे चक्र है। इसके पड़ोसियों हरे रंग की सर्कल हैं:
{0.25, 0.25}
{0.25, 0.5}
{0.25, 0.75}
..
..
..
{0.75, 0.75}
अब, कतार खाली होने तक एल्गोरिदम लूप हो जाता है। लूप में, शीर्ष बिंदु हटा दिया जाता है (पॉप()), फिर चेक किया गया, उसके बाद पड़ोसियों कतार में जोड़े गए हैं।
उदाहरण के लिए, पहली पाश में, नीले वृत्त कतार में शीर्ष बिंदु हुआ। इसे कतार से हटा दिया गया है, फिर चेक किया गया है, उसके पड़ोसियों (लाल मंडल) उत्पन्न होते हैं और कतार में जोड़े जाते हैं।
समस्या यह है कि, मेरा कोड जो पड़ोसियों के अंक उत्पन्न करता है, यह नहीं जानता कि पिछले बिंदु का दौरा किया गया है या नहीं।
और मैं पहले देखे गए बिंदुओं की एक सूची नहीं रख सकता, और प्रत्येक बार जब कोई नया बिंदु उत्पन्न होता है (उच्च आयाम और उच्च रिज़ॉल्यूशन उदाहरण के साथ, डी = 8 और डेल्टा = 0.03125, यह हमेशा के लिए ले जाएगा!)
इस खोज एल्गोरिथ्म है:
public void search(int d, double delta, double[] inpoint)
{
Queue queue = new Queue();
queue.push(inpoint);
while(!queue.isEmpty())
{
// remove top point from Queue
double[] a = queue.pop();
// Check point a and do some calculations
// ;;;;;;;;;;;;;;;;
// Generate neighbours of current point:
ArrayList<double[]> neighbors = new ArrayList<double[]>();
nextMoves(a, new double[d], delta, d, neighbors);
// For each point in neighbors, push to Queue:
for(int i=0 ; i < neighbors.size(), i++)
queue.push(neighbors.get(i));
}
}
और यह पड़ोसियों पैदा करने के लिए एल्गोरिथ्म है, यह पुनरावर्ती एल्गोरिदम है।
public static void nextMoves(double[] inatt, double[] outatt, double delta, int d, ArrayList<double[]> neighbors)
{
if(d == inatt.length)
{
if(!outOfBound(outatt,d))
{
moves.add(outatt);
}
}
else
{
// first case: add delta:
outatt[d] = inatt[d]+delta;
nextMoves(inatt, outatt, delta, d+1, moves);
// second case: subtract delta:
outatt[d] = inatt[d]-delta;
nextMoves(inatt, outatt, delta, d+1, moves);
// third case: no change:
outatt[d] = inatt[d];
nextMoves(inatt, outatt, delta, d+1, moves);
}
}
जैसा कि मैंने पहले उल्लेख किया था, पहले गए गए बिंदुओं की एक सूची रखने का एक संभावित समाधान नहीं है। यदि मैं ऐसा करता हूं, तो जब उच्च आयाम और उच्च रिज़ॉल्यूशन होता है तो सूची बहुत बड़ी हो जाती है। और प्रत्येक बार एक बिंदु बनने पर इस सूची को रैखिक रूप से खोजना होगा!
शायद मुझे इस सूची को स्थानिक सूचकांक में व्यवस्थित करना चाहिए? मुझे नहीं पता ... मैं आपके इनपुट की सराहना करता हूं।
क्या आप हमें बता सकते हैं कि आप प्रत्येक बिंदु पर कौन सा ऑपरेशन करना चाहते हैं? मुझे संदेह है कि कोई असली दुनिया की समस्या है जहां आप वहां कुछ भी किए बिना प्रत्येक बिंदु पर "यात्रा" करने की योजना बना रहे हैं। –
'और इस सूची को प्रत्येक बार एक बिंदु बनाया गया है, तो रैखिक रूप से खोजना होगा' ... नहीं, आपको डुप्लिकेट पॉइंट की जांच करने के लिए पूरी सूची को खोजना नहीं होगा यदि आप बस बिंदु का उपयोग करके सरणी को _access_ कर सकते हैं सवाल। –
क्या आपकी कतार कक्षा फीफो (पहली बार में पहली बार) है? और क्या यह जांचने की अनुमति देता है कि क्या कतार में तत्व पहले से मौजूद है या नहीं? –