गहराई की पहली खोज जल्दी समाप्त हो रही है

मैं जावा में एक प्रोग्राम बना रहा हूं जो हेरिस्टिक का उपयोग किए बिना n-puzzle हल करता है, बस राज्य की अंतरिक्ष की पहली और चौड़ाई-पहली खोजों के साथ। मैं गहराई-पहली खोज के कार्यान्वयन के साथ थोड़ा सा संघर्ष कर रहा हूं। कभी-कभी यह दिए गए पहेली को हल करेगा, लेकिन दूसरी बार ऐसा लगता है कि यह जल्दी छोड़ देता है।

यहां मेरा डीएफएस वर्ग है। DepthFirstSearch() को एक पहेली बोर्ड पारित किया जाता है, जिसे शुरू में हल किए गए बोर्ड को घुमाकर उत्पन्न किया जाता है (यह सुनिश्चित करने के लिए कि बोर्ड एक हल करने योग्य राज्य में है)।

public class DepthFirst {
static HashSet usedStates = new HashSet(); 

public static void DepthFirstSearch(PuzzleBoard currentBoard)
{   
   //If the current state is the goal, stop.
    if (PuzzleSolver.isGoal(currentBoard)) {    
        System.out.println("Solved!");
        System.exit(0); 
    } 

   //If we haven't encountered the state before,
   //attempt to find a solution from that point.
    if (!usedStates.contains(currentBoard)) {                       
        usedStates.add(currentBoard);           
        PuzzleSolver.print(currentBoard);

        if (PuzzleSolver.blankCoordinates(currentBoard)[1] != 0) {
            System.out.println("Moving left");
            DepthFirstSearch(PuzzleSolver.moveLeft(currentBoard));
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[0] != PuzzleSolver.n-1) {
            System.out.println("Moving down");
            DepthFirstSearch(PuzzleSolver.moveDown(currentBoard)); 
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[1] != PuzzleSolver.n-1) {
            System.out.println("Moving right");
            DepthFirstSearch(PuzzleSolver.moveRight(currentBoard)); 
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[0] != 0) {
            System.out.println("Moving up");
            DepthFirstSearch(PuzzleSolver.moveUp(currentBoard));    
        }

        return; 
    } else {
       //Move up a level in the recursive calls
        return; 
    }
}   
}

मैं जोर दे सकता हूं कि मेरा moveUp (), moveLeft (), moveRight (), और moveDown() विधियों और तर्क सही ढंग से काम करते हैं, इसलिए समस्या कहीं और झूठ बोलनी चाहिए।

हैशकोड के साथ मेरी पहेलीबार्ड ऑब्जेक्ट क्लास यहां है और विधियों के बराबर है:

static class PuzzleBoard {
    short[][] state;        
    /**
     * Default constructor for a board of size n
     * @param n Size of the board 
     */
    public PuzzleBoard(short n) {
        state = PuzzleSolver.getGoalState(n);
    }
    public PuzzleBoard(short n, short[][] initialState) {
        state = initialState; 
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Arrays.deepHashCode(state);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        PuzzleBoard other = (PuzzleBoard) obj;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (state[i][j] != other.state[i][j])
                    return false; 
            }
        }
        return true;
    }   
}

जैसा कि पहले बताया गया था, कभी-कभी खोज ठीक से काम करती है और समाधान के लिए पथ पाती है, लेकिन दूसरी बार यह समाधान ढूंढने से पहले और स्मृति से बाहर होने से पहले बंद हो जाती है।

खोज के बंद होने से पहले कुछ चाल शुरू करने से आउटपुट का एक स्निपेट यहां दिया गया है।

...
Moving down
6 1 3 
5 8 2 
0 7 4 
Moving right
6 1 3 
5 8 2 
7 0 4 
Moving left
Moving right
Moving up
6 1 3 
5 0 2 
7 8 4 
Moving left
Moving down
Moving right
Moving up
Moving up
Moving right
Moving down
Moving up
Moving down
Moving up
Moving down
Moving up
Moving down
Moving up
Moving down
...

मैंने इसे ब्रेवटी के लिए जल्दी से छोटा कर दिया, लेकिन यह कई बार बार-बार ऊपर और नीचे बढ़ता है और कभी भी हल राज्य को हिट नहीं करता है।

क्या कोई भी गलत क्या कर रहा है उस पर प्रकाश डाल सकता है?

Edit: Here is MoveUp(). The rest of the move methods are implemented in the same way.

/**
 * Move the blank space up
 * @return The new state of the board after the move
 */
static PuzzleBoard moveUp(PuzzleBoard currentState) {
    short[][] newState = currentState.state; 
        short col = blankCoordinates(currentState)[0]; 
        short row = blankCoordinates(currentState)[1]; 
        short targetCol = col; 
        short targetRow = row; 
        newState[targetCol][targetRow] = currentState.state[col - 1][row];
        newState[targetCol - 1][targetRow] = 0; 

        return new PuzzleBoard(n, newState); 
    }
