Top

Published in:

2016 | OriginalPaper | Chapter

4. Search Methods

Author : Mariusz Flasiński

Published in: Introduction to Artificial Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We begin our presentation of AI models with search methods not only for chronological reasons, but also because of their methodological versatility.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Computational Intelligence

next chapter Evolutionary Computing

Deciding which aspects are essential and which should be neglected is very difficult in general. This phase of the construction of a solution method is crucial and influences both its effectiveness and efficiency. On the other hand, an abstract model is given for some problems, e.g., in the case of games.

Of course, in explaining the idea of an abstract model of problem, we will assume a “perspective of Providence” to draw a plan of the labyrinth. In fact, we do not know this plan - we know only the types of elements that can be used for constructing this plan.

The remaining nodes correspond to intermediate states of problem solving.

According to Means-Ends Analysis, MEA, discussed in Sect. 2.1.

Again, from the “perspective of Providence”, not from our perspective.

Let us recall that such a node is called the root of the tree.

Let us remember that a “black triangle” is behind us, cf. Fig. 4.1a.

Again, from the “perspective of Providence”.

Of course, assuming we do not pass through paths we have already visited.

According to the old rule of walking in a labyrinth. Otherwise, we can go round in circles.

In the case of a labyrinth this would mean that there are a lot of alternative paths at each intersection.

In case of a labyrinth it would mean that some paths are very long during a search process and some of them are very short.

The constant c is a parameter of the method.

Edsger W. Dijkstra—a professor of computer science at the Eindhoven University of Technology. His contribution to computer science includes Reverse Polish Notation, the ALGOL compiler, structured programming, and a semaphore model used in operating systems.

In the case of the labyrinth the cost could be defined as the difficulty of going along a segment of the path. The difficulty could be defined as the width of the path (let us assume we are rather fat) and the slope of the path (let us assume we are not fit).

In the case of Uniform Cost Search the order in which new states are generated is not accidental in sensu stricto. The method is not “blind” completely, because the order in which states are generated is determined by the cost function. However, this function does not say what the distance to a solution state is. Therefore, this method is not considered a heuristic method.

A good example of hill climbing is a situation when we want to reach the top of a mountain. However, we have neither a map nor a compass, we are here at night, and a dense fog hangs over the mountains. We have only an altimeter. So, according to the idea of hill climbing, we should go in the direction for which the altimeter shows the biggest increase in height.

In May 1997 Deep Blue, constructed by IBM scientists under the supervision of Feng-hsiung Hsu, won a chess match against the world champion Garry Kasparov.

The evaluation function estimates the expected utility of a game, defined by the utility function. This function is a basic notion of game theory formulated by John von Neumann and Oskar Morgenstern in 1944.

In the case of game trees we use a specific terminology. A level is called a ply. Plies are indexed started with 1 (not 0, as in common search trees).

Hence, a mini-max method.

An arrow up means that we ascribe to a node the biggest value of its successors, an arrow down means we ascribe to a node the smallest value of its successors.

Research into a program that plays checkers (English draughts) was continued by a team led by Jonathan Schaeffer. It has resulted in the construction of the program Chinook. In 2007 Schaeffer’s team published an article in Science including a proof that the best result which can be obtained playing against Chinook is a draw.

In case we analyze a tree having more plies.

It is of great importance in complex games, e.g., chess. The Deep Blue computer, playing against G. Kasparov, expanded some paths to 40 plies.

Constraint satisfaction problems are of great importance in computer science. Therefore, there is a variety of mathematical models, mainly based on graph theory, operational research, and linear algebra, that are used for their solution. In the monograph we introduce only basic ideas of AI heuristic search methods which are used for solving these problems. We refer the reader interested in CSPs to the well-known monograph of Edward Tsang [305]. For constraint programming, the monograph by Krzysztof R. Apt [8] is recommended.

Each subsequent level in the tree corresponds to a subsequent variable.

In a mathematical formulation, we seek a global maximum in the solution space.

As we more away from the summit of this hill, values of the heuristic function decrease.

In practice finding a local extremum means finding some solution which is not satisfactory.

Scott Kirkpatrick—a professor of physics and computer science (MIT, Berkeley, Hebrew University, IBM Research, etc.). He is the author of many patents in the areas of applying statistical physics in computer science, distributed computing, and computer methods in physics.

This improves the properties of a material.

This probability is determined according to the Boltzmann distribution. This defines the distribution of energy among particles in a thermal equilibrium as \(P = e^{(- \Delta E_{ij}/kT)}\), where \(\Delta E_{ij} = E(j) - E(i)\), and k is the Boltzmann constant.

Fred W. Glover—a professor of computer science, mathematics, and management science at the University of Colorado. An adviser at Exxon, General Electric, General Motors, Texas Instruments, etc.

The tabu list is a LIFO queue (Last-In-First-Out).

Title: Search Methods
Author: Mariusz Flasiński
Publisher: Springer International Publishing
Book: Introduction to Artificial Intelligence
Print ISBN: 978-3-319-40020-4

Electronic ISBN: 978-3-319-40022-8

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-40022-8_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner