Nave - A*

import copy

class Nod:
    def __init__(self, nrStare, stare):
        self.nrStare=nrStare
        self.stare=stare
        self.valoare=self.calculeazaValoare()
        self.valoareMaxima=self.valoare+self.calculeazaValoareMaxima()

    def calculeazaValoare(self):
        valoare=50

        if len(self.stare)>4:
            if self.stare[4]==2:
                valoare+=4
        if len(self.stare)>2:
            if self.stare[2]==1:
                valoare+=5
        for i in range(0,len(self.stare)-1):
            if self.stare[i]%2-(self.stare[i+1]%2)==0:
                valoare-=8
        return valoare

    def calculeazaValoareMaxima(self):
        valoare=0
        if 1 not in self.stare and len(self.stare)<3:
            valoare+=5
        if 2 not in self.stare and len(self.stare)<5:
            valoare+=4
        return valoare

    def navaDejaRepartizata(self, nava):
        if nava in self.stare:
            return True
        return False

def adaugareFrontiera(nod, frontiera):
    if len(frontiera)==0:
        frontiera.insert(0,nod)
        return 1
    else:
        for i in range(0,len(frontiera)):
            if nod.valoareMaxima>=frontiera[i].valoareMaxima:
                frontiera.insert(i,nod)
                return 1
    frontiera.append(nod)

def afisareSolutie(nod):
    print ("Repartizarea cea mai buna este (", end="")
    for echipaj in nod.stare:
        print ("{} ".format(echipaj), end="")
    print (") cu valoarea {}.".format(nod.valoare))

def Cautare():

    frontiera=[]
    teritoriu=[]
    optim=Nod(1,[])
    frontiera.append(optim)

    while len(frontiera)!=0:
        nodCurent=frontiera.pop(0)

        if len(nodCurent.stare)==5:
            afisareSolutie(nodCurent)
            print ("Au fost expandate {} noduri si evaluate {} noduri.".format(len(teritoriu),len(frontiera)))
            return 1

        teritoriu.append(nodCurent)
        for i in range(1,6):
            if nodCurent.navaDejaRepartizata(i)==False:
                stare=copy.deepcopy(nodCurent.stare)
                stare.append(i)
                nod=Nod(len(frontiera)+len(teritoriu)+1,stare)
                adaugareFrontiera(nod, frontiera)





Cautare()