КОНСКА ПЪТ, Наука и живот

  • конска

Дневникът е добавен в кошницата.

КОНСКИ УДАР

Доктор на физико-математическите науки Р. БАХТИЗИН, К. ЩУКАТУРОВ.

В научно-популярната литература човек често се сблъсква с така наречените „шахматни“ проблеми, свързани с шахматни фигури, например: възможно ли е с ход на рицар да се заобиколи дъска 8х6, като е посетил всеки квадрат само веднъж? Това не е толкова лесна задача, колкото може да изглежда на пръв поглед. Лесно е да се провери, че броят на възможните ходове от всяка клетка може да бъде от 0 до 8. Представяме ги като дърво с йерархична структура. Да приемем, че "средният" брой ходове е два:

Оказва се, че при 64-ия ход броят на възможните комбинации достига 264. Това е много голям брой. Още от училище познаваме проблем от забавлението по математика за търговец, който като награда предложи да постави едно зърно на първия квадрат на шахматна дъска, две на втория, четири на третия и т.н. Броят на зърната на последният 64-и квадрат, равен на 263, се оказа толкова огромен, че надвишава всички зърнени запаси по земното кълбо. Връщайки се към нашия проблем, ние отбелязваме, че изброяването на всички възможни комбинации с помощта на посоченото дърво отнема много дълго време дори при използването на най-мощните компютри до момента (Pentium 4 - 1,9 GHz, 512 Mb RAM е използвано за изброяване). В този проблем с изброяването алгоритмите за произволно търсене са по-приемливи, когато всеки ход е избран произволно измежду възможните. Колкото и да е странно, това е случайното търсене, което значително намалява времето за изчисление. Полученият разтвор е даден по-долу.