Is it difficult to make an elephant out of a fly?
Recently, before writing about my thoughts on the development of AI , I decided to look at what was already written about AI on Habré. Among others, I came across an article with a rather complicated solution (through a genetic algorithm) of the well-known task of searching for metagrams : two words (nouns) of the same length were given, you need to get the second one from the first, changing only one letter and getting a meaningful word.
Salvador Dali. The temptation of sv. Anthony. 1946. (Fragment).
The Belgian Royal Museum of Fine Arts (Brussels).
Does this task really require such a complex decision? Maybe this is the task of AI? - I proceed from the definition :
(On the application of genetic algorithms in AI see the book: D. Rutkovskaya, M. Pilinsky, L. Rutkovsky, Neural networks, genetic algorithms and fuzzy systems, M .: Hotline - Telecom, 2006 ).
However, the casket opens quite simply. Let the length of each of the given words . From the dictionary of nouns write out all the words long . The number of found words we denote . These words are labels of the vertices of an undirected graph. Each pair of vertices whose labels differ by one letter is joined by an edge. To do this, we iterate over all pairs of vertices, comparing their labels - the number of pairs , number of literal comparisons . Next, we solve the typical problem of finding the shortest path between the specified vertices of the graph.
')
The dictionary of nouns from the CD-ROM to the book by Sergey Melnikov , Delphi and Turbo Pascal on entertaining examples, SPb .: BHW - Petersburg, 2006 (by the way, in this book you can find many ingenious and simple solutions to such seemingly difficult tasks with words):
Received:
It is unlikely that an ordinary person will figure out faster. Moreover, since the algorithms are used, the correctness of which is strictly proved, it is obvious that the program is guaranteed to find the shortest solution if it exists within the framework of this dictionary. But a person will not be able to prove that his decision is the shortest, as well as the fact that there is no solution. Thus, here the computer is out of competition with the person, and this task is not the task of AI.
Here are some other metagrams:
Over the last decision, the program was already thinking 25.21 seconds. Interestingly, the graph is disconnected. For example, it was not possible to find solutions for the pawn - the queen.
You can expand the task. Let the program find the longest chains with a given number of letters, that is, generate puzzles. To solve this problem, we need to take the length of the edge of our graph equal to one and calculate the matrix of distances between the vertices. This can be done, for example, using the Floyd-Warshel algorithm . So, for words in 11 letters we get:
Find a solution for a pair of cramming - winding:
In conclusion of this small note, it is worth noting that the programmer, right at the start of a new task, is trying to use a similar, well-known solution. With the growing popularity of AI methods, they will increasingly be applied to various tasks. But special care is required here - otherwise a huge elephant can turn out from a small algorithmic fly.
At the same time, all that has been said should in no way be taken as a criticism of this article with a genetic algorithm. The author of any work has the unconditional right to explore any algorithm for any task. And such research brings its benefits. In particular, thanks to him, it became possible to compare, given in this note.
(Continuation: article about graph representations ).
Salvador Dali. The temptation of sv. Anthony. 1946. (Fragment).
The Belgian Royal Museum of Fine Arts (Brussels).
Does this task really require such a complex decision? Maybe this is the task of AI? - I proceed from the definition :
AI includes tasks that a computer solves noticeably worse than a person.
(On the application of genetic algorithms in AI see the book: D. Rutkovskaya, M. Pilinsky, L. Rutkovsky, Neural networks, genetic algorithms and fuzzy systems, M .: Hotline - Telecom, 2006 ).
However, the casket opens quite simply. Let the length of each of the given words . From the dictionary of nouns write out all the words long . The number of found words we denote . These words are labels of the vertices of an undirected graph. Each pair of vertices whose labels differ by one letter is joined by an edge. To do this, we iterate over all pairs of vertices, comparing their labels - the number of pairs , number of literal comparisons . Next, we solve the typical problem of finding the shortest path between the specified vertices of the graph.
')
The dictionary of nouns from the CD-ROM to the book by Sergey Melnikov , Delphi and Turbo Pascal on entertaining examples, SPb .: BHW - Petersburg, 2006 (by the way, in this book you can find many ingenious and simple solutions to such seemingly difficult tasks with words):
The dictionary lists all the nouns of the "Orthographic Dictionary"
(106,000 words, 28th edition, 1990). [...] Typing was carried out in 1996-98 by the players of the team “Puzlary” (http://puzzle.ezakaz.ru) - Konstantin Knop, Jacob Seidelman, Valery Timonin, Viktor Kabanov, Dmitry Filimonenkov.
Received:
( ): 1501
: 2402
: (8 ) --------
: 4.59 .
It is unlikely that an ordinary person will figure out faster. Moreover, since the algorithms are used, the correctness of which is strictly proved, it is obvious that the program is guaranteed to find the shortest solution if it exists within the framework of this dictionary. But a person will not be able to prove that his decision is the shortest, as well as the fact that there is no solution. Thus, here the computer is out of competition with the person, and this task is not the task of AI.
Here are some other metagrams:
-----------
----
-------
----------
Over the last decision, the program was already thinking 25.21 seconds. Interestingly, the graph is disconnected. For example, it was not possible to find solutions for the pawn - the queen.
You can expand the task. Let the program find the longest chains with a given number of letters, that is, generate puzzles. To solve this problem, we need to take the length of the edge of our graph equal to one and calculate the matrix of distances between the vertices. This can be done, for example, using the Floyd-Warshel algorithm . So, for words in 11 letters we get:
: 3391
: 223
: 9
: -, -, -, -
: 3821.45 .Find a solution for a pair of cramming - winding:
: (9 ) ---------
: 62.12 .
In conclusion of this small note, it is worth noting that the programmer, right at the start of a new task, is trying to use a similar, well-known solution. With the growing popularity of AI methods, they will increasingly be applied to various tasks. But special care is required here - otherwise a huge elephant can turn out from a small algorithmic fly.
At the same time, all that has been said should in no way be taken as a criticism of this article with a genetic algorithm. The author of any work has the unconditional right to explore any algorithm for any task. And such research brings its benefits. In particular, thanks to him, it became possible to compare, given in this note.
(Continuation: article about graph representations ).
Source: https://habr.com/ru/post/338604/
All Articles