हास्केल पर बैकट्रैकिंग लागू करना

Question

मुझे हास्केल पर बैकट्रैकिंग करने में समस्या है, मुझे पता है कि रिकर्सिव फ़ंक्शंस कैसे करें, लेकिन जब मैं एकाधिक समाधान या सर्वोत्तम (बैकट्रैकिंग) प्राप्त करने का प्रयास करता हूं तो मुझे परेशानी होती है।

कुछ तारों के साथ एक सूची है, तो मुझे स्ट्रिंग से एक अक्षर बदलने के लिए एक स्ट्रिंग से दूसरे समाधान प्राप्त करने की आवश्यकता है, मुझे सूची, पहली स्ट्रिंग और अंतिम प्राप्त होगी। यदि कोई समाधान है तो समाधान की वापसी की गई है, अगर समाधान नहीं है तो यह -1 देता है। यहाँ एक उदाहरण है:

wordF ["spice","stick","smice","stock","slice","slick","stock"] "spice" "stock" 

तब मैं अपने सूची है और मैं "spice" के साथ शुरू और "stock" के लिए मिलता है और सबसे अच्छा समाधान है ["spice","slice","slick","stick","stock"] चार चरणों के साथ "spice" से "stock" को पाने के लिए की जरूरत है। तो यह 4 लौटाता है।