2
जिस तरह से मैं हल करने के लिए अपनी पहेली उत्पन्न कर रहा हूं वह एक हल राज्य से शुरू हो रहा है और फिर वहां से एक यादृच्छिक संख्या की वैध चाल बना रहा है। तो हाँ, मैं एक हल करने योग्य राज्य से शुरू कर रहा हूँ।
जोड़ा लेखक Michelle, स्रोत
@ विक्रमबैट मैंने अधिक संदर्भ के लिए PuzzleSolver क्लास के एक कदम() फ़ंक्शंस को जोड़ा।
जोड़ा लेखक Michelle, स्रोत
क्या आप सुनिश्चित हैं कि यह एक हल करने योग्य पहेली उत्पन्न करता है?
जोड़ा लेखक Adam Arold, स्रोत
@ MrSmith42 नहीं ऊपर और नीचे चलना वैध चाल हैं क्योंकि आप नहीं जानते कि पिछले राज्य से कौन सा पिछला राज्य आया है और मुझे लगता है कि ओपी ने किया है जो हैशसेट में एकमात्र तरीका है।
जोड़ा लेखक Vikram Bhat, स्रोत
@ मिशेल PuzzleSolver.moveLeft (वर्तमान) और ऐसे अन्य कथन हैं जो नए बोर्ड ऑब्जेक्ट उत्पन्न करते हैं या बस पुराने को बदलते हैं? इसे एक नई वस्तु को आदर्श रूप से वापस करना होगा अन्यथा इस कार्यान्वयन में डीएफएस सही तरीके से काम नहीं करेगा।
जोड़ा लेखक Vikram Bhat, स्रोत
@ मिशेल कृपया मेरे उत्तर में जो मैंने उल्लेख किया है उसे आजमाएं क्योंकि आपका तर्क तर्क है कि हैशकोड और बराबर के साथ संदेह है। जैसा कि मैंने सुझाव दिया है, आपको उनकी आवश्यकता नहीं है।
जोड़ा लेखक Vikram Bhat, स्रोत
PuzzleSolver कोड कहां है?
जोड़ा लेखक MadConan, स्रोत
चाल अनुक्रम <कोड> ऊपर बढ़ना, नीचे जाना अमान्य होना चाहिए, क्योंकि यह पिछले राज्य की ओर जाता है। आपको बराबर विधि की जांच करनी चाहिए यदि यह वास्तव में अपेक्षित काम करता है (और आपका हैशकोड() विधि भी)। उनके लिए कुछ परीक्षण लिखें ...
जोड़ा लेखक MrSmith42, स्रोत
@ विक्रमबैट वह उसके लिए बराबर() में जांचती है: अगर (यह == obj) {वापसी सही;}। साथ ही, उसने उल्लेख किया कि कभी-कभी उसके डीएफएस को समाधान सही तरीके से मिल जाता है, इसलिए मुझे लगता है कि यह समस्या नहीं है।
जोड़ा लेखक ile, स्रोत
सिर्फ एक अनुमान है क्योंकि मैं यह निर्धारित करने के लिए कि कौन सी दिशा को स्थानांतरित करने के लिए if() कथन को समझ में नहीं आता है; लेकिन मुझे लगता है कि यह एक कोने में "अटक" हो रही है। चूंकि आप if() और कोई अन्य अगर() का उपयोग कर रहे हैं, तो यह आगे बढ़ने की कोशिश कर रहा है और फिर तुरंत वापस ले जाया जा सकता है। फिर फिर से स्थानांतरित करने की कोशिश करता है?
जोड़ा लेखक DoubleDouble, स्रोत

2 उत्तर

हैशसेट में ऑब्जेक्ट को स्टोर न करने का प्रयास करने के लिए पिछले सबसे अच्छी चीज में हैशसेट के साथ मुझे कई समस्याएं हैं लेकिन स्ट्रिंग में अपनी ऑब्जेक्ट को एन्कोड करने का प्रयास करें।

ऐसा करने का एक तरीका यहां है: -

StringBuffer encode(PuzzleBoard b) {

   StringBuffer buff = new StringBuffer();

    for(int i=0;i

Note:- Here no need to write your own hashcode function & also no need to implement equals function as java has done it for you in StringBuffer.

0
जोड़ा

मुझे आपके कार्यान्वयन में समस्याएं मिलीं: -

निम्नलिखित कोड में: -

static PuzzleBoard moveUp(PuzzleBoard currentState) {
    short[][] newState = currentState.state; 
        short col = blankCoordinates(currentState)[0]; 
        short row = blankCoordinates(currentState)[1]; 
        short targetCol = col; 
        short targetRow = row; 
        newState[targetCol][targetRow] = currentState.state[col - 1][row];
        newState[targetCol - 1][targetRow] = 0; 

        return new PuzzleBoard(n, newState); 
    }

यहां आप currentState.state से newState के रूप में एक ही सरणी के संदर्भ का उपयोग कर रहे हैं, इसलिए जब आप नए स्टेटस में परिवर्तन करते हैं तो आपके वर्तमानस्टेट.स्टेट भी बदलेगा जो कॉल रिटर्न के दौरान डीएफएस को प्रभावित करेगा। इसे रोकने के लिए आपको एक नई सरणी शुरू करनी चाहिए। क्या किया जाना है: -

static PuzzleBoard moveUp(PuzzleBoard currentState) {
    short[][] newState = new short[n][n]; 
        short col = blankCoordinates(currentState)[0]; 
        short row = blankCoordinates(currentState)[1]; 
        short targetCol = col; 
        short targetRow = row; 
        for(int i=0;i

सभी चाल के लिए यह परिवर्तन, स्थानांतरित ....

इसके अलावा मुझे नहीं लगता कि आपका हैशसेट सही तरीके से काम कर रहा है क्योंकि अगर ऐसा होता तो आपको हमेशा अपने नए राज्य को हैशसेट में मिल जाएगा और आपका प्रोग्राम रुक जाएगा। जैसा कि आप समान संदर्भ के साथ राज्य सरणी की तुलना करते हैं, इसलिए हमेशा सत्य हो जाएगा। कृपया हैश के रूप में मेरे एन्कोड फ़ंक्शन का प्रयास करें और उपयोग करें।

0
जोड़ा