AI avec Python - Recherche heuristique

La recherche heuristique joue un rôle clé dans l'intelligence artificielle. Dans ce chapitre, vous en apprendrez plus en détail.

Concept de recherche heuristique en IA

L'heuristique est une règle empirique qui nous conduit à la solution probable. La plupart des problèmes de l'intelligence artificielle sont de nature exponentielle et ont de nombreuses solutions possibles. Vous ne savez pas exactement quelles solutions sont correctes et vérifier toutes les solutions coûterait très cher.

Ainsi, l'utilisation de l'heuristique restreint la recherche de solution et élimine les mauvaises options. La méthode d'utilisation de l'heuristique pour diriger la recherche dans l'espace de recherche est appelée recherche heuristique. Les techniques heuristiques sont très utiles car la recherche peut être accélérée lorsque vous les utilisez.

Différence entre la recherche non informée et informée

Il existe deux types de stratégies de contrôle ou de techniques de recherche: non informées et informées. Ils sont expliqués en détail comme indiqué ici -

Recherche non informée

Elle est également appelée recherche aveugle ou stratégie de contrôle aveugle. Il est nommé ainsi car il n'y a des informations que sur la définition du problème et aucune autre information supplémentaire n'est disponible sur les états. Ce type de techniques de recherche chercherait dans tout l'espace d'états pour obtenir la solution. Breadth First Search (BFS) et Depth First Search (DFS) sont des exemples de recherche non informée.

Recherche informée

Elle est également appelée recherche heuristique ou stratégie de contrôle heuristique. Il est nommé ainsi parce qu'il y a des informations supplémentaires sur les états. Ces informations supplémentaires sont utiles pour calculer la préférence parmi les nœuds enfants à explorer et à développer. Il y aurait une fonction heuristique associée à chaque nœud. Best First Search (BFS), A *, Mean et Analysis sont des exemples de recherche éclairée.

Problèmes de satisfaction des contraintes (CSP)

Contrainte signifie restriction ou limitation. En IA, les problèmes de satisfaction des contraintes sont les problèmes qui doivent être résolus sous certaines contraintes. L'accent doit être mis sur le fait de ne pas violer la contrainte tout en résolvant de tels problèmes. Enfin, lorsque nous atteignons la solution finale, CSP doit obéir à la restriction.

Problème du monde réel résolu par la satisfaction des contraintes

Les sections précédentes ont traité de la création de problèmes de satisfaction des contraintes. Maintenant, appliquons cela aux problèmes du monde réel aussi. Voici quelques exemples de problèmes du monde réel résolus par la satisfaction de contraintes:

Résolution d'une relation algébrique

Avec l'aide du problème de satisfaction de contraintes, nous pouvons résoudre des relations algébriques. Dans cet exemple, nous allons essayer de résoudre une simple relation algébriquea*2 = b. Il renverra la valeur dea et b dans la fourchette que nous définirions.

Après avoir terminé ce programme Python, vous serez en mesure de comprendre les bases de la résolution de problèmes avec la satisfaction des contraintes.

Notez qu'avant d'écrire le programme, nous devons installer le package Python appelé python-constraint. Vous pouvez l'installer à l'aide de la commande suivante -

pip install python-constraint

Les étapes suivantes vous montrent un programme Python pour résoudre une relation algébrique en utilisant la satisfaction de contraintes -

Importez le constraint package en utilisant la commande suivante -

from constraint import *

Maintenant, créez un objet de module nommé problem() comme indiqué ci-dessous -

problem = Problem()

Maintenant, définissez des variables. Notez que nous avons ici deux variables a et b, et nous définissons 10 comme leur plage, ce qui signifie que nous avons obtenu la solution dans les 10 premiers nombres.

problem.addVariable('a', range(10))
problem.addVariable('b', range(10))

Ensuite, définissez la contrainte particulière que nous voulons appliquer à ce problème. Observez qu'ici nous utilisons la contraintea*2 = b.

problem.addConstraint(lambda a, b: a * 2 == b)

Maintenant, créez l'objet de getSolution() module en utilisant la commande suivante -

solutions = problem.getSolutions()

Enfin, imprimez la sortie en utilisant la commande suivante -

print (solutions)

Vous pouvez observer la sortie du programme ci-dessus comme suit -

[{'a': 4, 'b': 8}, {'a': 3, 'b': 6}, {'a': 2, 'b': 4}, {'a': 1, 'b': 2}, {'a': 0, 'b': 0}]

Carré magique

Un carré magique est un arrangement de nombres distincts, généralement des entiers, dans une grille carrée, où les nombres de chaque ligne et de chaque colonne et les nombres de la diagonale s'additionnent tous au même nombre appelé «constante magique» .

Ce qui suit est une exécution pas à pas d'un code Python simple pour générer des carrés magiques -

Définissez une fonction nommée magic_square, comme indiqué ci-dessous -

def magic_square(matrix_ms):
   iSize = len(matrix_ms[0])
   sum_list = []

Le code suivant montre le code pour la verticale des carrés -

for col in range(iSize):
   sum_list.append(sum(row[col] for row in matrix_ms))

Le code suivant montre le code pour l'horizontale des carrés -

sum_list.extend([sum (lines) for lines in matrix_ms])

Le code suivant montre le code pour l'horizontale des carrés -

dlResult = 0
for i in range(0,iSize):
   dlResult +=matrix_ms[i][i]
sum_list.append(dlResult)
drResult = 0
for i in range(iSize-1,-1,-1):
   drResult +=matrix_ms[i][i]
sum_list.append(drResult)

if len(set(sum_list))>1:
   return False
return True

Maintenant, donnez la valeur de la matrice et vérifiez la sortie -

print(magic_square([[1,2,3], [4,5,6], [7,8,9]]))

Vous pouvez observer que la sortie serait False car la somme n'est pas au même nombre.

print(magic_square([[3,9,2], [3,5,7], [9,1,6]]))

Vous pouvez observer que la sortie serait True comme la somme est le même nombre, c'est-à-dire 15 ici.