एरलांग में जादू वर्गों को उत्पन्न करते समय बहुत अधिक स्मृति खपत - विश्वविद्यालय के लिए अनुकूलन

Question

के लिए सहायता की आवश्यकता है मुझे एक एल्गोरिदम लागू करना है जो किसी भी किनारे की लंबाई और एक विशिष्ट राशि के लिए सभी possibile जादू वर्ग बनाता है। एन = 3 के लिए एल्गोरिदम अपेक्षित के रूप में काम कर रहा है। लेकिन जब मैं कुछ समय के बाद n = 4 के लिए सभी जादू वर्ग उत्पन्न करता हूं तो मैं स्मृति से बाहर निकलता हूं। कार्य समस्या में इस समस्या का पहले ही उल्लेख किया गया था। मैंने पहले ही कोड को अनुकूलित करने का प्रयास किया है, लेकिन यह अभी भी काम नहीं कर रहा है जैसा कि इसे करना चाहिए। तो मुझे उम्मीद है कि कोई मुझे कुछ सलाह दे सकता है।

मेरा मूल विचार यह है: सबसे पहले मैं सभी संभावित पंक्तियां उत्पन्न करता हूं जिन्हें मैं दिए गए नंबरों के साथ उपयोग कर सकता हूं और फिर मैं इन तरीकों को गठबंधन करने की कोशिश कर रहा हूं कि एक जादू वर्ग के प्रतिबंध पूर्ण हो गए हैं। यह बैकट्रैकिंग के माध्यम से होता है। मुझे लगता है कि समस्या makeRows है जो सभी पंक्तियों को संग्रहीत करने के दौरान बहुत अधिक स्मृति का उपभोग करती है।

यदि आपको कोड के कुछ और स्पष्टीकरण की आवश्यकता है तो मैं दे सकता हूं!

magicSquare(N, Value) -> 
    Squares = buildSquare(N, makeRows(N, N*N, Value, N)), 
    io:fwrite("Squares ready"), io:fwrite("~n"), 
    Result = lists:filter(fun(X) -> testsquare(X, N, Value) end, Squares), 
    io:write(length(Result)), 
    Result. 

buildSquare(0, _) -> [[]]; 
buildSquare(Rows, AvailableRows) -> 
    [ [X|L] || L <- buildSquare(Rows-1, AvailableRows), X <- AvailableRows, onlyUniqueNumbers(lists:flatten([X|L]))]. 

onlyUniqueNumbers(List) -> erlang:length(List) == sets:size(sets:from_list(List)). 

%produces all possible rows with a dimension of Fields and the Numbers from 1 to Numbers and the right sum for each row 
makeRows(0,_,_,_) -> [[]]; 
makeRows(Fields, Numbers, Value, TargetLength) -> 
    [ [X|L] || X <- makeRows(Fields-1, Numbers, Value, TargetLength), L <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)]. 

checkRow(Row, Length, Value) when length(Row) < Length -> true; 
checkRow(Row, Length, Value) -> 
    Sum = lists:sum(Row), 
    if Sum == Value -> true; 
    true -> false 
    end. 

testsquare(Square, N, Value) -> checkAllDiagonal(Square, Value) andalso checkAllHorizontal(Square, Value) andalso checkAllVertical(Square, N, Value). 

checkAllHorizontal([H|T], Value) -> 
    case checkHorizontal(H, Value, 0) of 
     true -> checkHorizontal(lists:nth(1, T), Value, 0); 
     false -> false 
    end; 
checkAllHorizontal([], Value) -> true. 

checkHorizontal([H|T], Value, Summe) -> checkHorizontal(T, Value, Summe + H); 
checkHorizontal([], Value, Summe) when Summe == Value -> true; 
checkHorizontal([], Value, Summe) -> false. 

checkAllVertical(Square, N, Value) -> checkAllVertical(Square, N, Value, 1). 
checkAllVertical(Square, N, Value, Column) -> 
    if 
     Column > N -> true; 
     true -> 
      case checkVertical(Square, Value, 0, Column) of 
       true -> checkAllVertical(Square, N, Value, Column + 1); 
       false -> false 
      end 
    end. 

checkVertical([], Value, Summe, Column) when Summe == Value -> true; 
checkVertical([], Value, Summe, Column) -> false; 
checkVertical([H|T], Value, Summe, Column) -> checkVertical(T, Value, Summe + lists:nth(Column, H), Column). 

