I am doing a work where i have to use some estrategies finding a final state, begining in other state this is the example that´s correct give it by the theachers, when i use the estrategy 1, as you can see my program generate 2 id nodes more than it must generate, but when i use the estrategy 2 it runs properly, and i am getting mad, because i don´t understand why:
init:(3118801, 273133)
goal:(3106201, 285733)
strategy:BFS
max_depth:500000
[0][(0.000,0.000),(3118801,273133),None,None,0,0.0,0.0000]
[2][(600.000,95.070),(3118201,273133),0,S,1,0.0,1.0000]
[9][(1200.000,98.479),(3118201,272533),2,O,2,0.0,2.0000]
[26][(1800.000,98.479),(3118201,271933),9,O,3,0.0,3.0000]
[46][(2400.000,98.479),(3117601,271933),26,S,4,0.0,4.0000]
[63][(3000.000,98.479),(3117601,271333),46,O,5,0.0,5.0000]
[88][(3600.000,98.479),(3117601,270733),63,O,6,0.0,6.0000]
[112][(4200.000,98.479),(3117001,270733),88,S,7,0.0,7.0000]
[130][(4800.000,98.479),(3117001,270133),112,O,8,0.0,8.0000]
[151][(5400.000,98.479),(3116401,270133),130,S,9,0.0,9.0000]
[167][(6000.000,98.479),(3116401,269533),151,O,10,0.0,10.0000]
[180][(6600.000,98.479),(3115801,269533),167,S,11,0.0,11.0000]
[189][(7200.000,98.479),(3115201,269533),180,S,12,0.0,12.0000]
[201][(7800.000,98.479),(3114601,269533),189,S,13,0.0,13.0000]
[217][(8400.000,98.479),(3114001,269533),201,S,14,0.0,14.0000]
[235][(9000.000,98.479),(3113401,269533),217,S,15,0.0,15.0000]
[251][(9600.000,98.479),(3112801,269533),235,S,16,0.0,16.0000]
[264][(10200.000,98.479),(3112201,269533),251,S,17,0.0,17.0000]
[277][(10800.000,98.479),(3111601,269533),264,S,18,0.0,18.0000]
[292][(11400.000,98.479),(3111001,269533),277,S,19,0.0,19.0000]
[309][(12000.000,98.479),(3110401,269533),292,S,20,0.0,20.0000]
[327][(12600.000,98.479),(3109801,269533),309,S,21,0.0,21.0000]
[343][(13200.000,98.479),(3109801,270133),327,E,22,0.0,22.0000]
[358][(13800.000,98.479),(3109201,270133),343,S,23,0.0,23.0000]
[379][(14400.000,98.479),(3108601,270133),358,S,24,0.0,24.0000]
[397][(15000.000,98.479),(3108001,270133),379,S,25,0.0,25.0000]
[411][(15600.000,98.479),(3108001,270733),397,E,26,0.0,26.0000]
[424][(16200.000,98.479),(3108001,271333),411,E,27,0.0,27.0000]
[439][(16800.000,98.479),(3107401,271333),424,S,28,0.0,28.0000]
[457][(17400.000,98.479),(3106801,271333),439,S,29,0.0,29.0000]
[474][(18000.000,98.479),(3106201,271333),457,S,30,0.0,30.0000]
[489][(18600.000,98.479),(3106201,271933),474,E,31,0.0,31.0000]
[501][(19200.000,98.479),(3106201,272533),489,E,32,0.0,32.0000]
[519][(19800.000,98.479),(3105601,272533),501,S,33,0.0,33.0000]
[548][(20400.000,98.479),(3105601,273133),519,E,34,0.0,34.0000]
[582][(21000.000,98.479),(3105601,273733),548,E,35,0.0,35.0000]
[623][(21600.000,98.479),(3105601,274333),582,E,36,0.0,36.0000]
[666][(22200.000,98.479),(3105001,274333),623,S,37,0.0,37.0000]
[702][(22800.000,98.479),(3105001,274933),666,E,38,0.0,38.0000]
[733][(23400.000,98.479),(3104401,274933),702,S,39,0.0,39.0000]
[769][(24000.000,98.479),(3104401,275533),733,E,40,0.0,40.0000]
[805][(24600.000,98.479),(3104401,276133),769,E,41,0.0,41.0000]
[847][(25200.000,98.479),(3104401,276733),805,E,42,0.0,42.0000]
[893][(25800.000,98.479),(3104401,277333),847,E,43,0.0,43.0000]
[946][(26400.000,98.479),(3103801,277333),893,S,44,0.0,44.0000]
[1001][(27000.000,98.479),(3103801,277933),946,E,45,0.0,45.0000]
[1059][(27600.000,98.479),(3103801,278533),1001,E,46,0.0,46.0000]
[1130][(28200.000,98.479),(3103801,279133),1059,E,47,0.0,47.0000]
[1209][(28800.000,98.479),(3103801,279733),1130,E,48,0.0,48.0000]
[1291][(29400.000,98.479),(3103801,280333),1209,E,49,0.0,49.0000]
[1374][(30000.000,98.479),(3103801,280933),1291,E,50,0.0,50.0000]
[1462][(30600.000,98.479),(3103801,281533),1374,E,51,0.0,51.0000]
[1552][(31200.000,98.479),(3103801,282133),1462,E,52,0.0,52.0000]
[1639][(31800.000,98.479),(3103801,282733),1552,E,53,0.0,53.0000]
[1722][(32400.000,98.479),(3104401,282733),1639,N,54,0.0,54.0000]
[1809][(33000.000,98.479),(3104401,283333),1722,E,55,0.0,55.0000]
[1902][(33600.000,98.479),(3103801,283333),1809,S,56,0.0,56.0000]
[1990][(34200.000,98.479),(3103801,283933),1902,E,57,0.0,57.0000]
[2068][(34800.000,98.479),(3103801,284533),1990,E,58,0.0,58.0000]
[2135][(35400.000,98.479),(3104401,284533),2068,N,59,0.0,59.0000]
[2188][(36000.000,98.479),(3104401,285133),2135,E,60,0.0,60.0000]
[2239][(36600.000,98.479),(3104401,285733),2188,E,61,0.0,61.0000]
[2284][(37200.000,98.479),(3105001,285733),2239,N,62,0.0,62.0000]
[2328][(37800.000,98.479),(3105601,285733),2284,N,63,0.0,63.0000]
[2384][(38400.000,98.479),(3106201,285733),2328,N,64,0.0,64.0000]
And my code gives me the next result:
[0][(0, 0),(3118801,273133),None,None,0,0,0]
[2][(600.0, 95.06982421875),(3118201,273133),0,S,1,0,1]
[9][(1200.0, 98.47891235351562),(3118201,272533),2,O,2,0,2]
[26][(1800.0, 98.47891235351562),(3118201,271933),9,O,3,0,3]
[46][(2400.0, 98.47891235351562),(3117601,271933),26,S,4,0,4]
[63][(3000.0, 98.47891235351562),(3117601,271333),46,O,5,0,5]
[88][(3600.0, 98.47891235351562),(3117601,270733),63,O,6,0,6]
[112][(4200.0, 98.47891235351562),(3117001,270733),88,S,7,0,7]
[130][(4800.0, 98.47891235351562),(3117001,270133),112,O,8,0,8]
[151][(5400.0, 98.47891235351562),(3116401,270133),130,S,9,0,9]
[167][(6000.0, 98.47891235351562),(3116401,269533),151,O,10,0,10]
[180][(6600.0, 98.47891235351562),(3115801,269533),167,S,11,0,11]
[189][(7200.0, 98.47891235351562),(3115201,269533),180,S,12,0,12]
[201][(7800.0, 98.47891235351562),(3114601,269533),189,S,13,0,13]
[217][(8400.0, 98.47891235351562),(3114001,269533),201,S,14,0,14]
[235][(9000.0, 98.47891235351562),(3113401,269533),217,S,15,0,15]
[251][(9600.0, 98.47891235351562),(3112801,269533),235,S,16,0,16]
[264][(10200.0, 98.47891235351562),(3112201,269533),251,S,17,0,17]
[277][(10800.0, 98.47891235351562),(3111601,269533),264,S,18,0,18]
[292][(11400.0, 98.47891235351562),(3111001,269533),277,S,19,0,19]
[309][(12000.0, 98.47891235351562),(3110401,269533),292,S,20,0,20]
[327][(12600.0, 98.47891235351562),(3109801,269533),309,S,21,0,21]
[343][(13200.0, 98.47891235351562),(3109801,270133),327,E,22,0,22]
[359][(13800.0, 98.47891235351562),(3109201,270133),343,S,23,0,23]
[381][(14400.0, 98.47891235351562),(3108601,270133),359,S,24,0,24]
[399][(15000.0, 98.47891235351562),(3108001,270133),381,S,25,0,25]
[413][(15600.0, 98.47891235351562),(3108001,270733),399,E,26,0,26]
[426][(16200.0, 98.47891235351562),(3108001,271333),413,E,27,0,27]
[441][(16800.0, 98.47891235351562),(3107401,271333),426,S,28,0,28]
[459][(17400.0, 98.47891235351562),(3106801,271333),441,S,29,0,29]
[476][(18000.0, 98.47891235351562),(3106201,271333),459,S,30,0,30]
[491][(18600.0, 98.47891235351562),(3106201,271933),476,E,31,0,31]
[503][(19200.0, 98.47891235351562),(3106201,272533),491,E,32,0,32]
[521][(19800.0, 98.47891235351562),(3105601,272533),503,S,33,0,33]
[550][(20400.0, 98.47891235351562),(3105601,273133),521,E,34,0,34]
[584][(21000.0, 98.47891235351562),(3105601,273733),550,E,35,0,35]
[625][(21600.0, 98.47891235351562),(3105601,274333),584,E,36,0,36]
[668][(22200.0, 98.47891235351562),(3105001,274333),625,S,37,0,37]
[704][(22800.0, 98.47891235351562),(3105001,274933),668,E,38,0,38]
[735][(23400.0, 98.47891235351562),(3104401,274933),704,S,39,0,39]
[771][(24000.0, 98.47891235351562),(3104401,275533),735,E,40,0,40]
[807][(24600.0, 98.47891235351562),(3104401,276133),771,E,41,0,41]
[849][(25200.0, 98.47891235351562),(3104401,276733),807,E,42,0,42]
[895][(25800.0, 98.47891235351562),(3104401,277333),849,E,43,0,43]
[948][(26400.0, 98.47891235351562),(3103801,277333),895,S,44,0,44]
[1003][(27000.0, 98.47891235351562),(3103801,277933),948,E,45,0,45]
[1061][(27600.0, 98.47891235351562),(3103801,278533),1003,E,46,0,46]
[1132][(28200.0, 98.47891235351562),(3103801,279133),1061,E,47,0,47]
[1211][(28800.0, 98.47891235351562),(3103801,279733),1132,E,48,0,48]
[1293][(29400.0, 98.47891235351562),(3103801,280333),1211,E,49,0,49]
[1376][(30000.0, 98.47891235351562),(3103801,280933),1293,E,50,0,50]
[1464][(30600.0, 98.47891235351562),(3103801,281533),1376,E,51,0,51]
[1554][(31200.0, 98.47891235351562),(3103801,282133),1464,E,52,0,52]
[1641][(31800.0, 98.47891235351562),(3103801,282733),1554,E,53,0,53]
[1724][(32400.0, 98.47891235351562),(3104401,282733),1641,N,54,0,54]
[1811][(33000.0, 98.47891235351562),(3104401,283333),1724,E,55,0,55]
[1904][(33600.0, 98.47891235351562),(3103801,283333),1811,S,56,0,56]
[1992][(34200.0, 98.47891235351562),(3103801,283933),1904,E,57,0,57]
[2070][(34800.0, 98.47891235351562),(3103801,284533),1992,E,58,0,58]
[2137][(35400.0, 98.47891235351562),(3104401,284533),2070,N,59,0,59]
[2190][(36000.0, 98.47891235351562),(3104401,285133),2137,E,60,0,60]
[2241][(36600.0, 98.47891235351562),(3104401,285733),2190,E,61,0,61]
[2286][(37200.0, 98.47891235351562),(3105001,285733),2241,N,62,0,62]
[2330][(37800.0, 98.47891235351562),(3105601,285733),2286,N,63,0,63]
[2386][(38400.0, 98.47891235351562),(3106201,285733),2330,N,64,0,64]
I can´t find the reason at this problem, this is my implementation, the BFS estrategy is the 1:
def expandir(self, nodo, factor_avance, altura_maxima, mapa,frontera):
valor_inicial = -99999.0
for dataset_name in mapa.datasets.keys():
valory=nodo.estado.get_y()
valorx=nodo.estado.get_x()
valorN = mapa.umt_YX(valory, valorx, dataset_name)
if(valorN != -99999.0):
valor_inicial = valorN
break
listaSucesores = nodo.estado.sucesor(factor_avance, 600, -99999.0, altura_maxima, mapa, valor_inicial)
heuristica=0
for i in range(0, len(listaSucesores)):
nEstado=listaSucesores[i][1]
nEstado = Estado(nEstado[0], nEstado[1])
valor_y=nEstado.get_y()
valor_x=nEstado.get_x()
if self.estrategia == 1:
valor = nodo.profundidad + 1
elif self.estrategia == 2:
if(nodo.padre==None):
nodo.valor = 1
valor = 1/(nodo.profundidad + 2)
elif self.estrategia == 3:
valor = nodo.costo[0] + float(listaSucesores[i][2])
elif self.estrategia == 4:
valor = nodo.costo[0] + float(listaSucesores[i][2]) + heuristica
elif self.estrategia == 5:
valor = heuristica
nuevoNodo = Nodo(nodo, nEstado, valor, nodo.profundidad + 1, (nodo.costo[0] + float(listaSucesores[i][2]),max(nodo.costo[1], float(listaSucesores[i][3]))) , heuristica, listaSucesores[i][0])
frontera.insertar(nuevoNodo)
def algoritmo_busqueda(self, factor_avance,altura_maxima,mapa):
camino = []
frontera=Frontera()
nodoInicial = Nodo(None, self.problema.estado_inicial, 0, 0, (0,0), 0, "None")
frontera.insertar(nodoInicial)
while ((not self.solucion) and (not frontera.esta_vacia())) :
nodoActual = frontera.sacar()
if self.problema.objetivo(nodoActual.estado):
self.solucion = True
else:
if not self.compruebaVisitado(nodoActual) and nodoActual.profundidad < self.cota:
self.visitados.append(nodoActual.estado.id)
self.expandir(nodoActual,factor_avance,altura_maxima,mapa,frontera)
if self.solucion:
print("\nSolucion encontrada\n")
return nodoActual.creacamino(camino)
else:
print("No existe una solucion\n")
I need to know the reason which I am genereting 2 more id nodes but the other results like cost, valor, or deep are right and id node are wrong