एक और समाधान ["spice","smice","slice","slick","stick","stock"]"stock" पर जाने के लिए पांच चरणों के साथ है, तो यह `5 लौटाता है। लेकिन यह एक गलत समाधान है क्योंकि एक और है जो इस से कम कदमों के साथ बेहतर है।

मैं सबसे अच्छा समाधान पाने के लिए एक बैक ट्रैकिंग बनाने, क्योंकि मैं कैसे है कि मेरे कोड खोज एक और समाधान और न कि केवल एक ..

यहाँ एक कोड है कि मैं करने की कोशिश की है बनाने के लिए पता नहीं है समस्याएं हो रही हैं बनाने, लेकिन मैं कुछ त्रुटियों, शुरू हो, btw मैं न पता है मेरे रास्ते के लिए अगर "बनाने के" बैक ट्रैकिंग अच्छा है या अगर कोई कुछ गलतियों कि नहीं देख im हैं ..

wordF :: [String] -> String -> String -> (String, String, Int) 
    wordF [] a b = (a, b, -1) 
    wordF list a b | (notElem a list || notElem b list) = (a, b, -1) 
      | otherwise = (a, b, (wordF2 list a b [a] 0 (length list))) 
    wordF2 :: [String] -> String -> String -> [String] -> Int -> Int -> Int 
    wordF2 list a b list_aux cont maxi | (cont==maxi) = 1000 
           | (a==b) = length list_aux 
           | (a/=b) && (cont<maxi) && notElemFound && (checkin /= "ThisWRONG") && (wording1<=wording2) = wording1 
           | (a/=b) && (cont<maxi) && notElemFound && (checkin /= "ThisWRONG") && (wording1>wording2) = wording2 
           | (a/=b) && (checkin == "ThisWRONG") = wordF2 list a b list_aux (cont+1) maxi 
           where 
           checkin = (check_word2 a (list!!cont) (list!!cont) 0) 
           wording1 = (wordF2 list checkin b (list_aux++[checkin]) 0 maxi) 
           wording2 = (wordF2 list checkin b (list_aux++[checkin]) 1 maxi) 
           notElemFound = ((any (==(list!!cont)) list_aux) == False) 
check_word2 :: String -> String -> String -> Int -> String 
check_word2 word1 word2 word3 dif | (dif > 1) = "ThisWRONG" 
           | ((length word1 == 1) && (length word2 == 1) && (head word1 == head word2)) = word3 
           | ((length word1 == 1) && (length word2 == 1) && (head word1 /= head word2) && (dif<1)) = word3 
           | ((head word1) == (head word2)) = check_word2 (tail word1) (tail word2) word3 dif 
           | otherwise = check_word2 (tail word1) (tail word2) word3 (dif+1) 

मेरा पहला समारोह wordF2 सूची प्राप्त , अंत, पहले तत्व के साथ वर्तमान समाधान प्राप्त करने के लिए एक सहायक सूची जो हमेशा वहां होगी ([a]), एक काउंटर वाई वें 0, और काउंटर (length list) का अधिकतम आकार ..

और दूसरा समारोह check_word2 यह जाँच करता है अगर एक शब्द "slice" को "spice" की तरह, एक और शब्द को पारित अगर यह नहीं कर सकते चाहते "spice""spoca" को वापस करती "ThisWRONG" कर सकते हैं।

यह समाधान पैटर्न मैच विफलता

Program error: pattern match failure: wordF2 ["slice","slick"] "slice" "slick" ["slice"] 0 1 

मैं थोड़ा मामलों और कुछ भी नहीं के साथ कोशिश कर रहा था की एक त्रुटि हो जाता है, और मुझे लगता है कि मैं गिनती और अधिकतम के साथ इस सूची में एक गलत स्थान प्राप्त सीमित कर रहा हूँ।

या हो सकता है मैं नहीं पता Haskell पर उलटे पांव लौटने को लागू करने के लिए कैसे कई समाधान, सबसे अच्छा समाधान, आदि प्राप्त करने के लिए ..

अद्यतन: मैं एक समाधान है, लेकिन इसके उलटे पांव लौटने से नहीं किया

wordF :: [String] -> String -> String -> (String, String, Int) 
wordF [] a b = (a, b, -1) 
wordF list a b | (notElem a list || notElem b list) = (a, b, -1) 
      | otherwise = (a, b, (wordF1 list a b)) 

wordF1 :: [String] -> String -> String -> Int 
wordF1 list a b | ((map length (wordF2 (subconjuntos2 (subconjuntos list) a b))) == []) = -1 
      | (calculo > 0) = calculo 
      | otherwise = -1 
      where 
      calculo = (minimum (map length (wordF2 (subconjuntos2 (subconjuntos list) a b))))-1 

wordF2 :: [[String]] -> [[String]] 
wordF2 [[]] = [] 
wordF2 (x:xs) | ((length xs == 1) && ((check_word x) == True) && ((check_word (head xs)) == True)) = x:xs 
      | ((length xs == 1) && ((check_word x) == False) && ((check_word (head xs)) == True)) = xs 
      | ((length xs == 1) && ((check_word x) == True) && ((check_word (head xs)) == False)) = [x] 
      | ((length xs == 1) && ((check_word x) == False) && ((check_word (head xs)) == False)) = [] 
      | ((check_word x) == True) = x:wordF2 xs 
      | ((check_word x) == False) = wordF2 xs 

check_word :: [String] -> Bool 
check_word [] = False 
check_word (x:xs) | ((length xs == 1) && ((check_word2 x (head xs) 0) == True)) = True 
       | ((length xs >1) && ((check_word2 x (head xs) 0) == True)) = True && (check_word xs) 
       | otherwise = False 

check_word2 :: String -> String -> Int -> Bool 
check_word2 word1 word2 dif | (dif > 1) = False 
         | ((length word1 == 1) && (length word2 == 1) && (head word1 == head word2)) = True 
         | ((length word1 == 1) && (length word2 == 1) && (head word1 /= head word2) && (dif<1)) = True 
         | ((head word1) == (head word2)) = check_word2 (tail word1) (tail word2) dif 
         | otherwise = check_word2 (tail word1) (tail word2) (dif+1) 

subconjuntos2 :: [[String]] -> String -> String -> [[String]] 
subconjuntos2 [] a b  = [] 
subconjuntos2 (x:xs) a b | (length x <= 1) = subconjuntos2 xs a b 
        | ((head x == a) && (last x == b)) = (x:subconjuntos2 xs a b) 
        | ((head x /= a) || (last x /= b)) = (subconjuntos2 xs a b) 

subconjuntos :: [a] -> [[a]] 
subconjuntos []  = [[]] 
subconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub 
where sub = subconjuntos xs 

एमएमएम इसका अक्षम हो सकता है लेकिन कम से कम यह समाधान करता है .. मैं सभी सकारात्मक समाधानों की खोज करता हूं, मैं सिर == "टुकड़ा" और अंतिम == "स्टॉक" की तुलना करता हूं, फिर मैं उन समाधानों को फ़िल्टर करता हूं जो समाधान हैं और प्रिंट करते हैं छोटा एक, धन्यवाद और यदि आपके पास कोई सुझाव है तो यह कहें :)

Answer 1

अच्छी तरह से परीक्षण नहीं है, लेकिन यह उम्मीद है कि मदद मिलेगी:

import Data.Function (on) 
import Data.List (minimumBy, delete) 
import Control.Monad (guard) 

type Word = String 
type Path = [String] 

wordF :: [Word] -> Word -> Word -> Path 
wordF words start end = 
    start : minimumBy (compare `on` length) (generatePaths words start end) 

-- Use the list monad to do the nondeterminism and backtracking. 
-- Returns a list of all paths that lead from `start` to `end` 
-- in steps that `differByOne`. 
generatePaths :: [Word] -> Word -> Word -> [Path] 
generatePaths words start end = do 
    -- Choose one of the words, nondeterministically 
    word <- words 

    -- If the word doesn't `differByOne` from `start`, reject the choice 
    -- and backtrack. 
    guard $ differsByOne word start 

    if word == end 
    then return [word] 
    else do 
     next <- generatePaths (delete word words) word end 
     return $ word : next 

differsByOne :: Word -> Word -> Bool 
differsByOne "" "" = False 
differsByOne (a:as) (b:bs) 
    | a == b = differsByOne as bs 
    | otherwise = as == bs 

उदाहरण चलाएँ:

>>> wordF ["spice","stick","smice","stock","slice","slick","stock"] "spice" "stock" 
["spice","slice","slick","stick","stock"] 

हास्केल में सूची मोनैड को आमतौर पर नोडेटर्मिनिस्टिक, बैकट्रैकिंग गणना के रूप में वर्णित किया जाता है। उपर्युक्त कोड क्या कर रहा है, सूची को मोनैड विकल्पों को उत्पन्न करने की ज़िम्मेदारी लेने की अनुमति दे रहा है, परीक्षण कर रहा है कि वे मानदंडों को पूरा करते हैं, और सबसे हालिया पसंद बिंदु में विफलता पर बैकट्रैकिंग करते हैं। सूची मोनड का बंधन, उदा। word <- words, इसका मतलब है "nondeterministically words में से एक को चुनें। guard का अर्थ है" यदि अब तक विकल्प इस स्थिति को पूरा नहीं करते हैं, बैकट्रैक और एक अलग विकल्प बनाते हैं। सूची मोनैड गणना का नतीजा उन सभी परिणामों की सूची है जो किसी भी guard एस का उल्लंघन नहीं करते हैं।

यदि यह सूची की समझों की तरह दिखता है, तो, सूची की समझ एक ही बात है जैसे सूची मोनैड- मैंने इसे समझ के बजाय मोनाड के साथ व्यक्त करना चुना।

Answer 2

क्लासिक ब्रूट-फोर्स खोज समस्याओं पर हाल ही में प्रकाशित कई लेख हैं।

• मार्क डोमिनस ने एक सरल संपूर्ण खोज के लिए a simple example of using lists प्रकाशित किया।
• जस्टिन ले ने पिछले लेख में a small modification के साथ पीछा किया जो खोज की वर्तमान स्थिति को ट्रैक करने में सरल बना।
• मैंने a further modification के साथ पीछा किया जो खोज पेड़ के हिस्से की जल्दी अस्वीकृति से लाभ को मापने की अनुमति देता है।

ध्यान दें कि मेरे लेख में कोड काफी धीमा है क्योंकि यह काम की मात्रा को मापने के साथ-साथ इसे कर रहा है। मेरे आलेख में खोज पेड़ के हिस्सों को तुरंत अस्वीकार करने के लिए अच्छे उदाहरण हैं, लेकिन इसे केवल एक उदाहरण माना जाना चाहिए - उत्पादन कोड नहीं। प्रत्यावर्तन

Answer 3

एक जानवर बल दृष्टिकोण का उपयोग कर:

import Data.List (filter, (\\), reverse, delete, sortBy) 
import Data.Ord (comparing) 

neighbour :: String -> String -> Bool 
neighbour word = (1 ==) . length . (\\ word) 

process :: String -> String -> [String] -> [(Int, [String])] 
process start end dict = 
    let 
    loop :: String -> String -> [String] -> [String] -> [(Int,[String])] -> [(Int,[String])] 
    loop start end dict path results = 
     case next of 
     [] -> results 
     xs -> 
      if elem end xs 
      then (length solution, solution) : results 
      else results ++ branches xs 
     where 
     next  = filter (neighbour start) dict' 
     dict'  = delete start dict 
     path'  = start : path 
     branches xs = [a | x <- xs, a <- loop x end dict' path' results] 
     solution = reverse (end : path') 
    in 
    loop start end dict [] [] 

shortestSolution :: Maybe Int 
shortestSolution = shortest solutions 
    where 
    solutions = process start end dict 
    shortest s = 
     case s of 
     [] -> Nothing 
     xs -> Just $ fst $ head $ sortBy (comparing fst) xs 

start = "spice" 
end = "stock" 
dict = ["spice","stick","smice","slice","slick","stock"] 

नोट्स:

• इस कोड को सभी possibles समाधान की गणना करता है (process) स्पर्श करें और कम से कम एक (shortestSolution), के रूप में कार्ल ने कहा, आप बेहतर प्रदर्शन के लिए खोज पेड़ के हिस्सों को छीनना चाह सकता है।

• का उपयोग -1 लौटने के बजाय जब कोई फ़ंक्शन परिणाम लौटने में विफल हो सकता है तो उसे प्राथमिकता दी जाती है।

---

एक और तरीका है चौड़ाई-पहले खोज के साथ एक पेड़ का उपयोग कर:

import Data.Tree 
import Data.List(filter, (\\), delete) 
import Data.Maybe 

node :: String -> [String] -> Tree String 
node label dict = Node{ rootLabel = label, subForest = branches label (delete label dict) } 

branches :: String -> [String] -> [Tree String] 
branches start dict = map (flip node dict) (filter (neighbour start) dict) 

neighbour :: String -> String -> Bool 
neighbour word = (1 ==) . length . (\\ word) 

-- breadth first traversal 
shortestBF tree end = find [tree] end 0 
    where 
    find ts end depth 
     | null ts = Nothing 
     | elem end (map rootLabel ts) = Just depth 
     | otherwise = find (concat (map subForest ts)) end (depth+1) 

result = shortestBF tree end 

tree :: Tree String 
tree = node start dict 

start = "spice" 
end = "stock" 
dict = ["spice","stick","smice","slice","slick","stock"]