checkAllDiagonal(Square, Value) -> 
    case checkDiagonal(Square, Value, 0, 1,1) of 
     true -> case checkDiagonal(Square, Value, 0, length(lists:nth(1, Square)),-1) of 
          true -> true; 
          false -> false 
         end; 
     false -> false 
    end. 

checkDiagonal([H|T], Value, Summe, Position, Richtung) -> checkDiagonal(T, Value, Summe + lists:nth(Position, H), Position + Richtung, Richtung); 
checkDiagonal([], Value, Summe, Position, Richtung) when Summe == Value -> true; 
checkDiagonal([], Value, Summe, Position, Richtung) -> false. 

ठीक है मैंने गणना प्रक्रिया में पहले पंक्तियों और वर्गों के लिए चेक जोड़ने की कोशिश की है। संशोधित फ़ंक्शन यहां दिए गए हैं।

buildSquare(0, _, _, _) -> [[]]; 
buildSquare(Rows, AvailableRows, RowLength, Value) -> 
    [ [X|L] || L <- buildSquare(Rows-1, AvailableRows, RowLength, Value), X <- AvailableRows, validateSquare([X|L], RowLength, Value)]. 

checkOnlyUniqueNumbers(List) -> erlang:length(lists:flatten(List)) == sets:size(sets:from_list(lists:flatten(List))). 

validateSquare(List, RowLength, Value) when length(List) == RowLength -> testsquare(List, RowLength, Value) andalso checkOnlyUniqueNumbers(List); 
validateSquare(List, _,_) -> checkOnlyUniqueNumbers(List). 

%produces all possible rows with a dimension of Fields and the Numbers from 1 to Numbers 
makeRows(0,_,_,_) -> [[]]; 
makeRows(Fields, Numbers, Value, TargetLength) -> 
    [ [X|L] || L <- makeRows(Fields-1, Numbers, Value, TargetLength), X <- lists:seq(1,Numbers), checkRow([X|L], TargetLength, Value)]. 

%Checks if the sum of the row is Value when the row has the needed length Length 
checkRow(Row, Length, _) when length(Row) < Length -> checkOnlyUniqueNumbers(Row); 
checkRow(Row, _, Value) -> 
    Sum = lists:sum(Row), 
    Sum == Value andalso checkOnlyUniqueNumbers(Row). 

Answer 1

खैर, erlang चार पंक्तियों के सभी +३१२१३४८६०८ संभावित संयोजनों की सूची बनाने के लिए

magicSquare(N, Value) -> 
    Squares = buildSquare(N, makeRows(N, N*N, Value, N)), 

की कोशिश करता आलसी नहीं है, इसलिए, प्रत्येक 34 को संक्षेप, 1 से 16 करने के लिए सभी नंबरों का उपयोग कर (समावेशी), जब तर्क 4 और 34 के साथ बुलाया जाता है।

भले ही प्रत्येक वर्ग में केवल 16 बाइट्स (प्रत्येक सेल के लिए एक) लिया गया हो, जिसके लिए 48 जीबी मेमोरी की आवश्यकता होगी, सूची ओवरहेड की गणना नहीं की जाएगी।

आपका एल्गोरिदम धीरे-धीरे - आलसी भाषा में काम करेगा - हालांकि। लेकिन एक गैर आलसी भाषा में, आप को की आवश्यकता है ताकि पहले और पहले, या पूरी तरह से अलग एल्गोरिदम चुनें।

