縦型探索ってこう?
再帰使えばもっと楽なんだろうけど、今回はあえて使わずにスタックで。動作未確認。
#!/usr/bin/python # -*- coding: utf-8 -*- import random def endTest(answer): str = "" for a in answer: str += a print str if str == "AFG": return True return False def getNextCandidate(now,mt): sets = set("") for m in mt[now]: sets.add(m) return sets def vSearch(startWord,mt): # mt マルコフテーブル answer = [] candidateStack = [] count = 0 now = startWord # cand は mapあたり cand = getNextCandidate(now,mt) candidateStack.append(cand) while True: #print "now", #print now, #print "answer", #print answer, #print "cand", #print cand #print "candidateStack", #print candidateStack #raw_input() # candが空になったらcandidateStackから引っ張り出す while len(cand) == 0: if len(candidateStack) == 0: return ""#探索失敗 cand = candidateStack.pop(-1) count -= 1 answer.pop(-1) if len(answer) == 0: return"" now = answer[-1] while True: next = random.choice(mt[now]) print "next", print next candFlag = False for a in cand: if next == a: candFlag = True break if candFlag == True: break cand.remove(next) if next == "yyend" or count > 30 : if endTest(answer) == True: answer.append(next) break else: print "false" continue candidateStack.append(cand) cand = getNextCandidate(next,mt) now = next answer.append(now) count += 1 result = "" for s in answer: result += s return result if __name__ == "__main__": mt = {} mt["yystart"] = ["A"] mt["A"] = ["B","F"] mt["B"] = ["C","D","E"] mt["C"] = ["yyend"] mt["D"] = ["yyend"] mt["E"] = ["yyend"] mt["F"] = ["C","G"] mt["G"] = ["yyend"] mt["yyend"] = [] print vSearch("yystart",mt)
追記
思いっきり間違えていたのでソースコードを思いっきり修正しました。