夫妻过河问题---图论算法的应用（Python实现）

小灰灰 2022-05-08 13:04 75阅读 0赞

class Graph(object):  
    """docstring for Graph"""  
    def \_\_init\_\_(self, mat):  
        super(Graph, self).\_\_init\_\_()  
        self.n = len(mat\[0\])  
        self.edge = 0  
        self.mat = mat  
        self.vertex = \[\]  
        self.visited = \[0 for i in range(n)\]  
        self.found = 0  
        self.path = \[\]  
        self.solution = \[\]  
    def DFS(self):  
        for i in range(self.n):  
            if not self.visited\[i\]:  
                self.dfs(i)  
    def dfs(self,i):  
        self.visited\[i\] = 1  
        print(i)  
        for j in range(self.n):  
            if not self.visited\[j\] and self.mat\[i\]\[j\]:  
                self.dfs(j)  
    def CrossRiver(self):  
        self.vertex = \[\]  
        for i in range(2):  
            for j in range(2):  
                for k in range(2):  
                    for p in range(2):  
                        for q in range(2):  
                            for r in range(2):  
                                self.vertex.append(\[i,j,k,p,q,r\])                              
        self.n = 64  
        self.mat = mat = \[\[0 for j in range(self.n)\] for i in range(self.n)\]  
        self.visited = \[0 for i in range(self.n)\]  
        self.initialize()  
        self.DFS\_()  
    def DFS\_(self):  
        for i in range(self.n):  
            if not self.visited\[i\] and not self.found:  
                self.dfs\_(i)  
    def dfs\_(self,i):  
        self.visited\[i\] = 1  
        \#print(i,self.mat\[i\]\[63\],self.vertex\[i\])  
        self.path.append(self.vertex\[i\])  
        if self.mat\[i\]\[63\]:  
            \#print(63,self.vertex\[63\])  
            print("found!")  
            self.path.append(self.vertex\[63\])  
            self.found = 1  
        for j in range(self.n):  
            if not self.visited\[j\] and self.mat\[i\]\[j\] and self.isSafe(G.vertex\[j\]):  
                if not self.found:  
                    self.dfs\_(j)  
    def isSafe(self,state):  
        a1,a2,b1,b2,c1,c2 = state\[0\],state\[1\],state\[2\],state\[3\],state\[4\],state\[5\]  
        if \[a1,a2,b1,b2,c1,c2\] == \[1,1,1,1,1,1\]:  
            return True  
        if a2 != a1 and (a2 == b1 or a2 == c1):  
            return False  
        if b2 != b1 and (b2 == a1 or b2 == c1):  
            return False  
        if c2 != c1 and (c2 == a1 or c2 == b1):  
            return False  
        return True  
    def initialize(self):  
        for i in range(self.n):  
            for j in range(self.n):  
                if self.isConnected(self.vertex\[i\],self.vertex\[j\]):  
                    self.mat\[i\]\[j\] = 1  
    def isConnected(self,state1,state2):  
        changes = \[\]  
        for i in range(len(state1)):  
            if state1\[i\] != state2\[i\]:  
                changes.append(\[state1\[i\],state2\[i\]\])  
        if changes == \[\]:  
            return False  
        if len(changes) == 1:  
            return True  
        if len(changes) == 2:  
            if changes\[0\]\[0\] != changes\[1\]\[0\]:  
                return False  
            else:  
                return True  
        else:  
            return False

def showMoves(self):  
        n = len(self.path)  
        solution = \[\]  
        m1 = "Move man 1 to the other side; "  
        m2 = "Move lady 1 to the other side; "  
        m3 = "Move man 2 to the other side; "  
        m4 = "Move lady 2 to the other side; "  
        m5 = "Move man 3 to the other side; "  
        m6 = "Move lady 3 to the other side; "

n1 = "Move man 1 back from the other side; "  
        n2 = "Move lady 1 back from the other side; "  
        n3 = "Move man 2 back from the other side; "  
        n4 = "Move lady 2 back from the other side; "  
        n5 = "Move man 3 back from the other side; "  
        n6 = "Move lady 3 back from the other side; "

path = G.path  
        for i in range(n-1):  
            \#This state  
            a1,a2,b1,b2,c1,c2 = path\[i\]\[0\],path\[i\]\[1\],path\[i\]\[2\],\\  
            path\[i\]\[3\],path\[i\]\[4\],path\[i\]\[5\]  
            \#Next state  
            a1n,a2n,b1n,b2n,c1n,c2n = path\[i+1\]\[0\],path\[i+1\]\[1\],path\[i+1\]\[2\],\\  
            path\[i+1\]\[3\],path\[i+1\]\[4\],path\[i+1\]\[5\]  
            \#Initialize move  
            move = ''  
            \#Judge  
            \#Couple one  
            if a1 == 0 and a1n == 1:  
                move += m1  
            if a1 == 1 and a1n == 0:  
                move += n1

if a2 == 0 and a2n == 1:  
                move += m2  
            if a2 == 1 and a2n == 0:  
                move += n2  
            \#Copule two  
            if b1 == 0 and b1n == 1:  
                move += m3  
            if b1 == 1 and b1n == 0:  
                move += n3  
            if b2 == 0 and b2n == 1:  
                move += m4  
            if b2 == 1 and b2n == 0:  
                move += n4  
            \#Couple three  
            if c1 == 0 and c1n == 1:  
                move += m5  
            if c1 == 1 and c1n == 0:  
                move += n5  
            if c2 == 0 and c2n == 1:  
                move += m6  
            if c2 == 1 and c2n == 0:  
                move += n6  
            self.solution.append('Step '+str(i+1)+': '+move)  
        for step in G.solution:  
            print(step)

n = 4  
mat = \[\[0 for j in range(n)\] for i in range(n)\]  
G = Graph(mat)  
G.CrossRiver()  
print("\\n走法如下：")  
for move in G.path:  
    print(move)  
G.showMoves()