आप जांच सकते हैं कि लंबवत और विकर्णों को पहले से ही buildSquare में लक्ष्य मान को योग करने का मौका मिला है, जो स्मृति आवश्यकता को कम कर सकता है कि यह 4 × 4 जादू वर्ग के लिए स्मृति में फिट हो (लेकिन मैं ' एम आश्वस्त से कम)। यदि आप केवल (N-1)×N ग्रिड बनाते हैं और लंबवत रकम से अंतिम पंक्ति की गणना करते हैं, तो N! के दूसरे कारक द्वारा Squares के आकार को कम कर देगा, जिसमें स्मृति में फ़िट होने का बेहतर मौका है (N == 4 के लिए, वास्तव में बड़े N के लिए नहीं) पहले काटने वाला।

लेकिन आपको जितनी जल्दी हो सके बाधाओं का उपयोग करने के लिए अपने एल्गोरिदम को पुन: स्थापित करना चाहिए। मान लें कि आप पहली पंक्ति 1 2 15 16 देखें। फिर आप जानते हैं कि बाएं कॉलम में 1 से नीचे तीन संख्याएं, और मुख्य विकर्ण पर तीन शेष संख्याओं को प्रत्येक को 33 तक जोड़ना चाहिए। इसलिए आपको 6612 के साथ { 3,4,5,6,7,8,9,10,11,12,13,14} से चुने गए छह नंबरों का एक सेट चाहिए। कई विकल्प नहीं हैं इन छः संख्याओं में से, उनमें से छह सबसे बड़ा केवल 69 तक है, इसलिए आपके पास

6, 10, 11, 12, 13, 14 
7, 9, 11, 12, 13, 14 
8, 9, 10, 12, 13, 14 

केवल तीन संभावनाएं हैं। निचले कोनों में दो संख्याएं दाएं कॉलम और मुख्य उत्तर-पूर्व विकर्ण से भी बाधित होती हैं। इन बाधाओं को ध्यान में रखते हुए एक साथ खोज स्थान को प्रतिबंधित कर दिया जाता है।

यदि आप अनुक्रमिक रूप से संभव वर्गों पर विचार करते हैं, तो दूसरे के बाद एक शीर्ष पंक्ति, और उम्मीदवारों को स्टोर न करें [आप जादू 4 × 4 वर्गों को स्टोर कर सकते हैं, वे बहुत अधिक नहीं हैं], आप सभी को पा सकते हैं छोटी मेमोरी में जादू वर्ग, और यदि आप बाधाओं को एक अच्छे तरीके से संभालते हैं, यहां तक ​​कि अपेक्षाकृत तेज़ी से भी।

Answer 2

मेरे पास एक दिशा है जो सहायक साबित हो सकती है। मैं लगभग यह काम कर रहा है, लेकिन अगले कुछ दिनों में इस पर किसी भी समय खर्च नहीं कर पाएगा।

सबसे पहले, मुझे विश्वास है कि यह समस्या एनपी-पूर्ण है जो इंगित करेगी कि आप घातीय रूप से इनपुट आकार बढ़ने के साथ घातीय स्मृति या समय का उपयोग करने जा रहे हैं।

किसी भी घटना में, यह मेरा दृष्टिकोण था: अपने जादू वर्ग संख्या 1..N शामिल

1. हैं, तो अपने उन एन संख्या के लिए सभी क्रमपरिवर्तन बनाने के लिए जा रहा है। सब के बाद, माया वर्ग (3,15) 1..15

2. के सभी संभव क्रमपरिवर्तन की एक सबसेट चाल के रूप में यह है, तो उत्पन्न होता है प्रत्येक क्रमचय दूर करने के लिए है हो जाएगा पंक्तियों है कि यह नहीं है का प्रतिनिधित्व करता है के सभी जादू संख्या तक योग। इस तरह आप सभी क्रमपरिवर्तनों को संग्रहित नहीं करते हैं, केवल वे जो बहुत ही आशाजनक हैं जिससे घातीय स्मृति से बचें (लेकिन घातीय समय नहीं)। दूसरे शब्दों में, प्रत्येक क्रमपरिवर्तन उत्पन्न करने के साथ-साथ, केवल इसे सहेजना अगर यह एक जादू वर्ग होना संभव है। मैं एक जनरेटर है कि एक परीक्षण किया पर एक क्वालीफायर के साथ क्रमपरिवर्तन बनाने के लिए एक सूची समझ का इस्तेमाल किया यह सुनिश्चित करें कि पंक्तियों के सभी सही ढंग से अभिव्यक्त किया

3. मेरा परीक्षण समारोह एक पैरामीटर कि इस मामले में पंक्ति लंबाई (3 संकेत दिया ले लिया) और [8,1,6,3,5,7,4,9,2] के क्रमपरिवर्तन की जांच करने में सक्षम था और यह निर्धारित करता है कि प्रत्येक पंक्ति (प्रत्येक उपन्यास 1-3, 4-6,7-9 को 15 तक सम्मिलित किया गया ।
4. क्रमपरिवर्तन जहां कम से कम जादुई संख्या के लिए हर पंक्ति रकम, तो एम.एन. मानदंडों के आराम के लिए फ़िल्टर कर प्राप्त करने के बाद।

सुनिश्चित करें कि क्रमपरिवर्तन बनाने के लिए अपने एल्गोरिथ्म पूंछ पुनरावर्ती है, वैसे।

फिर से, यह मेरे लिए काम कर रहा था (सिवाय इसके कि यह कहां नहीं था;)), लेकिन मैं कुछ दिनों के लिए अपने कंप्यूटर से दूर हूं।

उम्मीद है कि इससे मदद मिलती है।