ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Valery Bokarev                       2:5020/400     23 Nov 2001  16:03:51
 To : All
 Subject : Графы и алгоритм "пятнашек"
 -------------------------------------------------------------------------------- 
 

 Hi All,
 
 Как реализовать алгоритм поиска, котрый осуществляет перестановку исходной
 произвольной комбинации вершин графа (некоторой произвольной сетки) в заданную
 комбинацию. Сетка содержит один пустой узел, при помощи которого и происходит
 перемещение узлов (аналогия с игрой "пятнашки")? Узлов может быть произвольное
 число (до 20).
 Можно ли сразу сказать имется решение или нет?
 
 Пример.
 Исходный граф:
 
       1 ----- 3 ---- 5       7
       | \     |      |      /|
       |  \    |      |     / |
       |   \   |      |    /  |
       6    -- 0 ---- 8 --    |
                      |       |
                      |       |
                      |       |
       9 ----- 2 ---- 4 ----- 10
 
 Конечный граф:
 
       1 ----- 2 ---- 3       4
       | \     |      |      /|
       |  \    |      |     / |
       |   \   |      |    /  |
       5    -- 6 ---- 7 --    |
                      |       |
                      |       |
                      |       |
       8 ----- 9 ---- 10 ---- 0
 
 PS
 Вершина с цифрой 0 - пустая вершина.
 
 Всего наилучшего, Valery
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор